Competition problem — Combinatorics

Library / /46 of 61

Combinatorics Difficulty 6.9 National olympiad Prove it Belarus

The vertices of the regular $n$ -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 $n$ -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 $n \ge 3$ determine who has a winning strategy.

Solution

Answer: for odd $n$ first player wins, and for even $n$ the second player wins.

**Let $n$ 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 $P$ and $Q$ . The second player with his first move connects one of them with adjacent vertex $R$ . After that, the second player plays the game for $n-2$ vertices, assuming that the vertices $P$ , $Q$ and $R$ "stick together" into one.
It remains to check that the second player wins for $n = 4$ . Without loss of generality let the first player connect the vertices $A_0, A_1$ . The second player with his first move will connect $A_2$ to the center of the circle. After that, there will be three components $A_0A_1, OA_2$ and $A_3$ . The first player will connect some two of them with his move and the second player will win.

**Let $n$ 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.