5
$\begingroup$

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

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

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
$\endgroup$
6
  • 1
    $\begingroup$ oeis.org/A215721 $\endgroup$
    – Idéophage
    Aug 1 '17 at 23:42
  • $\begingroup$ @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. $\endgroup$
    – Théophile
    Aug 1 '17 at 23:46
  • $\begingroup$ @Théophile: Thanks, really good answer. Could you please share your code? $\endgroup$ Aug 2 '17 at 1:13
  • $\begingroup$ @user2682450 You're welcome. I have my code on another computer, but I'll be able to post it tomorrow. $\endgroup$
    – Théophile
    Aug 2 '17 at 1:34
  • $\begingroup$ @user2682450 I've added the code. If anyone has suggestions on it, please let me know! $\endgroup$
    – Théophile
    Aug 2 '17 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.