Puzzle II

So the answer to the puzzle in the last post is… [drum roll]


“Wait a minute,” you say, “what kind of answer is that?” Well, the question was “Is it possible to 2-color the edges of a K5 so that it contains no monochromatic K3?” And the answer is Yes.

So your response is probably something like “As for the quality of ‘Yes’ as an answer, all by itself it is no better than ‘No’, or ‘Armadillo’. For that answer carries with it no explanation; the answer does not convince anyone that it is the correct answer.”

Fair enough, but how am I supposed to know what would convince you that my answer is correct? The declared winner of the puzzle decided it was sufficiently convincing to provide a coloring that had the requested properties; it is so self-evident that that constitutes sufficient proof, it was not even necessary to include “Yes” in the answer. So now it’s my turn to be an epistemological stickler: granted that your response is meant to support an answer of ‘Yes’, how do I know that your example is a valid proof? “It’s pretty obvious,” you say, “you just check all the triangles, and make sure each one has some red and some blue.” But how do I know (how do you know?) that you actually checked all of the triangles, and checked all of them correctly? Do you even know how many triangles need to be checked?

Well, since I did declare a winner, I must have had some idea of how to verify an example as correct or not. K5_no_K3I had a known, “canonical” answer that I was aiming for (Right), which can be described with the four words (count ’em): “red outside, blue inside”, or even by the two words “two cycles” (the red cycle being 1->2->3->4->5->1, and the blue cycle being 4->1->3->5->2->4). Equivalent Winning EntryThe winning (and only) entry (if you change the color names back to red and blue, instead of using black) looks like this other graph (Left). If you swap the drawn positions of vertices 3 and 4 (as indicated), you will see that the winning entry would be identical to the intended correct answer, so it is equivalently correct, in terms of demonstrating a coloring of K5 with no monochromatic K3. OK, so the winning entry is equivalent to my intended solution, but how do I even know that my solution is correct?

Well, instead of enumerating all of the triangles to show that it is correct, let me note that in the canonical answer of “red outside, blue inside”, two edges share a red edge if and only if they are ‘next to’ each other (now I mean geometrically, but if you press me, I can get more precise). Any three vertices can have at most two pairs of ‘next to each other’, thus at most two red edges, thus always at least one blue edge. So there are no red triangles. But what about blue triangles? Since there are only 5 vertices, no matter how you try to spread them out, there will always be at least two of your three that are ‘next to’ each other, and thus have a red edge, and thus do not form a blue triangle. Q.E.D.

OK, enough said about why an ‘obvious’ answer to an easy puzzle is correct. On to the next puzzle. It turns out that, modern brides being as they are, 5 reception guests are not sufficient, so our host must find a group of 6 guests which meets his paranoid criteria. So is it possible to have a 6-person party, such that

  • there are not three people who are all friends, and
  • there are not three people who are all strangers?

The equivalent question in graph theory goes like this:

Is it possible to 2-color the edges of K6 such that there are no monochromatic K3?

Here is a picture of K6, should you want to print it out or copy it as a starting point. Once you are ready to look at the answer (and read the next puzzle, the real one I’m aiming for), you can proceed to here.


11 Responses

  1. I guess we’re deadlocked now! Where do we go from here?

  2. […] Comment on Puzzle II by RubeRadComment on Puzzle II by RubeRadComment on Puzzle II by the foresterComment on Pope v. Islam by Aunt BarbaraComment on Puzzle I by Puzzle II « BlogorrheaComment on Pope v. Islam by the foresterComment on Pope v. Islam by the foresterComment on Pope v. Islam by Aunt BarbaraComment on Moses’ Law is not God’s Law by AnonymousComment on Puzzle I by RubeRad […]

  3. I have updated the post to include diagrams to help the text (or Images to humiliate the Words, if you prefer)

  4. Heh. Well, I thought about “red outside, blue inside” for the K5 puzzle, but it won’t work for K6 ’cause there are “inside” triangles in K6. Back to the drawing board…

  5. Good point! The inside triangles of 1,3,5 and 2,4,6 demonstrate exactly why my “proof” for K5 fails for K6, because this statement fails:

    no matter how you try to spread them out, there will always be at least two of your three that are ‘next to’ each other

    Good to know someone’s working on the puzzle!

  6. The answer is “no” – however, I couldn’t prove that unless I was to exhaust every color combination possible which would amount to a few markers running out. I’m sure there’s also a mathematical proof, but don’t know it. And I must say that I am writing this before looking at the answer because I didn’t see the link to go to the next puzzle until now :-)

  7. Good for you for trying (and for not peeking)! I hereby now grant you permission to go look at the answer to find the mathematical proof…

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: