Anybody You Know?

In the last post--when I mentioned counting the number of games in Sim--I failed to take into account any tie games.  In fact, the question can be asked, can there be any tie games?  Can we draw fifteen lines between the six vertices, and end up without any major triangles all in the same color?

To explore this possibility, I'd like to tell a little story that came to me in a dream (well, no it didn't, but it sounds better that way):

  I was invited to a gathering by my friend Alicia.  It was supposed to be a “game night,” so we were told to bring a game to play with the others.  When I arrived, Alicia was the only one there.
  “Hey there, Alicia, what game did you bring?”  I asked.  “Decided to go with an oldie,” she said, “Chutes and Ladders.”  “Classic,” I commented.
  “How about you, Karl B?  What game did you bring?” she asked. 
  “Well, it’s a new one I’ve created called Friends and Strangers,” I replied. “I’m hoping to try it out tonight.  But it depends on how many people show up.  You can play it with three or more, but you need three people who are all mutual friends or mutual strangers.”
  “Mutual strangers?” she asked, puzzled.
  Just then, another friend of mine showed up, Caroline.  “How’s it going, Karl B?  Is this where the game night is?”
  “Yes, do you know Alicia?” I said, introducing the two ladies.  Having never met before, they exchanged pleasantries.
  “How many folks do you expect tonight?” asked Caroline.
  “I really don’t know,” replied Alicia.  “I just put the announcement on the bulletin board.  It could be a really random collection of people.  Can we play your game, Karl B, with just the three of us?”
  “Not really,” I said.  “It requires three people who really know each other, or three people who know nothing about each other.  Since you and Caroline are ‘strangers,’ but I know you both, we don’t yet qualify.”
  “Weird game,” commented Caroline, munching on some celery from the food table. “I have Apples to Apples™, but that is better with more people, too.”
  “Do you always speak with little superscripts?” asked Alicia.
  At this point a new face arrived, someone I had never met before.  It turned out that his name was Daniel, and he was a friend of Caroline’s, but a new acquaintance to Alicia.
  “So can we play your game, yet, Karl B.?” asked Alicia.  “We’ve got three people who don’t know each other: I don’t know Caroline, you don’t know Daniel, and Daniel doesn’t know me.”
  Daniel thought this was an odd question, so after explaining my game’s requirements, I replied, “No, I’m afraid it still won’t work.  That’s what I meant by mutual strangers. It needs to be a three-way arrangement, or a three-way estrangement, so to speak.”  “Cute play on words,” commented Caroline.  Daniel just chewed on some chips and salsa.
  I decided to draw a diagram.  “See, before Daniel came, we had three people, so I’ll draw three labels, A, B, and C.  I’ll draw two blue lines to show that I know Alicia and Caroline, and a red one to show Caroline and Alicia are new to each other.”

 Figure 3-1

  Alicia took the pens from me.  “I get it.  Now that Daniel is here, we add a label ‘D’, and draw a blue line to his friend Caroline, and two red ones to you me as strangers.” 

 Figure 3-2

  At this point, Daniel finally spoke up.  “Okay, so to play your game, we would need triangles between three of the people, uh, I mean labels. And those triangles must be all red or all blue, right?  I mean, there's a red triangle internally here, but it falls short of the labels.”
  “Yes, that’s one one way to look at it,” I replied.
  “So,” asked Daniel, “how many people have to be at a party in order to assure that you can play your game?”
  “Um, I don’t know, really,” I admitted.  “I’ve always just foisted this on my family, and we’re all friends…”
  “Not my family,” interjected Caroline.
  “…so I was kind of hoping for three people tonight who were mutual strangers so we could test out that aspect of the game.  I've never thought of a ‘minimum’ number.”
  Daniel considered the diagram further. “Well, if no one else shows up, I’ve got Ticket to Ride™ which is fine with four people.” “More superscripts,” Alicia muttered.
  “Oh, I do hope someone else shows up,” I said.  “If someone comes who knows two of the four of us, we’ll be able to play one way or the other…I think.”
  “I’m not so sure,” murmured Daniel.
  At that point, Alicia jumped up excitedly.  “We’re about to find out!  Here comes my friend Ethan!” as one more person entered the room.  Poor guy, he was immediately assaulted with questions about who he knew in the room and who he didn’t.  After all the introductions, it turned out he was good friends to Alicia and Daniel, but Caroline and I were strangers.
  “Great!” I said.  “We should be good, now.”
  “I don’t think so, Karl B,” said Caroline ominously, studying the diagram.  She grabbed the pens and drew four more lines.

