Juego para matemáticos sobre diferenciación de polinomios y restas en sus coeficientes.

Question

Estoy en un foro de rompecabezas francés y uno de nosotros preguntó este rompecabezas Juego de polinomas . Estamos teniendo algunas dificultades para resolverlo en el primer caso. Y no hemos empezado a pensar en la generalización, pero tenemos curiosidad, así que si nos pueden ayudar, ¡nos alegraremos! :)

El juego es simple, hay dos jugadores, y un polinomio $$P(x)=\sum_{k=0}^{n}a_k\cdot x^k$$

Turno tras turno juegan, y sólo pueden hacer una de dos cosas diferentes:

Tomar su derivada o restar un entero $u$ a partir de uno de los coeficientes $a_k$ con $0<u\le a_k$ . El primero que obtenga $0$ gana el partido.

¿Qué polinomios de grado dos pierden con una estrategia óptima? ¿Se puede generalizar con un grado $n$ ¿polinomio?

Gracias de antemano.

Answer 1

Algunas reflexiones sobre el caso cuadrático:

Observe en primer lugar que la opción derivada sólo es útil una vez (para un polinomio de 2º grado): Después de eso, el polinomio es lineal, y tomar la derivada de nuevo es simplemente entregar la victoria a su oponente, que puede entonces eliminar todos los coeficientes restantes. Así que una vez que la derivada ha sido tomada, el resto del juego procede por la estrategia normal de Nim. Como sólo quedan dos coeficientes, si no son iguales, el jugador 1 (es decir, el jugador actual en este punto) reduce el mayor para que lo sean. Al jugador 2 no le queda más remedio que volver a hacerlos desiguales, patrón que continúa hasta que el jugador 2 se ve obligado a hacer que uno de los coeficientes sea 0, y el jugador 1 puede vaciar el otro para ganar.

Pero esto plantea una dificultad para el jugador que toma la derivada. Sería el jugador 2 en el escenario anterior. Así que el único momento en que tiene sentido tomar la derivada es cuando $2a_2 = a_1$ . Cuando se da esa condición, tomar derivados es una estrategia ganadora. Otra posición ganadora es tener $a_1 = a_0$ con $a_2$ distinto de cero, ya que entonces se puede eliminar $a_2$ y deja a tu oponente con la misma posición perdedora descrita anteriormente. (Teniendo $a_2$ igual a uno de los otros coeficientes -otra posición ganadora en Nim- no lo es aquí, ya que tu oponente puede usar la opción derivada para salirse de la trampa).

Por lo tanto, al principio de la partida, la estrategia tiene que ser evitar dejar a tu oponente con $2a_2 = a_1$ o con $a_1 = a_0$ .

Edita: Algunas reflexiones adicionales sobre el juego cuadrático.

Si la derivada no se toma nunca, evidentemente hay que seguir la estrategia habitual de Nim. Llamar a un jugador "en control" si ese jugador tiene una posición Nim ganadora. Defina también $\xi(n)$ sea la menor potencia de $2$ que sea estrictamente mayor que $n$ . En Nim de 3 pilotes, si el pilote mayor es de al menos $\xi$ del XOR de los otros dos montones, entonces el jugador sólo tendrá una opción de movimiento para mantener el control. Pero si el montón más grande es más pequeño, entonces habrá múltiples opciones.

Cuando se permite tomar la derivada, se debe seguir la estrategia normal de Nim, pero evitando los casos en los que $2a_2 = a_1$ . Cuando se tiene más de una opción, creo que como mucho una de ellas resultaría en $2a_2=a_1$ (no lo he confirmado), dejándote libertad para elegir la otra. Así que el único impacto es cuando se fuerza el movimiento Nim. Es decir, cuando $a_1 \operatorname{xor} a_0 = {a_1\over 2}$ y $a_2 \ge \xi({a_1\over 2})$ o $a_2 \operatorname{xor} a_0 = 2a_2$ y $a_1 \ge \xi(2a_2)$ . El jugador 2 ganará estas posiciones si sigue la estrategia Nim, como lo hará en cualquier posición que se reduzca a una de éstas a medida que avance la partida. En esas posiciones, sin embargo, a menudo será posible entregar el control al jugador 2 de tal manera que se enfrente al mismo dilema, por lo que esto no garantiza automáticamente que estas posiciones sean ganadas por el jugador 2.

Answer 2

Esto no es una respuesta, sino un largo comentario: parece muy difícil encontrar patrones salvo en los casos más sencillos (por ejemplo, cuando el polinomio es lineal).

