Colouring a Pentagram

CJ and Dan are playing a game in which they take turns coloring the sides and diagonals of a regular pentagon, shown in white to the right. CJ uses a blue marker while Dan uses a red marker. A player can only color the entire segment between two vertices of the pentagon , and cannot color a segment that has already been colored. The first player to make a triangle entirely of their own color for which all three vertices are vertices of the pentagon wins the game.

If CJ goes first and both players play optimally, who will win the game?

CJ Dan It will be a draw

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Patrick Corn
Nov 28, 2017

First case: CJ and Dan pick edges that share a vertex. In this case, CJ picks another edge from the shared vertex, which Dan must block by taking the third side of the triangle. Then CJ picks the final edge from the shared vertex, and is now threatening to make two different triangles. Dan cannot block both of these.

Numbering vertices, say CJ picks 12 and Dan picks 15. Then CJ picks 13, so Dan must take 23, and then CJ picks 14, and will win on his next turn by either taking 24 or 34.

Second case: CJ and Dan's edges don't share a vertex. WLOG CJ picks 12 and Dan picks 34. Then CJ picks 15, so Dan must take 25, and now CJ picks 13 and will win on his next turn by either taking 23 or 35.

Edit: sorry, I feel like the problem is a bit ambiguous. Are we always connecting two vertices of the pentagon or are we coloring the smaller line segments in between? I assumed the former; if the latter, then the problem is harder than my solution suggests.

I think it's more than just a bit ambiguous

Peter Anderson - 3 years, 6 months ago

So what happens in the first case if Dan picks 13 instead of 15?

Mirek Baudys - 3 years, 6 months ago

Log in to reply

CJ takes 15, so Dan must take 25, and then CJ picks 14, and will win on his next turn by either taking 24 or 34.

Patrick Corn - 3 years, 6 months ago

I think two different color that share a vertex, that vertex have two colors.

Kelvin Hong - 3 years, 6 months ago

Looks like they disabled answers because this problem is flawed...

Skoteh90 . - 3 years, 6 months ago

Log in to reply

I don't think they did.

Sharky Kesa - 3 years, 6 months ago

No, we only colour the segments between two vertices of the pentagon. Also, the triangle must be formed by three of the vertices of the pentagon. Also, this solution is slightly flawed since I've said a segment between any two vertices, not adjacent vertices.

Sharky Kesa - 3 years, 6 months ago

Log in to reply

Not sure where the flaw is. The symmetry of the graph makes "adjacency" moot, no?

Patrick Corn - 3 years, 6 months ago
Steven Yuan
Dec 5, 2017

Label the vertices A, B, C, D, and E going clockwise from the top vertex. CJ's strategy is start by coloring in one of the diagonals of the pentagon, then coloring in another diagonal that shares a vertex with the first one, regardless of what Dan does. A sample game might begin:

Turn CJ Dan 1 A C B C 2 A D \begin{array}{c|c|c} \text{Turn} & \text{CJ} & \text{Dan} \\ \hline 1 & AC & BC \\ 2 & AD & \\ \end{array}

This combination of beginning moves will threaten to form a triangle, so Dan must block it:

Turn CJ Dan 1 A C B C 2 A D C D \begin{array}{c|c|c} \text{Turn} & \text{CJ} & \text{Dan} \\ \hline 1 & AC & BC \\ 2 & AD & CD \\ \end{array}

In doing so, Dan might threaten to form a triangle of his own, so CJ must block it, but after some number of moves, Dan can no longer threaten to form any triangles:

Turn CJ Dan 1 A C B C 2 A D C D 3 B D A B \begin{array}{c|c|c} \text{Turn} & \text{CJ} & \text{Dan} \\ \hline 1 & AC & BC \\ 2 & AD & CD \\ 3 & BD & AB \end{array}

After this happens, CJ can clinch the win by choosing a vertex shared by two diagonals and coloring in a side containing that vertex:

Turn CJ Dan 1 A C B C 2 A D C D 3 B D A B 4 D E \begin{array}{c|c|c} \text{Turn} & \text{CJ} & \text{Dan} \\ \hline 1 & AC & BC \\ 2 & AD & CD \\ 3 & BD & AB \\ 4 & DE & \\ \end{array}

This will always threaten to form two triangles - in the sample game, they are B D E BDE and C D E CDE - which Dan cannot block simultaneously. Therefore, CJ will always win the game.

Can you explain why this strategy always results in two triangles eventually?

Sharky Kesa - 3 years, 6 months ago

Aren't you coloring again the same segment? Even if that color is the same?

Mateus Marcuzzo - 3 years, 6 months ago
Cesare Sibra
Dec 4, 2017

CJ goes first and chooses one of the sides of the inverted little pentagon in the centre.

Then Dan makes his move, he can choose everything he want to fight back CJ's previous move.

Then CJ chooses one of the diagonal's segments linked with the one he had chosen first.

Finally, Dan tries to choose another segment to put back his opponent but with his third and last move CJ will win every single time, provided that he plays first.

In this game whoever plays first is, basically, the winner.

Cecil Merrell
Dec 8, 2017

It's the same concept in tic tactics toe. And in mini miny moe For every even number of moves the first player will win

Barrie Callender
Dec 10, 2017

If both players play optimally then whoever goes first will win assuming playing optimally means to win.

That need not always be true. For example, if the (contrived) game is "each turn you can remove 1 stone from the pile" and we start with 4 stones, then clearly the 2nd player would win.

Calvin Lin Staff - 2 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...