Game Theory: Connecting Points On A Circle

Question

"You have 21 points on a circle and each turn a player may connect any two points with a chord so that it doesn't intersect any other chords (not even at the endpoints!). The player who can't move loses."

I want to solve this problem for a general odd number.

Progress: It is clear that P1 wins if there is an even number of points - draw a diameter and use symmetry. However, it is unclear what happens with an odd number of points.

Note that a move splits the game into two independent games. However, since the game is impartial, splitting a game into two winning positions does not guarantee a win. I tried working backwards and I tried considering the cases in which P1 or P2 can force a win OR a loss. For example, for $n = 4$, P1 can both force a win and a loss.

My stumbling block with this approach is that a player may choose to start playing a winning game on one of the games but then change his mind and start playing a losing game and it might happen that at that point he can actually force both. Any help is appreciated.

Answer 1

Let $v(n)$ be the nim-value of the game for $n$ points. Then we have $v(0)=v(1)=0$, $v(2)=1$, and the following recursive relation for $n\geq 3$: $$v(n)=\textrm{mex}\{v(k)+v(n-2-k):0\le k \le n-2\}$$ where $\textrm{mex}$ is the minimal excluded element function.

Here are the first several values:

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 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
...

The pattern repeats at a period of $34$, and the losing positions are exactly those where $$n \equiv 5,9,21,25, \textrm{or } 29 \pmod{34},$$ as well as (curiously) $n = 1, 15$, and $35$.

---

Code

Here is the Ruby code I wrote (please note that I'm not a programmer, so I'm sure there are much better ways to do this):

$stored_v = [nil]   # store previously calculated values of v so that
                    #  we don't have to recursively calculate them every time

def mex(l)          # mex (minimal excluded element) of a list l
    ls = l.sort.uniq

    for i in 0..ls.size do
        if i != ls[i] then
            return i
        end
    end
    return ls.size
end

def v(n)            # nim-value of a game with n points
    if $stored_v[n] != nil then
  return $stored_v[n]
    end

    if n <= 1 then
        $stored_v[n] = 0
  return 0
 elsif n <= 3 then
  $stored_v[n] = 1
        return 1
    else
        l = []
        for k in 0...n-2 do
            l = l + [v(k) ^ v(n-2-k)]   # bitwise XOR (i.e., nim sum) of
                                        #  games on k and n-2-k points
        end
        $stored_v[n] = mex(l)
        return mex(l)
    end
end