HN Explorer

What's your favorite math proof?

9 points by RiderOfGiraffes ↗ HN
We have a lot of people here with a more-than-passing knowledge of math and who understand that math is about structure and form. For others it's just about arithmetic, formulas, calculations and equations. So I ask those with more math - what's your favorite math proof? How can you show someone that math is about elegant arguments?

Here are a few:

The infinitude of the primes.

If you take a single closed curve that is allowed to cross itself, it can always be colored checker-board style.

For a map, vertices+regions=2+borders (but not on a Moebius strip or donut)

Less accessible, but a real favorite of mine:

  1+sqrt(2) = 2 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + ...))))
From that we can deduce that sqrt(2) is irrational.

Six people at a party - you can find three who have all shaken hands, or three who have not.

Cut a Moebius strip in half lengthwise and it remains in one piece.

I have some others, but I'd like to hear yours. Alternatively, ask more.

33 comments

[ 3.6 ms ] story [ 74.9 ms ] thread
gills
I'm a big fan of e^ix = cos x + i sin x

Cook's theorem is pretty sweet too.

RiderOfGiraffes
Yah, I like both of them a lot, but I find them hard to explain to those who aren't already in some sense "into math." I was going to include Euler's equation, but left it out for that reason. I do sometimes explain 3-coloring of graphs, and can sometimes get to NP-Completeness, although it's a bit of an effort.

However, I don't want to preclude stuff that maybe can be explained, even if at first glance it doesn't seem so.

pmiller2
Maybe you should actually state Cook's theorem. :-) (It states that k-SAT is NP-complete, btw.)

Why is it important? It was the first result that identified a naturally-occurring, NP-complete problem. Thanks to Cook's theorem, to prove that problem X is NP-complete, we can always use the strategy of providing a polynomial-time reduction from k-SAT to problem X.

pmiller2
My favorite proof is Fuerstenberg's proof of the infinitude of primes, seen here: http://primes.utm.edu/notes/proofs/infinite/topproof.html
RiderOfGiraffes
That's brilliant! I up-voted you - no idea why it didn't stick.
pmiller2
The real reason it works is actually deep magic. Dirichlet's theorem states: given any two positive coprime integers $a$ and $d$, there are infinitely many primes of the form $a + nd$ where $n$ is a positive integer.

This result is one of the deeper facts of analytic number theory. I have no clue in hell how to prove it other than "look it up in Hardy and Littlewood."

dissonant
Haha. Actually, Hardy and Littlewood in 'An Introduction...' don't prove this result, stating that it is too difficult!

They do prove some subcases, though!

RiderOfGiraffes
Another one I forgot is the proof that the topology of lines through a point is the same as the topology of a moebius strip glued to a disk, which is a projective plane. That's the same as identifying antipodal points on a sphere.

That's a talk I give to 14 year-olds who seem to love it.

[deleted]
(comment deleted)
RiderOfGiraffes
Scapegoat 6

No idea how many of these might be needed, so I'll stop there. Interesting to see if this idea works. If you do, thanks for playing.

RiderOfGiraffes
I'm about to go off-line, but I'd like to run an experiment.

This submission could easily sink without a trace simply because not enough people see it. I'd like it to get voted up, but I don't care about the karma. So I've put in another few replies. If you want, up vote the submission, but balance my karma by downvoting one of the scapegoats.

Just an idea ...

blasdel
One upvote for using the word scapegoat correctly, six downvotes for cluttering the thread.

Also, if you're going to ask a chatty question, it's distasteful to say "I'll go first", especially when you are doing so in the body of the question.

RiderOfGiraffes
Well, at least downvoting the scapegoats put them at the bottom so they don't reall clutter the thread. Now that down-votes are capped at -4 I didn't know how many would be needed to make sure people had something appropriate to down-vote should they choose to play.

It appears no one did. I'm disappointed that the idea didn't work. I didn't really expect it to, but it's a shame when low expectations are lived down to.

With regards the "I'll go first," the idea was to try to set the tone by giving a few examples, and possibly inspire people who read it to go "ooh, that reminds me ..."

In short, I don't think it is distasteful, but I'll take your comment as a data point for the future. Thanks for taking the time.

allenbrunson
i'd be wary of doing this if i were you.

pg seems to frown on using the voting system for anything other than its intended purpose. probably because there is a lot more going on than meets the eye. for example, he has said in the past that this site contains code to detect voting rings. i've read things that suggest it's even more complicated than that, but he seems to prefer secrecy about how it all works, so i'll keep my speculations to myself.

a couple of months ago, another news.yc user invited people to downvote a bunch of his comments. it turned into a bit of an argument with some people, and he got banned for it. he asked to be let back in and pg granted his request, but it still seems like a place you don't want to go.

pmiller2
Another favorite: in any group of 6 or more people, there exist either three mutual acquaintances or three mutual strangers.

Proof: Assume to the contrary that there's some group of six people not satisfying the theorem. Let the six people be named $p_1$ through $p_6$. Since acquaintance and non-acquaintance are symmetric relations, we can model this by drawing between each pair of acquaintances and edge of a certain color (say red) and between each pair of strangers an edge of a different color (say blue). The result is then equivalent to saying there is no way to color the edges of the complete graph $K_6$ with two colors that doesn't produce a monochromatic triangle.

Consider the six edges incident with $p_1$. Since there are five of them, we know at least three will have the same color. WLOG, assume the three edges of the same color are red, and, further WLOG assume the other ends of these edges are $p_2, p_3,$ and $p_4$.

Now, if we want to avoid monochromatic triangles, we have to color the edges $p_2 p_3$ and $p_3 p_4$ blue. But, to avoid the $p_2 p_2 p_4$ triangle being mono-blue, this then forces the edge $p_2 p_4$ to be red to avoid forming the blue triangle $p_2 p_3 p_4$. This then yields the monochromatic triangle $p_1 p_2 p_4$.

Since all of the edge colorings after the initial three coming from $p_1$ were forced, this implies no $2$-coloring of the edges of $K_6$ exists without a monochromatic triangle.

RiderOfGiraffes
I agree, which is why I put it in the original submission. Nice that you included the proof - thanks.

I also like the infinite version: In every infinite graph there is either an infinite induced complete subgraph, or an infinite induced empty subgraph.

http://news.ycombinator.com/item?id=951250

pmiller2
Hah, I didn't notice you put it in the submission, or I probably wouldn't have written out the proof. :P I like to show this to low-level math classes (I'm a grad student, so I end up teaching freshmen a lot) with two different colors of chalk on the board. Inevitably, at least one person thinks it's pretty cool, which makes it worth it.

BTW, the infinite Ramsey theorem and the finite Ramsey theorem are equivalent. Obviously, the infinite version implies the finite version. To show the finite version implies the infinite version, you can use the countable version of Zorn's lemma (which you prove from the countable theorem of choice -- note it's a theorem, not an axiom).

pmiller2
Another favorite is Steinitz's theorem: the graphs of the $3$-dimensional convex polyhedra are precisely the $3$-connected planar graphs.

The proof isn't hard, but a bit too long for this space. :-)

kikibobo69
I've always loved the proof of the Gauss-Bonnet theorem, which ties together differential geometry and topology, and basically states that however you distort a compact, boundaryless two-dimensional Riemannian manifold, its total curvature remains the same. The proof (well, the proof I learned -- there are several) was long with many steps, each of which was simple and intuitive. It comes together in a sort of crescendo. Here: http://www.math.dartmouth.edu/~leibon/gbt/sld001.htm
instcode
Yay! I really love Euclid proof of The infinitude of primes. It is so short, simple & elegant that any starting learner could understand it easily.

http://primes.utm.edu/notes/proofs/infinite/euclids.html

I put it here: Call the primes in our finite list p1, p2, ..., pr. Let P be any common multiple of these primes plus one (for example, P = p1p2...pr+1). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete.

drallison
I am amused by the proof that all natural numbers are interesting. Sort the numbers into two lists, one of interesting numbers and the other of uninteresting numbers. If there is a smallest uninteresting number, that number would be interesting and it would not be on the list. Therefore the list of unintersting numbers is empty.
pmiller2
It's similar to the proof that all horses are the same color.

Suppose we have $n$ horses. It suffices to show they are all the same color. We do so by induction on $n$.

If $n=0$ or $n=1$, then, certainly all $n$ horses are the same color, so the base case holds.

For the inductive hypothesis, assume we've shown that all the horses in any group of $n-1$ or fewer horses are the same color, and suppose we are faced with a group of $n$ horses. Choose some horse arbitrarily and remove it, leaving a group of $n-1$ horses for our consideration. By the induction hypothesis, these horses are all the same color. Replace the horse we removed and then remove a different horse from the group. Likewise, these horses are all the same color. This then implies that all $n$ horses are the same color. Since $n$ is arbitrary, this shows that all horses are the same color.

Fizzley
Cute.

I know it's a joke, but the inductive step fails for n = 2. Each of the two groups of 1 horses being the same colour does not imply that all the horses are the same colour.

:)

pmiller2
Yeah, but it's still hella fun to throw at a class of undergrads on a Friday afternoon. :-)
Fizzley
This is similar to the following question:

Is there a positive integer that does not have an accurate semantic definition in english of less than 100 characters? (i.e. "The first number", "The first prime", "The third perfect square", etc.)

Proof that there is no such number:

Suppose there were. Construct a list of all the numbers that don't have an accurate english semantic definition in less than 100 characters. The first of these can be accurately defined as "The first number that does not have an accurate english semantic definition in less than 100 characters", a contradiction. :-P

fluffy
Those aren't proofs, those are statements (which happen to be true).