Make triangle of rods (game strategy)

Question

There are set of rods of length $1,2,3,4 \dots N$. Two players take turns to chose 3 rods and compose triangle with non-zero area. After that this particular 3 rods are removed. If it is not possible to compose triangle then player looses.

Who has winning strategy?

---

[Edit] Some easy observations:

• We get a triangle of non-zero area, if and only if the lengths of the chosen rods, say $a<b<c$, satisfy the strict triangle inequality $a+b>c$. It may be easier to use this in the form $a>c-b$ that can be interpreted as stating that the shortest chosen rod must be longer than the length gap between the two longer ones.
• The rod of length one can never be used because $a=1$ makes it impossible to satisfy the inequalities in the previous bullet. We can simply pretend that the rod of length one is not part of the game.
• When $N=7$ removing the triple $\{3,5,7\}$ leaves the other player with rods of lengths $\{2,4,6\}$ and no legal moves. This position is a win for the first player.
• When $N=8$ removing the triple $\{4,6,7\}$ similarly leaves the second player with an impossible task. The collection of lengths $\{2,3,5,8\}$ has (just barely) too long gaps for the second player to use either $2$ or $3$ in the role of $a$. This is also a win for the first player.
• On the other hand when $N=9$ the game plays out differently. After removing the triple of rods used by the first player, five rods of lengths $2\le x_1<x_2<x_3<x_4<x_5\le9$ remain. Here $x_2\ge3$. Because $x_3\ge4$ and $x_5\le9$ we have $x_3+2x_2>x_5$. This means that either $x_4-x_3$ or $x_5-x_4$ must be less than $x_2$. Therefore the second player can pick either the rods of lengths $\{x_2,x_3,x_4\}$ or the rods of lengths $\{x_2,x_4,x_5\}$. After having removed those rods, only two remain, so the second player wins in this case.

But what happens in the general case? [/Edit, JL]

Answer 1

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]);
      }
   }
}

Answer 2

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.