Puzzle III

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 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.

Advertisements

8 Responses

  1. I refrained from participating because I got the sense that I spoiled the last puzzle for everyone by answering so quickly.

  2. I refrained from participating because I got the sense that I spoiled the last puzzle for everyone by answering so quickly.

    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!

  3. […] 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 […]

  4. […] 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 […]

  5. 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!

  6. 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 <

  7. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: