# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
bonanova
Daedalian Member

 Posted: Mon Jan 14, 2013 5:26 pm    Post subject: 1 Someone observed that a good trivia question links the familiar with the obsucure: a little-known fact regarding a familiar subject or vice-versa. Simple proofs of difficult conjectures exhibit a similar attractiveness, bordering on beauty. This forum is for sharing proofs that are beautiful to you. My fav is the proof, using two colors, that the power set possesses a higher cardinality: has no bijection with the original set._________________ Vidi, vici, veni.
Trojan Horse
Daedalian Member

 Posted: Tue Jan 15, 2013 2:40 am    Post subject: 2 The Bolzano-Weierstrass Theorem: every infinite sequence of real numbers has an infinite subsequence that is monotone (either nondecreasing or nonincreasing). It's also known as the Spanish Hotel Theorem, due to proof #2 on this webpage. I loved the proof so much, I used it in one of my classes a couple of years ago.
Jedo the Jedi
Paragon in Training

 Posted: Tue Jan 15, 2013 3:07 am    Post subject: 3 My favorite proof hasn't been proven yet...at least I'm not aware that it has._________________Paragon Tally: 18 mafia, 3 SKs (1 twice), 1 cultist, numerous chat scum...and counting.
Quailman
His Postmajesty

 Posted: Tue Jan 15, 2013 3:34 am    Post subject: 4 1=2
Jack_Ian
Big Endian

 Posted: Tue Jan 15, 2013 11:13 am    Post subject: 5 Take a square uniform grid of arbitrary size and remove opposite corners. Is it possible to fill the resultant shape with domino tiles where each tile is a rectangle exactly 2 squares long. It's quite complex until you think of it as a Mutilated Chessboard Problem Essentially, if alternate squares are coloured like a chessboard, then the removed squares are always of the same colour, leaving one colour having more squares than the other. A domino tile, when placed, will always cover a single black square and a single white square, so it can never fill the mutilated board. So simple you could explain it to a four-year-old.
groza528
No Place Like Home

 Posted: Tue Jan 15, 2013 5:09 pm    Post subject: 6 I kind of like the classic inductive reasoning problem: In how many ways can you fill a 2 x N rectangle using N dominoes?
Zag
Tired of his old title

 Posted: Tue Jan 15, 2013 6:13 pm    Post subject: 7 I'm fond of the proof that there is no highest prime. Some of the reason I like this proof has nothing to do with the math, but with events in my life. I had explained the proof to my son (who posts here as Zahariel), when he was five years old. A couple of months later we were visiting my in-laws and I was in the living room, chatting, when suddenly my father-in-law burst in. He exclaimed, "MY grandson is soooo smart -- he knows a proof that there is no highest prime number!" He went on to describe the proof, but what he described was totally incorrect, badly confused. I kept my mouth shut (thanks to previous painful experience) but later that day asked my son to describe the proof to me. He had it exactly correct.
Death Mage
Raving Lunatic

 Posted: Tue Jan 15, 2013 10:13 pm    Post subject: 8 Quail's got it almost right. The best proof is 1%=2 proof._________________* These senseless ramblings brought to you by Insanity™. If you just can't figure the dang thing out, it must be Insanity™. [YOUR AD HERE!]
extro...*
Guest

 Posted: Wed Jan 16, 2013 12:33 am    Post subject: 9 1) Godel's first incompleteness theorem. 2) Undecidability of the Halting Problem 3) Any recursively enumerable set of axioms in first order logic is equivalent to some recursive set. (equivalent in the sense that the same theorems can be derived)
The Potter
Feat of Clay

Posted: Wed Jan 16, 2013 12:56 am    Post subject: 10

 extro...* wrote: 1) Godel's first incompleteness theorem.

And now the list of elegant proofs is complete.

