Game of polygons

Question

Initially, there is a polygon with N vertices drawn in the plane. The polygon is strictly convex, i.e., each internal angle is strictly smaller than 180 degrees. The vertices of the polygon are numbered 1 through N, in clockwise order.

Two players play the game on this polygon. The players take alternating turns. In each turn, the current player chooses a diagonal or a side of the polygon and draws it as a straight line segment. (A diagonal of the polygon is a line segment that connects any two non-adjacent vertices of the polygon.) The player is only allowed to choose a diagonal or a side that does not intersect any of the previously drawn segments (it must not share endpoints with any of them either). The player who cannot draw a diagonal or a side according to the above rules loses the game.

You are given the int N.

We assume that both players play the game optimally. Return 1 if the first player wins and 2 otherwise.(player 1 always starts the game)

Input   Output

3        1

4        1

15       2

Answer 1

This is a Nim-like game.

We start with a "heap" of $n$ vertices, and a move parts a heap of $a\ge2$ vertices into two smaller heaps with $b,c$ vertices, where $b+c=a-2$ and $b,c\ge 0$.

Equivalently, we have $(b+2)+(c+2)=a+2$, i.e. the game can also described like this:

We start with a single heap with $n+2$ tokens, and a move consists of partitioning a heap into two smaller heaps of at least two tokens each.

A single heap of $n$ tokens is equivalent to some nimber $[m]$, and we wish to determine $m=f(n)$. Then the original game is won for the first player if and only if $f(n+2)\ne 0$. If I'm not mistaken, the sequence $f(n)$ begins like this: $$0, 0, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 2, 7, 4, 0, 1, 1, \ldots $$ and I cannot say that I recognize a real pattern. Also, the sequence of $n$ such that $f(n)=0$ starts like this: $$1,2,3,7,11,17,23,27,31,37,41,45,57,61,65,75,79,91,95,99,\ldots$$ and again I cannot recognize a simple pattern. (The fact that $17=15+2$ occurs in this list corresponds to the sample case of the $15$gon that is won by the second player).

However, here's an algorithm to compute $f(n)$ recursively (a computer program with memoization suggests itself, and that's how I determined the sequences given above):

• For $n\le 3$, $f(n)=0$
• For $n\ge 4$, compute $f(a)\oplus f(n-a)$ (bitwise XOR) for $a=2,\ldots, n-2$; then $f(n)$ is the smallest nonnegative integer not occuring among the results.