Los números que aparecen a continuación son valores Nim; los $i,j$ -ésima entrada es el valor del polinomio $i + jx + 8x^2$ para $0 \leq i,j \leq 40$ . (He elegido $8$ arbitrariamente como coeficiente para $x^2$ .) En otras palabras, se trata de un corte en la capa $8$ de un $3$ -de valores Nim para polinomios cuadráticos.

 8  9 10  7 11 12  3  4  0  1  2  5  6 16 17 19 13 22 14 15 23 24 26 18 27 20 21 31 32 25 33 28 29 37 30 39 40 34 36 35 44
 7 10  8  9  6 11  2  3  1  0  4 17  5 19 18 12 20 14 13 16 15 27 28 26 29 30 23 21 22 24 34 25 36 35 38 31 33 32 43 42 46
 9  8 11  6 10  3 13  1  2  4  0  7 16  5 20 17 12 21 15 14 24 25 18 19 28 22 30 23 27 26 35 36 38 31 29 40 32 33 34 43 37
 6  7  9  8 12  5 10  0  3  2  1  4 17 18 19 11 21 13 23 24 14 15 16 27 20 28 22 33 25 30 26 34 37 29 35 41 31 42 32 38 36
11 12 13  1  2  9  7 10  5  3  6  0  4  8 21 14 15 20 22 25 26 16 17 23 18 19 24 29 28 33 36 27 39 30 34 42 41 31 35 44 32
10  5  2  3  7  1  8  9  4  6 11 18  0 12 22 15 16 17 20 13 25 14 27 28 24 21 19 34 23 36 32 31 26 41 40 29 30 35 42 45 33
 2  4  1 10  0  8  9  7 11 13  5  3 14  6 16 18 19 12 17 26 27 28 15 20 21 25 29 24 30 22 23 32 31 33 36 34 35 38 39 37 40
 1  3  0  2  4  7  5  8 10 14  9 11 12 13  6 23 18 15 16 19 20 17 22 21 25 27 26 30 29 31 28 24 32 40 33 36 38 43 44 46 34
 0  1  4 11  9  2  6  5  7  8 12 10  3 14 13 16 17 18 25 22 19 20 21 15 23 24 27 26 34 28 30 35 33 36 31 32 39 37 29 40 38
 3  0  5  4  1  6 11 12  9 10  7  8 13 15  2 24 14 16 18 17 21 19 23 25 22 26 28 27 20 29 31 30 34 32 37 33 36 39 38 41 42
 4  2  3  0  5 15  1  6  8  7 10  9 11 17 12 13 24 19 21 18 16 22 14 29 26 23 25 28 31 27 20 33 30 34 43 35 37 36 41 39 48
 5  6  7 17  3  0  4  2 12  9  8 13 10 11 14 20 23  1 19 21 18 30 24 16 15 31 33 22 26 32 27 29 28 38 44 37 25 40 46 34 35
