Prove the following game never ends in a tie by the Pigeonhole Principle 2. A Ra

Question

Prove the following game never ends in a tie by the Pigeonhole Principle

2. A Ramsey game. This two-player game requires a sheet of paper and pencils of two colors, say red and blue. Six points on the paper are chosen, with no three in line. Now the players take a pencil each, and take turns drawing a line connecting two of the chosen points. The first player to complete a triangle of his/her own color loses. (Only triangles involving 3 points count). Prove that the game never ends in a tie. (Hint: think pigeonhole principle).

Explanation / Answer

Let's name points 1 to 6. For a game to end in tie, total 15 lines has to be drawn, without making triangle of single color.

Lets consider point 1, From point 1, 5 lines are drawn.

Case 1: assume that all of them of same color.

so we have 1-2,1-3,1-4,1-5 and 1-6 of same color. Now we cant use same color again as joining any other point will complete triangle as 1-x,1-y,x-y. (1<x,y<=6)

Note that we have drawn 5 lines and other color has 10, which is not possible. As lines need to be drawn in alternate order so It should be 8 or 7.

Case 2: 4 of them belong to same color,

1-2,1-3,1-4,1-5 are of same color(without loss of generality)

which means 2-3, and 3-4 have to be different color.

Now line 2-4. It cant have color of 1-2 or color of 2-3 as it will complete triangle 1-2-4 or 2-3-4. Thus game will not be tie.

Case 3: 3 of them same color.

Same above arguement is valid as we didnt use 1-5.

Now we cant have less than 3 lines of same color as total lines from single point are 5 and number of colors is two.

Hence game will never end as tie.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.