Hacer triangulo de barras (juego de estrategia)

Question

Hay un conjunto de varillas de longitud $1,2,3,4 \dots N$. Dos jugadores se turnan para elegir 3 varillas y componer triángulo con los no-cero de la zona. Después de que este particular 3 varillas son eliminados. Si no es posible componer triángulo entonces el jugador pierde.

Que tiene estrategia ganadora?

---

Algunas observaciones:

• Tenemos un triángulo de no-cero si y sólo si las longitudes de las varillas, decir $a<b<c$, cumplen la estricta desigualdad de triángulo $a+b>c$. Puede ser más fácil el uso de este en la forma $a>c-b$ que puede ser interpretado como una declaración de que el menor elegido barra debe ser mayor que la longitud de la brecha entre las dos más largas.
• La varilla de longitud uno nunca puede ser utilizado debido a que $a=1$ hace imposible la satisfacción de las desigualdades en la viñeta anterior. Simplemente podemos pretender que la varilla de longitud uno no es parte del juego.
• Al $N=7$ extracción de la triple $\{3,5,7\}$ deja que el otro jugador con las barras de longitudes $\{2,4,6\}$ y legal no se mueve. Esta posición es una victoria para el primer jugador.
• Al $N=8$ extracción de la triple $\{4,6,7\}$ hojas del mismo modo que el segundo jugador con una tarea imposible. La colección de longitudes $\{2,3,5,8\}$ (apenas) demasiado tiempo brechas para el segundo jugador para utilizar cualquiera de las $2$ o $3$ en el papel de $a$. Esta es también una victoria para el primer jugador.
• Por otra parte, cuando $N=9$ el juego se juega de manera diferente. Después de quitar el triple de barras utilizado por el primer jugador, cinco barras de longitudes $2\le x_1<x_2<x_3<x_4<x_5\le9$ quedan. Aquí $x_2\ge3$. Debido a $x_3\ge4$ $x_5\le9$ tenemos $x_3+2x_2>x_5$. Esto significa que cualquiera de $x_4-x_3$ o $x_5-x_4$ debe ser menor que $x_2$. Por lo tanto, el segundo jugador puede elegir cualquiera de las barras de longitudes $\{x_2,x_3,x_4\}$ o de las barras de longitudes $\{x_2,x_4,x_5\}$. Después de haber eliminado a los barras, sólo quedan dos, así que el segundo jugador gana en este caso.

Pero, ¿qué ocurre en el caso general?

Answer 1

Este es un nim-como imparcial juego, por lo que cada posición tiene un nim-valor asociado con él. Yo escribí un pequeño programa para calcular el nim-valores, y los valores de las posiciones de partida son:

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

El juego es por lo tanto una victoria para el segundo jugador al$N$$9, 14, 15, 20, 21, 26, 27$, y una victoria para el primer jugador para el resto de los valores con $4 \le N \le 28$.

Tal vez el patrón de ceros continúa y es el segundo jugador gana por cada $N\ge9$$N \equiv 2,3 \mod 6$.

La integridad, aquí está el código de c# he utilizado:

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