News for hackers. Stuff that matters.
Re:What's your favorite math proof? by pmiller2 on Monday December 07, 2009 @06:14PM (#982483)
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.

Re:What's your favorite math proof? by RiderOfGiraffes on Monday December 07, 2009 @06:17PM (#982491)
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

Re:What's your favorite math proof? by pmiller2 on Monday December 07, 2009 @06:21PM (#982502)
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).