Personally I have always been a fan of proofs that involve the squeeze theorem. There is something fun about saying that upper and lower bounds have to be the same thing.
_________________
Artwork | Fractals | Don't ignore your dreams; don't work too much; say what you think; cultivate friendships; be happy.
Nsof
Daedalian Member

 Posted: Wed Jan 16, 2013 7:34 am    Post subject: 11 proofs - Irrationality of sqrt(2) - Infinitude of primes - Cantour's diagonalization (mentioned by bonanova) - Halting problem (mentioned by extro. there is something similar between this and Godel's incompleteness theorem. i.e. finding a function, plugging it into itself and then watch it break down) - Cook's theorem like because of the result - Green's theorem - e^iT=1. (where T=2*PI)
extro...*
Guest

Posted: Wed Jan 16, 2013 4:41 pm    Post subject: 12

 Nsof wrote: - Halting problem (mentioned by extro. there is something similar between this and Godel's incompleteness theorem. i.e. finding a function, plugging it into itself and then watch it break down)

Halting problem is interesting as one of the first examples, if not the first, of a non-computable function (that non-computable functions must exist is a simple consequence of the cardinality of the set of functions being greater than the cardinality of the set of programs).

A much more elegant and general theorem is Rice's theorem: for any non-trivial property (i.e. not always true, or always false) of a partial function, no program can decide whether some other program computes a function with that property.

Regarding the incompleteness theorem, maybe elegant isn't a good word for Godel's proof. There's really a lot that goes into the construction of "this statement has no proof in P.A." .... but it's fun to work through.

There's a radically different proof of the same theorem by Saul Kripke (an amazing logician with only an undergraduate math degree) that doesn't involve creating a self-referential proposition.
Dented Ford
Hoopy Frood

 Posted: Wed Jan 16, 2013 4:51 pm    Post subject: 13 1 = true 0 = false
referee
June 21st, 2004 Member

 Posted: Sat Jan 19, 2013 4:41 pm    Post subject: 14 I like the proof that the sum of combinatorial numbers (n 0) + (n 1) + ... + (n n) equals 2^n, because the final step is the more elegant ever: 1 + 1 = 2._________________Jan 21st, 2008: The pillaging continues. Mar 4th, 2008: Rest in Peace, Gary Gygax. May your dice always roll a natural 20 wherever you are. Be the Ultimate Ninja! Play Billy Vs. SNAKEMAN today!
Zag
Tired of his old title

 Posted: Sat Jan 19, 2013 5:41 pm    Post subject: 15 From the post in extro's thread about proofs, I started looking into proofs surrounding perfect numbers, and now I want to add Theorem of Even Perfect Numbers to this list. What a pretty proof! Part of what I liked about it was that I understood it in the amount of time I was willing to give to it -- about 10 minutes -- a crucial element that has evaded me for a few of the proofs others have posted here.
Amb
Amb the Hitched.

Posted: Sun Jan 20, 2013 12:32 am    Post subject: 16

 Quote: I like the proof that the sum of combinatorial numbers (n 0) + (n 1) + ... + (n n) equals 2^n, because the final step is the more elegant ever: 1 + 1 = 2.

So (6*0)+(6*1)+(6*2)...+(6*6) = 2 ^ 6 ???
Thok
Oh, foe, the cursed teeth!

Posted: Sun Jan 20, 2013 12:37 am    Post subject: 17

 Amb wrote: So (6*0)+(6*1)+(6*2)...+(6*6) = 2 ^ 6 ???

(n m) here is n choose m, the number of ways to choose m objects from a set of n distinct objects. There's no multiplication.
referee
June 21st, 2004 Member

 Posted: Sun Jan 20, 2013 5:22 am    Post subject: 18 Also the proof that when an inhabitant of the island of Knights and Knaves say "If I am a knight, then X", then we know for sure that he is a knight, and X is true. It's like a triple loop!_________________Jan 21st, 2008: The pillaging continues. Mar 4th, 2008: Rest in Peace, Gary Gygax. May your dice always roll a natural 20 wherever you are. Be the Ultimate Ninja! Play Billy Vs. SNAKEMAN today!
extropalopakettle
No offense, but....

 Posted: Sun Feb 10, 2013 1:36 am    Post subject: 19 The Pólya conjecture is that for any natural number n, there are at least as many natural numbers
Nsof
Daedalian Member

Posted: Sun Feb 10, 2013 2:35 pm    Post subject: 20

 The Potter wrote: Personally I have always been a fan of proofs that involve the squeeze theorem. There is something fun about saying that upper and lower bounds have to be the same thing.
Our professor called this the sandwich theorem. Squeeze sounds better.

The Euler product formula for the Riemann zeta function connects infinite summation and infinite (prime) product which at face value is not intuitive (at least for me).

The proof is relatively short
_________________
Will sell this place for beer
Zag
Tired of his old title

 Posted: Sun Feb 10, 2013 5:53 pm    Post subject: 21 That went so far over my head that I didn't even feel inclined to duck.
extropalopakettle
No offense, but....

Posted: Mon Feb 11, 2013 2:17 am    Post subject: 22

 extropalopakettle wrote: The Pólya conjecture is that for any natural number n, there are at least as many natural numbers

Another large counterexample proving a conjecture false:

Euler's sum of powers conjecture, a generalization of Fermat's Last Theorem:

a 1 k + a 2 k + ... + a n k = b k

has no solutions where n < k.

(Fermat's Last Theorem is just where n=2)

Conjectured by Euler in 1769, disproved by counterexample in 1966 with :

27 5 + 84 5 + 110 5 + 133 5 = 144 5

The smallest counterexample where k=4:

95800 4 + 217519 4 + 414560 4 = 422481 4

It's still open for all k > 5.
Nsof
Daedalian Member

Posted: Mon Feb 11, 2013 7:07 am    Post subject: 23

 Zag wrote: That went so far over my head that I didn't even feel inclined to duck.
I posted this because I thought it simpler than the theorem of even perfect numbers. (and because it connects infinite summation and product)
_________________
Will sell this place for beer
esme
^^^^-- is female! Get the pronouns right

Posted: Mon Feb 11, 2013 9:33 am    Post subject: 24

Nsof wrote:
 The Potter wrote: Personally I have always been a fan of proofs that involve the squeeze theorem. There is something fun about saying that upper and lower bounds have to be the same thing.
Our professor called this the sandwich theorem. Squeeze sounds better.

In French, this is called the "theoreme des gendarmes", the idea being that a drunk between two policemen will also arrive at the police station.

Here is a nice geometrical theorem with a proof I like a lot:

Theorem (of Monge): Given three (disjoint) circles in a plane, we regard the intersections of the two external tangents of every pair of circles. These three intersection points lie on a line.

Proof: Regard the three circles as balls resting on the plane. Then the two external tangents are just part of the tangent cone of the two balls. The summit of each cone has to lie both on the given plane (which contains a tangent line in all three cones) and in the plane that touches the three balls from above. Therefore, the three summits lie on the line which is the intersection of the two planes. QED

The above picture was taken from the thread http://mathoverflow.net/questions/8846?sort=votes&page=1 (which contains very nice proofs without words, but assumes quite a lot of background knowledge since the site is addressed to research mathematicians).
_________________
Mundus vult decipi, ergo decipiatur.
extropalopakettle
No offense, but....

Posted: Mon Feb 11, 2013 10:12 am    Post subject: 25

 esme wrote: Proof: Regard the three circles as balls resting on the plane. Then the two external tangents are just part of the tangent cone of the two balls. The summit of each cone has to lie both on the given plane (which contains a tangent line in all three cones) and in the plane that touches the three balls from above. Therefore, the three summits lie on the line which is the intersection of the two planes. QED

Wow, that has to my my favorite transition from not obviously true to obviously true. Also interesting that it goes from what seems simpler to what seems more complex (circles on a 2D plane and their tangents to spheres tangent to a plane and their tangent cones) to make the result obvious.
Zag
Tired of his old title

Posted: Mon Feb 11, 2013 11:46 am    Post subject: 26

 extropalopakettle wrote: Wow, ..

What he said. That's a beautiful proof, esme!
Thok
Oh, foe, the cursed teeth!

 Posted: Thu Feb 14, 2013 11:54 am    Post subject: 27 A proof that e is irrational: Recall e = 1/0! +1/1! +1/2! +1/3! +.... Suppose e=p/q, for some integer q which we can assume is >0. Then e(q!) = p(q-1)! is an integer. e(q!) = (q!/0!+q!/1!+...+q!/q!)+q!/(q+1)!+q!/(q+2)!+... Now e(q!) is an integer, and so is (q!/0!+q!/1!+...+q!/q!). Therefore so is the difference e(q!)-(q!/0!+q!/1!+...+q!/q!) = q!/(q+1)!+q!/(q+2)!+... = 1/(q+1)+1/(q+1)(q+2)+1/(q+1)(q+2)(q+3)+.... But the last expression is strictly bigger than 0, and it is strictly less than 1/2+1/2*1/2+1/2*1/2*1/2+... =1/2+1/4+1/8+... = 1. So it is an integer between 0 and 1, which is impossible. Hence one can not express e as p/q, aka e is not a rational number.
Zag
Tired of his old title

 Posted: Thu Feb 14, 2013 12:07 pm    Post subject: 28 I'll buy that you proved the number defined by x = 1/0! +1/1! +1/2! +1/3! +.... is irrational, but you haven't proved that it equals e (that is, the number for which the derivative of (it raised to the x) is the same value) (e x ) d / dx = e x
Thok
Oh, foe, the cursed teeth!

 Posted: Thu Feb 14, 2013 12:20 pm    Post subject: 29 Fair enough. Proving e^x=1/0!+x/1!+x^2/2!+x^3/3!+... as functions isn't that much harder (the power series converges everywhere by the ratio test, equals it's own derivative, and equals e^x at x = 0, but verifying that taking derivatives of an absolutely convergent power series can be done term by term or that there is a unique function equal to its own derivative with f(0)=1 is starting to get on the long side). Then you can just plug in x = 1 on both sides. Part of the point is that the proof that e is irrational is relatively accessible, especially compared to the proof that pi is irrational.
bonanova
Daedalian Member

 Posted: Mon Mar 11, 2013 2:11 pm    Post subject: 30 A geometrical conjecture can be proved by simple physics: the points of tangency of a non-planar quadrilateral to a sphere are coplanar. Place a point mass on each vertex of the quadrangle with value inversely proportional to the distance to its two associated points of tangency [they are equal] and the pairwise centers of mass at the ends of each side will be at the points of tangency. The center of mass of all four masses can be the combination of either of two different pairwise cm's. The four points describe two lines that intersect, and are thus coplanar. There is a geometrical proof as well. BTW, the power set cardinality proof in post 1 is not the diagonal proof mentioned in post 11 but one that uses colors: Assume a 1-1 correspondence of the elements of a set with its subsets has been established. Color an element blue if it's a member of its paired subset and red otherwise. The red elements comprise a subset that by definition cannot be paired with either a blue or a red element. Thus the power set has higher cardinality._________________ Vidi, vici, veni.
Nsof
Daedalian Member

Posted: Mon Mar 11, 2013 8:30 pm    Post subject: 31

 bonanova wrote: BTW, the power set cardinality proof in post 1 is not the diagonal proof mentioned in post 11 but one that uses colors: Assume a 1-1 correspondence of the elements of a set with its subsets has been established. Color an element blue if it's a member of its paired subset and red otherwise. The red elements comprise a subset that by definition cannot be paired with either a blue or a red element. Thus the power set has higher cardinality.
Very nice!
_________________
Will sell this place for beer
esme
^^^^-- is female! Get the pronouns right

 Posted: Tue Mar 12, 2013 12:53 am    Post subject: 32 It is even easier to prove that 1/e is irrational instead, because the tail estimate for an alternating series is just the next term instead of a majorisation with a geometric series._________________Mundus vult decipi, ergo decipiatur.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAmbAnonymousbonanovaDeath MageDented Fordesmeextropalopakettlegroza528Jack_IanJedo the JediNsofQuailmanrefereeThe PotterThokTrojan HorseZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum