Make triangle of rods (game strategy)

combinatorial-game-theory

This is a nim-like impartial game, so each possible position has a nim-value associated with it. I wrote a little program to calculate the nim-values, and the values of the starting positions are:

N  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
v  1  1  1  2  2  0  3  1  1  2  0  0  1  1  1  2  0  0  1  1  1  2  0  0  1

The game is therefore a win for the second player when $N$ is $9, 14, 15, 20, 21, 26, 27$, and a win for the first player for the other values with $4 \le N \le 28$.

Maybe the pattern of zeroes continues and it is a second player win for every $N\ge9$ with $N \equiv 2,3 \mod 6$.

For completeness, here is the c# code I used:

using System;
using System.Collections.Generic;

namespace test4
{
   class TriangleGame
   {
      static void Main()
      {
         for (int n = 3; n <= 24; n++)
         {
            CalcGame(n);
         }
      }

      static void CalcGame(int N)
      {
         int numpos = 1 << N;
         int[] nimval = new int[numpos];
         ISet<int> reachable = new HashSet<int>();
         for (int p = 0; p < numpos; p++)
         {
            reachable.Clear();
            for (int s1 = 1, m1 = 1; m1 < numpos; m1 += m1, s1++)
            {
               if ((p & m1) != 0)
               {
                  for (int s2=s1+1, m2 = m1 + m1; m2 < numpos; m2 += m2, s2++)
                  {
                     if ((p & m2) != 0)
                     {
                        for (int s3=s2+1, m3 = m2 + m2; m3 < numpos && s3<s1+s2; m3 += m3, s3++)
                        {
                           if ((p & m3) != 0)
                           {
                              int q = p - m1-m2-m3;
                              reachable.Add(nimval[q]);
                           }
                        }
                     }
                  }
               }
            }
            // find first unused number
            int k = 0;
            while (reachable.Contains(k)) k++;
            nimval[p] = k;
         }
         Console.WriteLine("Game {0} has nimval {1}", N, nimval[numpos-1]);
      }
   }
}

This is a partial answer that explains that the first player wins if $n \!\!\! \mod \!\! 6 \in \{0, 4, 5 \}$.

First thing to note is that $1$ can never participate in any triangles, so we can pretend that it does not exist and game is player on rods of length $2, 3, \ldots, n$. The main idea of first player strategy will be to always eliminate three shortest rods. It turns out that second player often can't interfere such a strategy.

1) $n \!\!\! \mod \!\! 6 = 0$. Then $(n - 1) \!\!\! \mod \!\! 6 = 5$ (there are only $n - 1$ rods that can participate in the game). The strategy of first player will be to always eliminate three shortest rods. If this is always possible, first player will win. We may note that there always will be at least $5$ rods before any turn of the first player. Now, consider three smallest rods with lengths $x_1 < x_2 < x_3$. If they don't form a triangle, then $x_3 \geqslant x_1 + x_2$. Because first player only eliminated rods with lengths less than $x_1$ before this moment, they eliminated at most $x_1 - 2$ rods (from $2$ to $x_1 - 1$). However, the second player has eliminated at least $x_3 - x_2 - 1 = x_1 - 1$ rods (from $x_2 + 1$ to $x_3 - 1$).

2) $n \!\!\! \mod \!\! 6 = 5$, $(n - 1) \!\!\! \mod \!\! 6 = 4$. We will use the same strategy: there will always be at least $4$ rods on any move of the first player.

3) $n \!\!\! \mod \!\! 6 = 4$, $(n - 1) \!\!\! \mod \!\! 6 = 3$. We will use the same strategy: there will always be at least $3$ rods on any move of the first player.

4) [I still did not solve this case.] $n \!\!\! \mod \!\! 6 = 1$, $(n - 1) \!\!\! \mod \!\! 6 = 0$. This case is interesting and probably can shed the light on the cases $n \!\!\! \mod \!\! 6 = 2$ and $n \!\!\! \mod \!\! 6 = 3$: if the first player would always eliminate three shortest rods, they will lose. I tried to use slight modifications of this strategy, but failed.

UPD

I found a proof along the same lines that the second player wins if $n \!\!\! \mod \!\! 6 = 3$
(so $(n - 1) \!\!\! \mod \!\! 6 = 2$).

Indeed, the second player will use the following strategy (except, maybe, for one move somewhere along the way; after that move the second player will continue using the same strategy): on each move, eliminate three shortest rods with length at least $4$. Obviously, the second player will win if they can keep it up: there is always at least $5$ rods before any move of the second player, so at least $3$ of them have the length at least $4$.

What could go wrong? Suppose that the three shortest rods with lengths at least $4$ are $x_1 < x_2 < x_3$ and $x_3 \geqslant x_1 + x_2$. First thing to note is that the second player eliminated only rods with lengths from $4$ to $x_1 - 1$ so far, so not more than $x_1 - 4$. Therefore, the first player definitely eliminated all rods from $x_1 + 1$ to $x_2 - 1$ and from $x_2 + 1$ to $x_3 - 1 \geqslant x_1 + x_2 - 1$, so at least $(x_2 - x_1 - 1) + (x_3 - x_2 - 1) \geqslant x_3 - x_1 - 2 \geqslant x_2 - 2 \geqslant (x_1 - 1) = (x_1 - 4) + 3$. But there is no way the first player could eliminate more than $(x_1 - 4) + 3$ rods in the meantime (because the second player eliminated only $x_1 - 4$). Therefore, $x_2 = x_1 + 1$ and $x_3 = x_1 + x_2$ and the second player eliminated all rods with lengths from $4$ to $x_1 - 1$ (and nothing else) and the first player eliminated all rods with lengths from $x_1 + 1$ to $x_3 - 1$ (and nothing else).

In this case, rods with lengths $2$ and $3$ are still here, so the second player will eliminate rods with lengths $2, x_1$ and $x_2 = x_1 + 1$. After that, only the following rods remain: $3$ and all rods from $x_3 = x_1 + x_2$ to $n$. Similar analysis shows that nothing can stop the second player from always eliminating three shortest rods with length at least $4$ from now on.

Make triangle of rods (game strategy)

Related

Recent Posts