So the answer to the previous puzzle is…

No.

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 K_{6} such that there are no monochromatic K_{3}.

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 K_{6}, and demonstrate that each coloring has at least one monochromatic K_{3}.

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 K_{6} have at least one monochromatic K_{3}. Note that each vertex of K_{6} has five outgoing edges (6 minus 1, since vertices do not have edges looping back to themselves). So pick any coloring of K_{6}, 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 K_{6}, there will be a monochromatic triangle somewhere. (Note that the reason this proof doesn’t apply to K_{5}, 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 K

_{100}such that there are no monochromatic K_{10}?

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.

classnotes, on October 1, 2006 at 9:12 pm said:I refrained from participating because I got the sense that I spoiled the last puzzle for everyone by answering so quickly.

the forester, on October 3, 2006 at 5:14 am said:Obviously that’s not a problem for me. In fact it seems my early answer served double-duty as a red herring — in which case, RubeRad, you’re welcome!

RubeRad, on October 3, 2006 at 5:24 am said:Indeed, you meant it for sarcasm, but God meant it for good!

Puzzle III.1: Permutations « Blogorrhea, on October 3, 2006 at 7:26 am said:[…] Comment on Puzzle III by RubeRadComment on Puzzle III by the foresterComment on “Day-Age” Creation Outline by the foresterComment on Puzzle III by classnotesComment on Puzzle II by Puzzle III « BlogorrheaComment on “Day-Age” Creation Outline by RubeRadComment on “Day-Age” Creation Outline by the foresterComment on New Dimensions in Evangelism by RubeRadComment on “Day-Age” Creation Outline by RubeRadComment on “Day-Age” Creation Outline by the forester […]

Puzzle II « Blogorrhea, on October 3, 2006 at 7:29 am said:[…] foresterComment on “Day-Age” Creation Outline by the foresterComment on Puzzle III by classnotesComment on Puzzle II by Puzzle III « BlogorrheaComment on “Day-Age” Creation Outline by RubeRadComment on “Day-Age” Creation Outline by theforesterComment on New Dimensions in Evangelism by RubeRadComment on “Day-Age” Creation Outline by RubeRadComment on “Day-Age” Creation Outline by the forester […]

the forester, on October 12, 2006 at 8:25 am said:This is another laughable answer, but I pose it so that you will give up waiting for the correct response and move on!

Yes, it is possible to 2-color the edges of K100 such that there are no monochromatic K10. It works as long as monochromatic KX2 is less than KY, where X is the number of seats at each table, and Y is the total number of guests.

Now have a great belly laugh, correct me, and

resume blogging!RubeRad, on October 12, 2006 at 8:52 am said:Ho, Ho, Ho!

Thx for the encouragement, and note that I do have a (short, non-Puzzle) post in the pipeline. And alas, I’m not waiting for the correct answer, just waiting for more free time!

To clarify, I think what you are saying is that your answer is that things change between 10 and 11, because 10 squared =100, but 11 squared=121>100. It’s an interesting theory, but the first big problem comes when you try to validate it against our known examples: 3 squared is 9, which is bigger than both 5 and 6, so your hypothesis would force both examples to behave the same.

(P.S. note that it is not equals signs, but less-than and greater-than symbols that interfere with HTML, but you can get them the hard way with the special 4-character codes > and <

Puzzle III.2: Combinations « Blogorrhea, on October 13, 2006 at 5:14 am said:[…] Comment on Unchained by Jeff KazulesComment on Unchained by RubeRadComment on Unchained by Jeff KazulesComment on Theonomy II by Unchained « BlogorrheaComment on Heresy by Unchained « BlogorrheaComment on Puzzle III by RubeRadComment on Puzzle III by the foresterComment on Announcement by RubeRadComment on Puzzle II by RubeRadComment on Puzzle II by Laura Davis […]