Game Theory: Connecting Points On A Circle

"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.

• Are we assuming that the points are equidistant along the circle? Aug 1 '17 at 22:33
• @eyeballfrog The exact geometry is irrelevant. Aug 1 '17 at 22:34

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

• oeis.org/A215721 Aug 1 '17 at 23:42
• @Idéophage Thanks, that is indeed the sequence. The description of the game is slightly different (dominoes on a $1 \times n$ grid instead of points on a circle), but of course amounts to the same thing. Aug 1 '17 at 23:46
• @Théophile: Thanks, really good answer. Could you please share your code? Aug 2 '17 at 1:13
• @user2682450 You're welcome. I have my code on another computer, but I'll be able to post it tomorrow. Aug 2 '17 at 1:34
• @user2682450 I've added the code. If anyone has suggestions on it, please let me know! Aug 2 '17 at 18:53