# The Kyiv Triangle Game

There are a number of triangles of various sizes in the figure below whose three vertices are among the vertices and edges on display. Two players, Alice and Bob, take turns coloring with their own color each of the 15 vertices. Once all vertices have been colored, each of the triangles is assigned to whoever has colored with their own color most of its vertices. The winner is the player with the most triangles assigned.

Is there a winning strategy for either of the two players?

Game based on a problem in the 2005 Kyiv Mathematical Festival.

• I guess I know which player doesn't have a winning strategy..
– Bass
Commented Jan 30 at 22:59
• I assume you want to see a particular winning strategy? Commented Jan 31 at 14:35
• @quarague Yes, I do. Or some advice as to how should Alice play to maximize her chances of winning. Commented Jan 31 at 22:24
• How many triangles are there? $27$ or $16$?
– Plop
Commented Feb 1 at 16:17
• @Plop the question states "There are a number of triangles of various sizes", so it should mean 27, I think. Commented Feb 1 at 16:21

I only attempt to answer the puzzle by assuming that "triangle" means "small triangle". I started thinking about the problem before understanding how the others could see $$27$$ triangles.

    |
x|x
x | x
x x|x x
x x | x x

3
x x
x 1 x
x x x x
x x 2 x x


The first picture represents what I call the "symmetry axis" in the following. The second encodes a strategy for Alice.

Strategy for Alice: start by playing 1. Then, each turn, whenever Bob plays on an "x", play the symmetric "x" along the vertical axis; and whenever Bob plays either 2 or 3, play the other one.

Three of the four triangles crossed by the symmetry axis will be assigned to Alice, and since the rest of the configuration is symmetric, half of the remaining triangles will be assigned to Alice, and the other half to Bob.

• This also works for the 27 triangles, it seems. Commented Feb 1 at 16:18
• Oh, it looks like it, yes! Thanks for noticing this.
– Plop
Commented Feb 1 at 16:24
• There are a number of triangles of various sizes, so yah, but otherwise good job.
– Sny
Commented Feb 2 at 7:42
• In fact, playing 2 first guarantees Alice a lead by 5.
– Sny
Commented Feb 2 at 7:44
• According to my calculations Alice can win regardless of her first move. If she plays the center she can end ahead by 3 (i.e. win with 15 : 12). Commented Feb 2 at 20:33

Alice has a winning strategy.

The graph presented has 27 triangles, each of which is uniquely assigned to a player, so one player must win. Since this is a finite game, one player must have a winning strategy. Bob does not have a winning strategy since Alice can steal his strategy (thanks @Bass). Therefore, Alice must have a winning strategy. What it is, though, I do not know.

• I don't understand your second sentence. Why can't it be a draw? Commented Jan 31 at 14:13
• @DmitryKamenetsky The total score of both players is 27 which is an odd number so they can't have the same score. Commented Jan 31 at 14:34
• @quarague ah yes good point. Commented Jan 31 at 14:55

I've played several games of this and found that, in my random assignments, Alice tends to win. While I haven't proven that this is the winning strategy, I have found a strategy that I have yet to find a way to beat as player 2.

The key insight:

The way I looked at it, you want your moves to have the maximum effect. You'd never want to play a move that is the third corner of triangles that you have already claimed. So the strategy should minimize that. The strategy posted by @Plop does seem to do that, but more that Alice will never make more mistakes than Bob. So I figure you should choose the spot that maximizes the number of triangles that you are "claiming" ie placing your color on one of the corners.

Assuming that from top to bottom and left to right, the playable vertices are A - O. Thus, E, H, and I are the best with 7 triangles. Then D, F, and M are next with 6. After that the 1/3 edges, B, C, G, H, L, and N with 4 triangles. And lastly the corners A, K, and O. Alice should maximize the number of triangles that she claims. So pick the vertex that is in the highest tier and the most triangles that 1) are the second of A's color, 2) are placing a new claim in a triangle where all 3 vertices are open, 3) that have just 1 of Bob's vertices, and 4) have the fewest triangles that have 2 vertices claimed by Bob.

This seems to maximize Alice's wins. Following that strategy, regardless of what Bob does, at least in all of my test games, player 1 will win.