The point goes to solarflare...
Printable View
The point goes to solarflare...
Nah, I don't think we're doing points anymore, but if we are, I cede it to you gstercken because of clarity.Quote:
Originally posted by gstercken
The point goes to solarflare...
ice???
Never was told that there are ice cubes on the punch.
:mad:
There were no ice cubes. They were ice icosahedrons.Quote:
Originally posted by Doctor Luz
Never was told that there are ice cubes on the punch.
Forgive me for breaking in.
If this question has already been posted, I am in error. (stopped
reading at page 12)
Assume the circumference of the earth is 27,000 miles exactly.
You tie a long string around the equator. The string will be
27,000 miles long.
Now, raise the string off the earth by 1 inch.
How much more string will be required to make the ends meet?
chuck
.000032 X PI
What are your units?
miles
Oh!, that explains all!. Everybody knows that ice icosahedrons are poisonous.Quote:
Originally posted by solarflare
There were no ice cubes. They were ice icosahedrons.
I'm going to go out on a limb and guess. I calculated it, but it doesn't seem right 6.28 inches.
Does this mean that my answer was wrong? where is the member who posted the question?
How many inches are in a mile?
1 inch = .000016 miles.
the two answers given are approx. the same, however I refuse to round off irrational numbers.
I did my calcualtion in feet. Opps!
My calculation was all messed up!
In my humble opinion you are right, souldog.
Goodz13
Seeing as you are a super moderator I am going to accuss you of simply taking my answer and converting it to inches.:D
Unless I am wrong your answer is correct, but you rounded pi off to 3.14. uggg
Souldog and Goodz have the correct answer.
delta c = 2 * pi * delta r
Ans: 6.28... inches
Are you sure? I thought that there was 5280 ft in a mile, so there would be 63360 " in a mile.Quote:
Originally posted by souldog
1 inch = .000016 miles.
the two answers given are approx. the same, however I refuse to round off irrational numbers.
too few decimals.Quote:
Originally posted by souldog
Unless I am wrong your answer is correct, but you rounded pi off to 3.14. uggg
3.1415926535897932384626433832795028841971693993751058209749445923078164062
862089986280348253421170679821480865132823066470938446095505822317253594081284
811174502841027019385211055596446229489549303819644288109756659334461284756482
337867831652712019091456485669234603486104543266482133936072602491412737245870
066063155881748815209209628292540917153643678925903600113305305488204665213841
469519415116094330572703657595919530921861173819326117931051185480744623799627
495673518857527248912279381830119491298336733624406566430860213949463952247371
907021798609437027705392171762931767523846748184676694051320005681271452635608
277857713427577896091736371787214684409012249534301465495853710507922796892589
235420199561121290219608640344181598136297747713099605187072113499999983729780
499510597317328160963185950244594553469083026425223082533446850352619311881710
100031378387528865875332083814206171776691473035982534904287554687311595628638
823537875937519577818577805321712268066130019278766111959092164201989380952572
010654858632788659361533818279682303019520353018529689957736225994138912497217
752834791315155748572424541506959508295331168617278558890750983817546374649393
192550604009277016711390098488240128583616035637076601047101819429555961989467
678374494482553797747268471040475346462080466842590694912933136770289891521047
521620569660240580381501935112533824300355876402474964732639141992726042699227
967823547816360093417216412199245863150302861829745557067498385054945885869269
956909272107975093029553211653449872027559602364806654991198818347977535663698
074265425278625518184175746728909777727938000816470600161452491921732172147723
501414419735685481613611573525521334757418494684385233239073941433345477624168
625189835694855620992192221842725502542568876717904946016534668049886272327917
860857843838279679766814541009538837863609506800642251252051173929848960841284
886269456042419652850222106611863067442786220391949450471237137869609563643719
172874677646575739624138908658326459958133904780275900994657640789512694683983
525957098258226205224894077267194782684826014769909026401363944374553050682034
962524517493996514314298091906592509372216964615157098583874105978859597729754
989301617539284681382686838689427741559918559252459539594310499725246808459872
736446958486538367362226260991246080512438843904512441365497627807977156914359
977001296160894416948685558484063534220722258284886481584560285060168427394522
674676788952521385225499546667278239864565961163548862305774564980355936345681
743241125150760694794510965960940252288797108931456691368672287489405601015033
086179286809208747609178249385890097149096759852613655497818931297848216829989
487226588048575640142704775551323796414515237462343645428584447952658678210511
413547357395231134271661021359695362314429524849371871101457654035902799344037
420073105785390621983874478084784896833214457138687519435064302184531910484810
053706146806749192781911979399520614196634287544406437451237181921799983910159
195618146751426912397489409071864942319615679452080951465502252316038819301420
937621378559566389377870830390697920773467221825625996615014215030680384477345
492026054146659252014974428507325186660021324340881907104863317346496514539057
962685610055081066587969981635747363840525714591028970641401109712062804390397
595156771577004203378699360072305587631763594218731251471205329281918261861258
673215791984148488291644706095752706957220917567116722910981690915280173506712
748583222871835209353965725121083579151369882091444210067510334671103141267111
369908658516398315019701651511685171437657618351556508849099898599823873455283
316355076479185358932261854896321329330898570642046752590709154814165498594616
371802709819943099244889575712828905923233260972997120844335732654893823911932
597463667305836041428138830320382490375898524374417029132765618093773444030707
469211201913020330380197621101100449293215160842444859637669838952286847831235
526582131449576857262433441893039686426243410773226978028073189154411010446823
252716201052652272111660396
its better
;)
1/63360 = .0000157828282.. ad infinitum
Here I was complaing about rounding off and I rounded off the conversion factor
oh Dr. Luz you have still rounded it off. I will never be satisfied with a finite approximation!!!:mad:
pi
that's better
Don't mind me, it's been a long day!:D
Who makes the next question?
Goodz13. I am afraid of asking questions. Life is a long journey to find the answer to THE QUESTION. If you ask a question what if you get THE ANSWER. the journey would be over.
Not if the answer leads to more questions.Quote:
Life is a long journey to find the answer to THE QUESTION. If you ask a question what if you get THE ANSWER. the journey would be over.
What row of numbers comes next?
1
11
21
1211
111221
312211
13112221
I found this one. I didn't make it up.
Sorry but thats a repeated one!
Is difficult to read all the 680 posts and remember all the questions.
The answer is:
413213
I'm too lazy to make one up myself, so I found another
A man walks up to you and says - "everything I say to you is a lie."
Is he telling you the truth or is he lying?
Or you can go Doctor Luz since you answered first.
Is not true neither false. Is a contradiction.
If he is telling the truth he lies, then he is not telling the thruth
if he is liying then he has told the truth, then he is not liying, and so on ad infinitum.
I'm lazy today too.
Here is an old one.
How would you join all the picture points whith only 4 straight lines without leaving the pen from the paper?
hmm... Do you mean to ask: Can it be done with four lines?
Seems to me the answer is no.
let
f(line) = the number of points covered by a line and not by any of the previously drawn lines.
clearly only one of the lines can have f(line) = 3. Since you can not lift the pencil at least one endpoint of two consecutively drawn lines must coincide.
I claim that f(line) = 1 for one of the four lines
Suppose Not
then three of the lines have f(line) = 2 and and one line has f(line)=3.
If not then f(line)= 2 for all of the lines and so does not cover 9 points.
The only way a line can have f(line) = 3 is to be the first line and since the next line drawn has f(line) = 2, this first line must draw from a corner to a corner.
now since the next line has f(line) = 2 and starts at a corner it also must draw form a corner to a corner.
and repeat, since the third line has f(line) = 2 and starts at a corner it must draw to the last available corner.
since the forth line starts at a corner and has f(line)=2. it also must draw to a corner, but all corners have already been covered
contradiction.
so at least one line has f(line)=1 so you can not cover 9 points shown with four lines
Quote:
Originally posted by Goodz13
What row of numbers comes next?
1
11
21
1211
111221
312211
13112221
Wait a sec... shouldn't it be 1113213211?Quote:
Originally posted by Doctor Luz
The answer is: 413213
I will attempt to draw this without using a picture:Quote:
Originally posted by Doctor Luz
How would you join all the picture points whith only 4 straight lines without leaving the pen from the paper?
I hope you can understand that ... ;)Code:_._._.
\. ./.
.X. !
\|
well of course you can do it if the lines are not required to begin and end at one of the points in the grid. That can't be the question because there is no challenge in it. Please clarify Dr. Luz.
well, I take it back, I guess the challenge was to see that you could terminate outside the grid. Assuming this is what was meant by the question
hehe... that's right, cover up the mistake... or just delete the post... ;)Quote:
Originally posted by souldog
well of course you can do it if the lines are not required to begin and end at one of the points in the grid. That can't be the question because there is no challenge in it. Please clarify Dr. Luz.
well, I take it back, I guess the challenge was to see that you could terminate outside the grid. Assuming this is what was meant by the question
Really the solution is that posted by solarflare.
Sorry if I have not been clear. I did not told that there is not any restriction about finishing the lines in the grid points.
Well there is no shame in being wrong, so why would I delete the post?Quote:
Originally posted by solarflare
hehe... that's right, cover up the mistake... or just delete the post... ;)
OK.. I would like to be able to ask a couple of questions in succession. They are simple questions and the result is nice.
I will include all the definitions needed
DEFINITIONS:
Given a set V and a set C of functions between subsets of V,
where V is the union of the domains and ranges of elements of C,
define a graph G(V,C)= {<x,y,c>| x, y are in V, c is in C and c(x) = y}
Elements of V are called vertices while elements of G(V,C) are called edges. given an edge e= <x,y,c> x is the first vertex, y is the second vertex and c is the color of e.
If X =The union of the domains of elements of C is disjoint from Y =the union of the ranges of elements of C then the graph is called a bipartite graph and is denoted B(X,Y,C)
Finally if the elements of C generate a group acting on V, then G(V,C) is called a cayley graph. and is denoted Gc(V)
Here a group G is said to act on a set V if each g in G corresponds to a permutation of V, for all g, h in G and x in V g(h(x)) = (gh)(x) and the identity of G is the identity permutation. The group G is said to act without non-trivial fixed point if no non-identity element of G fixes an element of V. if g(x)=x iff g = e the identity.
Two distinct edges of a graph are adjacent if they share a vertex and two vertices are adjacent if they are elements of a single edge. The valency of a vertex v is the cardinality of the set of vertices adjacent to it and the degree of a vertex is the cardinality of the set of edges containing it.
A path P=P(e1,...en) in a graph is a sequence of distinct edges e1...en, where for each i = 1,...,n-1 edge i is adjacent to edge i+1. and no vertex of P is contianed in more than two edges of P. note the following is a path p = {<x,y,c>, <x,z,c'>} i.e. a path can start in the range. Given a path p(e1,...,en) with e1=<x,y,c> and en=<z,w,c'>, if y is a vertex of e2 then P starts at x, otherwise it starts at y. If z is a vertex of edge n-1 then P ends at w, otherwise it ends at z. A path which starts at x' and ends at w' is said to connect x' to w'. P is called a cycle when it start at x', ends at w' and x'=w'. By convention any vertex x is connected to itself by a path of length 0.
Clearly the property of being connected defines an equivalence on the vertices of G(V,C) and restricting the functions in C to an equivalence class yields a subgraph of G (By these definitions a subgraph is just a subset) called a connected component. Any two distinct connected components are disjoint. Define the path-distance between two vertices x and y of a connected component by min{length(P), P connects x to y}. Note that path-distance defines a integer valued metric on a connected component.
A subset I of a bipartite graph B = B(X, Y, C) is called a matching if distinct elements of I are not adjacent. A vertex v of the graph B iis said to be covered by the matching I if it is in some and so exactly one element of I. A perfect matching is one which covers all elements of B.
END OF DEFINITIONS
Prove the following
Lemma: Let B(X,Y,C) be a bipartite graph. If the valency of each vertex of B is at least two and each connected component of B contains at most one cycle, then B contains a perfect matching.
I must say, souldog, that if questions in college had been this interesting, I would have done my homework more often! It is one of the smoothest, quickest, tightest introductions into the connection between homology and graph theory (and expressly forming the graph theory on function theory!). Although this is a great foundation to start learning either graph theory or homology, I must say I have never seen a book with that form...
Anyway, for the solution I would begin with a lemma from homology: a path P with no loops has a boundary d(P) that consists of at least 2 points with a valency of less than or equal to 1. Its a simple inductive proof on paths with no self-interception inducted over path length.
Now, you only have to look at each component, since a perfect matching for each connected component gives a perfect matching forthe entire graph through union (since there are no connections by definition between distinct connected components).
The key is that for each vertex with at least two valence, we can arbitrarily distinguish 2 edges as "in" and "out" with repect to that vertex (ie. we can direct two edges relative to each vertex). We look at the X and Y components of the bipartite graph and choose an arbitrary element of X which we label x1 (by the theorem of choice -- the finite version of the axiom of choice -- because we want to enumerate an ordering on the sets X and Y). Construct a path P from x1 by the following rule: after a choice of in and out directings on x1 has made, choose the edge out as the next element of the path. Following this procedure, you label the vertices reached y1, x2, y2, ... until the path forms a cycle and an edge contains a previously used vertex. We know that each connected component must have at least one loop by the lemma and the knowledge that there exist no valence 1 vertices. If the subsets of X and Y contained in the path that has looped upon itself (call the subsets xx and yy) are not the entire sets X and Y then we look at X disjoint xx and Y disjoint yy and build a new path until it loops or a vertex is constricted (its out must go to a vertex of other path). The same is done backwards for the in to the first vertex, and we arrive at one of two situations: either both in and out connect to the first path or a second loop is formed separate from the first loop. In the first case we also have a new loop separate from the initial loop, since the path separating the vertices in and out connect two disjoint paths (and thus a loop). Thus there is a contradiction and you have proved that all vertices of X are in xx and all of Y in yy.
So finally, you just look at the subset of the path that connects the "out"s only from X's to Y's (x1 out to y1, x2 out to y2). This is a matching (no adjacent edges) and the contradiction above proves it is perfect. You also get a nice relationship on the fact that the bipartite graph must have equal cardinality Xs and Ys if it is to have all vertices valence 2 or greater yet only one loop. As mentioned above the union of all the perfect matchings in each component gives the perfect matching for the graph.
This formulation of graph thoery was worked out by my twin brother and I. I really like it beacuse all the various structures you usually consider are just subsets of the original graph.
I don't think your proof quite works. There is no assumption that the cardinality of the connected components is finite. In particular there may be connected components which contain no cycles.
It is a very slick proof of the finite case. Maybe I have misunderstood something?
I must admit I had you in mind Galathaea when I asked this question. I hope you keep working on it, I think you will like where it goes next...
Aha! Infinity, my long time friend and sometimes enemy... I will have to have a talk with her...
Ah.. now that I am back at work, I have more time to think about this little bugger :)! I'll just post some of my random thoughts since I find if I commit my thoughts to public perusal, my brain works a bit harder at working things out...
Ok. So the loss of the assumption of finite graphs makes use of the lemma unworkable. There are infinite paths (and indeed many infinite trees - those with nonterminating leaves) with no cycles and yet at least 2 valence at each vertex (the boundary of these graphs can indeed be empty). So the proof of the infinite case will probably require the use of the Axiom of Choice and construction of a possibly infinite series of cases of paths. Basically, one will probably have to use transfinite induction to show that there must be for every infinite path at least one valence 3 vertex connecting it to another path (or it would fail to be part of the connected component - a contradiction) -- but wait... that might not even be necessary. Once on has an inductive construction of paths (finite or infinite), one should be able to construct a matching in the same way as above (extending now both directions down the path if necessary). It seems that the matching over non-terminating leaves won't cause a problem with the previous construction, but I am still thinking mainly in terms of a countable selection of vertices. I guess if there were an uncountable number of vertices, the transfinite induction would still work (call a path constructed from a given choice vertex a "neighborhood" of the vertex -- then look at the case of the graph minus the path and prove each vertex still has matching element possible). Hmm... maybe the use of the idea that if a path does not include all points implies that there are at least two vertices of valence 3 is important here...
Well, it is indeed more interesting still. I will work on ironing out the ideas for a formal proof. It seems that most of the machinery from the finite proof could be gotten rid of once the infinite proof is worked out, since the lemma was too important there...
If anyone sees something terribly awry in my musings, please let me know!
Paths are always finite in length. In particular lets say that the connected components are either finite or countable. I guess we could start talking about other cases and Transfinite Induction would proably work (what to do at limit cardinals?), but is not needed.
Yes, but you really don't need to proceed by contradiction. What to do about a connected component with a cycle?Quote:
Once on has an inductive construction of paths (finite or infinite), one should be able to construct a matching in the same way as above (extending now both directions down the path if necessary). It seems that the matching over non-terminating leaves won't cause a problem with the previous construction, but I am still thinking mainly in terms of a countable selection of vertices. I guess if there were an uncountable number of vertices, the transfinite induction would still work (call a path constructed from a given choice vertex a "neighborhood" of the vertex -- then look at the case of the graph minus the path and prove each vertex still has matching element possible). Hmm... maybe the use of the idea that if a path does not include all points implies that there are at least two vertices of valence 3 is important here...
Well, I guess the cycle case is the most important, since the path pairing would seem to solve the non-cyclic case fairly easy. I am glad to hear that contradiction is not needed, since transfinite ad absurdum always makes me look twice at the problem (as our discussion on intuitionism a few months back probably illustrates :)!). I somehow think that I should go back to the function foundations and the fact that X and Y are disjoint for bipartite graphs, but I am not yet clear on the connections to be made. The functions in cycles seem to have a relationship that I cannot yet formalize or express in words, but it is based on the fact that every element of the domain must map to an element of the range (not 1 to 2, since they are functions, but 2 to 1 is acceptible).Quote:
Originally posted by souldog
Yes, but you really don't need to proceed by contradiction. What to do about a connected component with a cycle?
The brain is bending nicely on this one...
Think of the case with a cycle as a flower. The cycle sits at the middle and at each vertex of the cycle a pettle may be connected. (Of course since the vertex may have valency 2, the pettle may have withered and fallen off). If a pettle is there then it will go twisting off to infinity.
hint: In a bipartite graph a cycle has even length.
Yes! Because the cycle must be finite, no matter the component! So the x to y matching is perfect on the cycle. Then each petal has either an x to y or y to x matching with no edges adjacent to the cycle matching, thus giving a perfect matching. I think where I have been confused is that the proof of the cycle with infinite paths (flower-petal) conformation probably requires a contradiction proof as illustrated in the first attempt. But that is a finite ad absurdum, perfectly acceptable by me!
Is this more along the lines you were thinking? Have I missed an important case?
That is exactly it!. Let me note that in the definitions I gave I implicitely assumed that connected components were countable since the path metric is integer valued. i really don't want to consider any other case.
Let me give a formal proof.
To find a perfect matching in B it suffices to consider the connected components one at a time. So we may assume that B is connected.
Suppose B contains no cycles. Fix a vertex v of B. Given any vertex z of B define the cluster around z to be the set
Cz={e in B| e contains z}. Note that since B has minimum valency 2 every cluster contains at least two edges. A cluster, Cz, is called an n-Cluster if z is of distance n from v. Define the distance between an edge and v to be the minimum of the distances between v and the vertices of e. Since B contains no cycles, any n-Cluster with n>0, has a unique edge closest to v.
To construct a perfect matching choose some edge e in the 0-Cluster Cv. Let I0 = {e} and O0 = Cv\{e}. Having defined I0,...,In-1, Let In and On be the smallest subsets of B extending In-1 and On-1, respectively, such that for any n_Cluster Cz:
1) If the edge in Cz closest to v is in In-1 then all the other edges in Cz are in On.
2) If the edge in of Cz closest to v is in On-1, then there is a unique edge of Cz in In and all other edges are in On.
It is easy to see that I= (union In) is a perfect matching in B.
Suppose B contains exactly one cylce C. Since C is a cycle in a bipartite graph, it has even length. Therefore we may devide the edges in C into two sets Ic and Oc such that if and edge is in one of these sets then the two edges adjacent to it are in the other set. So Ic is a perfect matching in C. Let v1,....v2l be the vertices of C. for i = 1,...,2l let Bi be the subgraph of B determined by the set of edges containing a vertex connected to vi by a path disjoint from C. Since Bi intersection Bj is null for i != j, it suffices to find a perfect matching in Bi union C extending Ic for each i = 1,...,2l. So fix i and let Io = Ic and O0 = (Oc union Cvi)\Ic, and proceed as in the first part of the lemma, considering clusters contained in Bi. This construction gives the desired perfect matching in Bi union C. Finally let I = Union Ii i=1,...,2l
Thats it. Now let me ask the next question. I want to tie this into the subject of ammenability.
DEFINITIONS:
Let a group G act on a set X. The set X is said to be G-paradoxical if for some m,n there are disjoint sets A1,...,An,B1,...Bm contained in X and group elements g1,...,gn. h1,...,hm such that both {g1(A1),...,gn(An)} and {h1(B1),...,hn(Bn)} are partitions of X. The set X is said to be (m,n)-paradoxical under G if in addition {A1,...,An,B1,...,Bm} is a partition of X.
The two notions are actuallu equivalent.
More generally, two subsets A and B of X are said to be G-equidecomposable if there are disjoint sets A1,...An partitioning A and disjoint sets B1,..,Bn partitioning B and group elements g1,...,gn such that gi(Ai)=Bi for i = 1,...,n
A Construction:
Suppose X, Y, and C are as in the definition of a bipartite graph and I is a partition of C, <Ca| a in I>. For each a in I Let Ya = union over c in Ca of ran(c). Let YI = union over a in I of (Ya X {a}) this is the cross product. Extend the functions: For each a in I and c in Ca, define c' : X -> Ya X {a} by c'(x) = <c(x), a>. Then let CI = {c': c in C}. Then since YI = Union over c' in CI of ran(c') we have the bipartite graph B(X, YI, CI).
Kind of a funky construction. The first vertex set is just X, while the second vertex set has distinguished (and perhaps duplicated) subset of Y. Note in the case when X and Y are "the same set" and the functions are group elements and so permutations (not partial) then YI will have multiple copies of Y.
END OF DEFINITIONS:
Prove the following
Proposition: Suppose G is a group acting on a set X. Then X is (m,n)-paradoxical under G if and only if there are C={g1,...,gm, h1,...,hn} contained in G and I = {g, h} as in the above definition (i.e. I is index set for partition of C {g1,...,gm} and {h1,..,hn}) such that B(X, XI, CI) contains a perfect matching.
wow alot of writing
You know... from here you could just launch into simplexes, complexes, chains, and homology. Or you could take a dtour into sperner's theorem, sieve algorithms, and more combinatorial results (which have some nice representations as results on 0-1 graphs -- which in many ways have results dual to bipartite graphs). Maybe take a diversion into the Banach-Tarski paradox where group amenability has, in one way, its origins. I don't know, maybe even focus down on the general algebraic results of the actions thus defined...
All I am saying is that this is one of the nicest series of questions to start a tour of modern discrete mathematics I have seen. I mean, truly this should be explored. It beats the work I have in my notebooks for succinctness, and I've been whitling away at just such a foundations for years...
Now to start the actual figuring...
Once you have proven the above proposition you will have basically proven the Banach-Tarski Paradox;) That is where I was heading. I will add that this prop. is pure definition manipulation.
11>4
That's what you think..Quote:
Originally posted by solarflare
11>4
Would this be true in certain p-adic fields??Quote:
Originally posted by solarflare
11>4
Yes and yes. But I guess this means nobody watches Futurama?? Not that I expected you would...