Two people take turns coloring a convex polyhedron

Question

Rachel and Beatrice take turns coloring the faces of a convex polyhedron red and blue, respectively. A player wins if she gets her color on three faces that share a common vertex. If Rachel goes first and both players use their optimal strategies, who wins the game?

I don't really understand where to start. I tried playing the game but that didn't help much for me because I couldn't think of any ideas. I know that for a tetrahedron, the game results in a tie. I know that for a cube the first person wins if they pick something adjacent to their first move. After this, I am not sure with a pentagon because if it is a square-based-pyramid, the first person wins if the pick the square but if it is a triangular prism, it results in a tie.

Answer 1

Generalizing that cube strategy, the first player $R$ wins if there's any face with four or more edges. Choose that face first. Whatever the second player $B$ does, there are three consecutive edges of that face with the other faces on them open. Choose the face connected to the middle edge. There are then two open faces that lead to a victory on $R$'s next move; $B$ can only block one of them, and $R$ wins.

Similarly, if there's any vertex that's part of five or more faces, the first player wins. Just keep choosing faces at that vertex until you've got three of them.

Both of these strategies win in the minimum three moves, so they don't have to worry about playing defense - the opponent doesn't get the chance to color enough faces for a chance of winning.

What polygons don't fit into either one of these categories? We need all faces to be triangles, and all vertices to have degree $4$ or less. That gives us the following system for the numbers of vertices, edges, and faces: $$3F = 2E$$ $$4V \ge 2E$$ $$V+F = E+2$$ The last equation there is the Euler characteristic, true for any polyhedron without holes. Combining these, $$12E+24=12(V+F)=4\cdot 3F+3\cdot 4V \ge 4\cdot 2E+3\cdot 2E = 14E$$ and $E\le 12$. That leads to three possibilities:

• $E=6,F=4,V=4$. The tetrahedron. Since neither player gets the chance to color three faces, it's a draw.
• $E=9,F=6,V=5$. This can be realized by building two triangular pyramids on opposite sides of the same base. The first player has a winning strategy here. Their first move is a face that covers two of the degree-$4$ vertices and one degree-$3$ vertex (because all of the faces are like that). Her second move is any face edge-connected to the first. On her third move, there are three or four winning options, of which at most two are blocked.
• $E=12,F=8,V=6$. The octahedron. As @Jaarbahd noted, this one's a victory for the first player $R$. Alternately, there's a strategy that doesn't bother with defense - for $R$'s second move, choose one of the three faces edge-connected to their first move (at least two are available). There are then four possible faces that win on the next move, and the first player's two moves can only block two of them.

So, there it is. On anything other than the tetrahedron, the first player wins in the minimum three moves, not bothering with defense. It's not much of a game.

Answer 2

I do not have an answer, but I may be able to contribute:

Consider the octohedron. You will find that Player 1 always wins with optimal strategy. Whichever face P2 picks for their first move, P1 replies by painting the opposite face. Unless P2 picks the face opposite P1's first move. In which case, P1 responds by selecting any face that is connected edgewise to P2's choie. Whatever P2 picks after that leaves a winning move.

Answer 3

All polyhedra with a vertex, $v*$, of degree 5+ is a win for player one. There are 5 faces incident to $v*$ each turn, player one chooses one of these faces, and player two is helpless. Additionally, all polyhedra with a non-triangular face, $f$, are a win for player 1. Player 1 chooses $f$ which is incident to 4+ vertices, and it plays out just like the cube scenario.

The only remaining case is the octohedron and and no pyramid, which I’ll leave you to work out.