Skip to main content
OlympiadHQ

Browse · MathNet

Print

Belarusian Mathematical Olympiad

Belarus counting and probability

Problem

The vertices of the regular -gon are marked. Two players play the following game: they, in turn, select a vertex and connect it by a segment to either the adjacent vertex or the center of the -gon. The winner is a player if after his move it is possible to get any vertex from any other vertex moving along segments. For each integer determine who has a winning strategy.
Solution
Answer: for odd first player wins, and for even the second player wins.

Let be even. Let's describe the winning strategy of the second player. First, similar to the solution of E1. of the problem of Category B, note that we can assume that the first player with his first move connected two adjacent vertices and . The second player with his first move connects one of them with adjacent vertex . After that, the second player plays the game for vertices, assuming that the vertices , and "stick together" into one. It remains to check that the second player wins for . Without loss of generality let the first player connect the vertices . The second player with his first move will connect to the center of the circle. After that, there will be three components and . The first player will connect some two of them with his move and the second player will win.

Let be odd. The solution is similar to the solution of the problem of Category B, since the first player connects the center at his first move.
Final answer
Odd number of vertices: first player wins. Even number of vertices: second player wins.

Techniques

Games / greedy algorithmsInvariants / monovariantsInduction / smoothing