Figure 3-3 

  I stared at the diagram.  No solid-color triangles between the labels.  I looked at the people.  No mutual friends between three of them, and no mutual strangers either (although we were fast becoming acquainted).  I was stuck.  People expressed sympathy for my plight.
  “Oh, well,” I said, appreciating their kind support.  “It probably isn’t a very good game, anyway.”
  “Looks like you’ll need at least six people to guarantee you can play,” mentioned Daniel.
  “That’s what we thought about five people,” I said.  “Maybe there’s a way to end up with six people who all know each other so mediocre-ly that there aren’t three friends or three strangers.”
  “Well, here comes Frank,” said Alicia, as the sixth member of the party strolled in.  “Perhaps he has a theory about this.”

He did have a theory.  That theory is now called Ramsey's theorem, named after Frank P. Ramsey, a British mathematician who lived from 1903 to 1930.  I love Wikipedia's description of the theory:

One of the theorems proved by Ramsey in his 1928 paper On a problem of formal logic now bears his name (Ramsey's theorem). While this theorem is the work Ramsey is probably best remembered for, he only proved it in passing, as a minor lemma along the way to his true goal in the paper...[1]

 Every article I remember about Sim invokes Ramsey's theorem to prove that Sim does not end in a tie.  Ramsey's theorem states, among other things, that any 6-vertex diagram drawn with two colors (such as a Sim game board) must have a monochromatic triangle between the vertices of one color or another. Therefore, Sim cannot have a tie game.  I suppose that this is appropriate, since it was Gustavus Simmons' research on Ramsey theory which led him to invent Sim.

I have the utmost respect for Ramsey and his theory, but this "proof" that there was no tie game has always seemed a little hollow to me. I would prefer something a little more accessible than just invoking a higher-math-type theorem.  My favorite explanation goes as follows:

Consider a completely filled-in game board of Sim.  Any given vertex has 5 lines drawn from it to the other vertices.  Therefore, there must be at least three of one color or the other (see Figure 3-4).

Figure 3-4. Three lines of one color drawn from one vertex

In a completely filled-in game board, lines 3-4, 3-5, and 4-5 must all be drawn.  It is easy to see that if any of them are draw with the same color (blue, in Figure 3-4), then a monochromatic triangle will be formed.  But, if all three of them are then "safely" colored the other color (red), then we still get a monochromatic triangle (red, in this case; see Figure 3-5).

Figure 3-5. A losing game results even if "closing lines" are drawn "safely."

So there you have it: a nice little proof that the Game of Sim will not end in a tie.  And, the successful conclusion of a lovely little game-night party.

Postscript:  The game Friends and Strangers is not a real game(although it is based on a real property[2]), and I'd be intrigued with anyone's attempt to devise one along the lines described in the dream.  I suppose that if there were ever such a game, the advanced version would require either four mutual friends or four mutual strangers.  Ramsey's theory states that you would have to have eighteen people to assure one group or the other[3].  Perhaps if you invited two baseball teams together...

[1] Wikipedia, Frank P. Ramsey, http://en.wikipedia.org/wiki/Frank_P._Ramsey, retrieved 15 Nov 2013.
[2] Wikipedia, Theorem on Friends and Strangers, http://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers, retrieved 15 Nov 2013.
[3]  Wikipedia, Ramsey's theorem, sub-topic Ramsey Numbers, http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers, retrieved 15 Nov 2013.