So the answer to the previous puzzle is…
No winners this time; Forester was just plain wrong, Jenny gets an A for effort. As for the rest of you slackers, I’ll give you the benefit of the doubt and assume that you were working through reams of paper and wearing your red and blue crayons down to little nubs desperately trying to find a 2-coloring of the edges of K6 such that there are no monochromatic K3.
If you did try (and fail) to construct such a coloring, you are undoubtedly familiar with the question “How can I be sure there is no answer? Maybe there is an answer, but I just haven’t tried hard enough or clever enough to find it”. Which is a different question than last time’s “If I think I have an answer, how can I be sure it’s a correct answer?” Combining the problems of both of those questions, one possible answer to the question is to enumerate all colorings of K6, and demonstrate that each coloring has at least one monochromatic K3.
But I’ll spare you all of the “how do you know” sophistry from last time, and jump directly into the proof that all colorings of K6 have at least one monochromatic K3. Note that each vertex of K6 has five outgoing edges (6 minus 1, since vertices do not have edges looping back to themselves). So pick any coloring of K6, and pick any vertex (in order to refer to it later, let’s call it by the name v), and consider the colors of its 5 edges. How can they break down between the two colors? Well, the 5 edges could be all 5 of one color, and 0 of the other, or 4 and 1, or 3 and 2. That’s it. So in every case, v has at least three edges which are the same color (let’s just call it color 1, which could be either red or blue, it doesn’t matter). So let’s follow those (at least) 3 edges of color-1, and consider those neighboring vertices of v; they all have edges between them too, and those edges have colors. Now on the one hand, it could be the case that the (3) edges between these 3 neighbors of v form a triangle of color 2, in which case we have shown that this coloring has a monochromatic triangle. On the other hand, if these three neighbors do not form a color-2 triangle, then at least one of these edges has color 1. But how did we find these three vertices to begin with? They are the vertices which have color-1 edges to v! Thus, we have found a color-1 triangle, between the vertices at either end of this color-1 edge, and v. So no matter how clever you (or anyone) is in coloring edges of K6, there will be a monochromatic triangle somewhere. (Note that the reason this proof doesn’t apply to K5, is that we can’t use the starting assumption of 5 edges that gets us to 3 edges of the same color).
The Bottom Line: no matter how hard our host tries engineer a bad-table-free guest list, there will always be three guests that are all strangers, or three guests that are all friends, and thus the possibility of lame dinner conversation. This result is known as The Theorem of Friends and Strangers. In terms of a table-size of 3, there’s something special that happens between 5 and 6 guests; as we saw in Puzzle I, it is possible to color K5 without mono triangles, but with 6 vertices, it is not possible. If you generalize to arbitrary table sizes, more colors, etc., then you get the gist of the division of Graph Theory called Ramsey Theory.
Moving forward, you will be interested to know that our friend the stingy host has come into a large sum of money (and/or has gained a large number of friends). So he has had to make the giant step up to a guest-list of 100, and thus he has had to engage a much larger hall, this time with tables that seat 10. He has learned his lesson from the previous two puzzles, so he knows that there is a threshold number of guests, below which it is possible to engineer friend/stranger relationships in order to prevent any 10 guests from all being friends, or all being strangers, but above which groups of 10 friends/strangers are inevitable. But he doesn’t know which side of that threshold 100 is on. How can we help him?
In graph theory language,
Is it possible to 2-color the edges of K100 such that there are no monochromatic K10?
Now I don’t expect anyone to actually attempt to solve this problem manually, but rather just to try to think about whether it is possible for anyone who doesn’t have a PhD in math to understand this problem at all. In the next post, I will examine the numerical magnitude of the question, so that all puzzlers will despair of ever answering it.