18 19  6  5 17  4  0 20 13 11 14 12  8  7  9 10 22  3  1  2 31 21 25 24 16 15 35 38 33 34 29 39 27 28 23 30 26 41 37 36 43
19 18 16 15  8 21 20 22 14 12  3 23  9  4 10 25  1  0 11  5  2  6  7 13 17 33 31 32 24 37 38 40 35 27 39 43 28 29 47 26 30
20 21 12 22 15 13 16 17  6 18 24 14  2  1  5  8  7  9  4  0  3 23 19 10 11 29 32 25 35 40 37 41 43 39 42 28 34 46 26 27 45
21 11 19 12 16 17 14 23 18  5 15  1 20  0  7  9  6 10  3  4 13  2 31 22 30  8 41 39 40 43 24 37 44 42 32 38 45 27 25 28 26
22 13 20 18 14 10 15 19 16 17 26 21  1  2 11  5  8  6  9 12  7  0  3  4 33 37 39 40 41 23 45 42 46 43 47 24 44 25 30 48 28
12 22 14 13 23 16 18 11 15 19 17  2 21 10  0  6  9  4  8 20  1 26 29  3  5  7 38 36 42 35 46 47 24 48 27 25 43 44 33 31 39
13 14 22 16 25 19 17 15 26 20 18 32 30 21  1  0  2  7 10  6  9  5  4 12  3 34  8 35 37 41 11 23 47 49 24 44 27 45 28 29 52
14 15 17 24 13 18 21 27 19 23 20 16 22  9 28  3 11  5  6  7 10  4  8  0 32  1  2 41 36 38 12 44 48 25 49 26 42 50 31 33 29
16 26 15 25 24 14 19 21 17 28 13 20 23 22  3  2  4 11  0  8 12  7  6  9 10  5  1 18 39 42 40 38 41 50 52 45 47 48 55 49 27
17 16 25 27 18 23 24 14 22 15 19 26 28 20  8  4  3 29  2 10  5  9 13  6  0 11 12  1 21  7 39 45 42 44 41 52 53 47 40 30 31
27 28 29 26 30 31 23 16 20 24 21 15 19 25 36  7  5 32 33  1  0  8 10 11  9 12  4  2  3  6 17 18 22 51 13 14 52 53 45 50 41
28 20 26 19 29 30 31 18 25 16 22 24 15 27 23 21 36  8  7  3  4 12  9  5  6 10 11  0  1 14  2 17 45 13 50 48 46 49 56 57 47
29 30 21 31 20 26 22 24 23 25 16 27 32 28 15 36 10 37 35 33  6  3  2  7  8  9 13 11  0  1  5  4 12 17 19 18 14 51 57 47 49
30 31 32 20 21 24 25 28 33 26 27 29 18 23 37 22 38 40 12 34 17 13  1 14  7 16 10  5  6  0  4  2  3  9  8 11 19 52 51 15 58
31 32 33 21 22 28 27 25 30 29 35 37 24 26 40 34 41 23 42 36 43  1  0  2 12  6  3  7  8  9 10  5  4 14 11 13 20 19 50 16 15
23 33 34 32 31 22 26 30 29 21 25 28 27 24 38 41 35 42 43 37 36 18  5  1  2  3  6  9  7 10  8  0 11  4 12 15 48 13 19 14 16
24 23 35 33 34 25 28 29 27 30 31 38 26 32 39 40 44 36 41 43 11 42 20  8  1  4  0 10  5 12  6  7  9  2  3 17 13 14 15 21 22
25 24 23 29 26 33 36 32 31 27 28 19 34 30 35 38 37 39 46 44 22 11 41 17  4  0  7  8  9 15 13 10  6  1  5  2  3 12 14 51 21
26 25 24 23 27 29 30 33 28 31 32 22 35 34 41 37 40 38 36 11 45 39 43 44 19  2 15  3 12 13  7 14  8 10  4  0  5  1  6  9 17
36 27 28 37 38 39 29 26 24 32 33 30 25 31 34 35 43 44 47 23 49 46 40 42 41 18  5 12 10  2  0  9 13  8 14  4  1  6  3  7 11
37 29 27 30 28 35 38 31 32 33 34 36 40 39 26 43 42 24 44 48 50 47 12 41 45 17 14  4  2  3  9  6 10  7 15  5 11  0  1  8 18
38 37 30 28 32 27 34 36 35 41 42 25 31 29 33 39 45 26 24 40 46 49 51 43 44 13  9  6 14  4  1  8  5 12  7 16 10 11  0  2  3
39 40 41 42 36 34 32 37 38 35 30 31 33 44 29 28 46 43 26 50 51 52 53 54 14 48 18 20  4  5  3  1  0 11  9  7  8 10 12 13  2
32 41 31 39 40 43 33 35 34 36 37 44 38 46 42 29 30 45 27 51 28 53 50 52 54 47 20 14 19  8 15 13  1 16  6  9  7  5 11  0  4
33 42 43 34 44 32 37 40 36 39 29 35 41 38 25 31 47 30 48 27 52 51 46 45 13 14 53 19 11 21 22  3  7  5  2 10  9  8 16 12  0
34 35 42 43 33 41 40 38 37 44 36 39 29 49 24 30 25 31 32 45 53 54 55 56 46 57 16 13 18 11 19 20  2  0  1  3  6  9  7  4  8
43 34 44 35 45 46 47 39 41 37 38 40 36 42 27 26 33 25 50 31 32 55 30 57 48 51 17 15 13 49 14 11 16  3  0  8 12 18  4 10  5
35 36 45 44 37 47 39 34 40 38 41 42 43 48 30 27 26 33 28 46 29 32 49 31 50 52 51 17 15 20 16 12 18  6 21  1 22  3  5 19  9
45 46 36 38 35 37 42 43 39 34 40 41 47 33 31 32 27 48 49 28 44 29 59 30 51 50 57 52 16 17 21 15 23 19 10  6  0  2  8 11 12

En $\mathcal P$ -posiciones (es decir, posiciones perdedoras) corren en tramos diagonales, pero a diferencia del Nim básico, no siguen un patrón regular (al menos no dentro de este rango; tal vez lo hagan más adelante). Aquí está la misma tabla, pero sólo mostrando la ubicación de las $\mathcal P$ -posiciones:

                0                                                                 
                  0                                                               
                    0                                                             
              0                                                                   
                      0                                                           
                        0                                                         
        0                                                                         
    0                                                                             
0                                                                                 
  0                                                                               
      0                                                                           
          0                                                                       
            0                                                                     
                                  0                                               
                                      0                                           
                          0                                                       
                                          0                                       
                            0                                                     
                              0                                                   
                                              0                                   
                                    0                                             
                                                0                                 
                                        0                                         
                                                      0                           
                                                        0                         
                                                          0                       
                                            0                                     
                                                              0                   
                                                    0                             
                                                  0                               
                                                                      0           
                                                            0                     
                                                                          0       
                                                                            0     
                                                                0                 
                                                                              0   
                                                                                0 
                                                                  0               
                                                                    0             

                                                                        0         

Este comportamiento es esencialmente el mismo para cualquier rebanada del cubo, y realmente no veo ninguna fórmula que lo prediga con exactitud.