13
$\begingroup$

I'm in a french puzzle forum and one of us asked this puzzle Game of polynoms. We are having some difficulties solving it for the first case. And we have not begun to think about the generalisation, but we are curious so if you can help us, we should be glad! :)

The game is simple, there are two players, and one polynomial $$P(x)=\sum_{k=0}^{n}a_k\cdot x^k$$

Turn after turn they play, and they can only do one of two different things:

Take its derivative or subtract an integer $u$ from one of the coefficients $a_k$ with $0<u\le a_k$. The first who obtains $0$ wins the game.

What polynomials of degree two are losing with an optimal strategy? Can you generalize with a degree $n$ polynomial?

Thank you in advance.

$\endgroup$
  • $\begingroup$ Are the coefficients $a_k$ supposed to be nonnegative integers? $\endgroup$ – Eric Wofsey Oct 25 '15 at 1:35
  • $\begingroup$ They are positive by the condition given on $u$. They would have to be integers for the game to ever have a solution instead of stalling out unsolved because all the coefficients are less than $1$. $\endgroup$ – Paul Sinclair Oct 25 '15 at 1:37
  • 3
    $\begingroup$ If it were not for the "take the derivative" option, this game would be identical to Nim. So the question becomes: how does taking the derivative upset the known strategy for Nim? $\endgroup$ – Paul Sinclair Oct 25 '15 at 1:51
  • $\begingroup$ In general, it seems that you want to be player 1 when there are an odd number of positive coefficients remaining. Let's say P1 eliminates a coefficient (differentiating can only eliminate $a_0$). If all remaining coefficients (an even number) are 1, then P1 wins. Otherwise, the next sequence of moves (under optimal play) is the game of nim where the coefficients converge to all 1's. $\endgroup$ – sai Oct 25 '15 at 1:58
  • $\begingroup$ Are the $a_k$ in the condition $0< u \leq a_k$ fixed by the original polynomial, or do they change from turn to turn? $\endgroup$ – David Hill Oct 25 '15 at 3:22
2
$\begingroup$

Some thoughts on the quadratic case:

Note first that the derivative option is only useful once (for a 2nd degree polynomial): After that, the polynomial is linear, and taking the derivative again is simply handing the win to your opponent, who can then remove all of the remaining coefficient. So once the derivative has been taken, the remainder of the game proceeds by the normal Nim strategy. Since there are only two coefficients left, if they are not equal, player 1 (i.e., the current player at this point) reduces the larger to make them so. Player 2 is left with no choice but to make them unequal again, which pattern continues until player 2 is forced to make one coefficient 0, and player 1 can empty the other one for the win.

But this brings up a difficulty for the player taking the derivative. They would be player 2 in the scenario above. So the only time it makes sense to take the derivative is when $2a_2 = a_1$. When that condition occurs, taking derivative is a winning strategy. Another winning position is to have $a_1 = a_0$ with $a_2$ non-zero, for then you can remove $a_2$ and leave your opponent with the same losing position described above. (Having $a_2$ equal to one of the other coefficients - another winning position in Nim - is not so here, as your opponent can use the derivative option to slip out of the trap.)

So at the start of the game, the strategy has to be to prevent leaving your opponent with either $2a_2 = a_1$ or with $a_1 = a_0$.

Edit: Some additional musings on the quadratic game.

If the derivative is never taken, then obviously the regular Nim strategy should be followed. Call a player "in control" if that player has a winning Nim position. Also define $\xi(n)$ to be the least power of $2$ that is strictly greater than $n$. In 3-pile Nim, if the largest pile is at least $\xi$ of the XOR of the other two piles, then the player will have only one choice of move in order to remain in control. But if the largest pile is smaller, then there will be multiple choices.

When taking the derivative is allowed, one should continue to follow the normal Nim strategy, but avoiding cases where $2a_2 = a_1$. When you have more than choice, I think that at most one of them would result in $2a_2=a_1$ (I haven't confirmed this), leaving you free to choose the other one. So the only impact is when the Nim move is forced. That is, when $a_1 \operatorname{xor} a_0 = {a_1\over 2}$ and $a_2 \ge \xi({a_1\over 2})$ or $a_2 \operatorname{xor} a_0 = 2a_2$ and $a_1 \ge \xi(2a_2)$. Player 2 will win these positions if you follow the Nim strategy, as he will for any position that reduces to one of these as the game play goes on. In those positions, though, it will often be possible instead to hand control over to player 2 in such a way that he faces the same dilemma, so this does not automatically guarantee that these positions are player 2 wins.

$\endgroup$
  • $\begingroup$ Hum, ok so we have some ideas which are the same than yours. Thank you for your answer. Have you got any ideas for a degree n polynomial? :) $\endgroup$ – ParaH2 Oct 25 '15 at 16:07
  • $\begingroup$ This wasn't offered as a full solution even for the quadratic case. Just some initial discoveries I had, which I thought I would share, in case it would aid anyone else in their own considerations. I'm not surprised that it isn't original. I'm still considering what the implications of this are on the quadratic game. $\endgroup$ – Paul Sinclair Oct 26 '15 at 16:27
1
$\begingroup$

This is not an answer but a long comment: it seems very difficult to find patterns except in the simplest of cases (e.g., where the polynomial is linear).

The numbers below are Nim values; the $i,j$-th entry is the value of the polynomial $i + jx + 8x^2$ for $0 \leq i,j \leq 40$. (I chose $8$ arbitrarily as the coefficient for $x^2$.) In other words, this is a slice at layer $8$ of a $3$-dimensional array of Nim values for quadratic polynomials.

 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

The $\mathcal P$-positions (i.e., losing positions) run in diagonal stretches, but unlike basic Nim, they don't follow a regular pattern (at least not within this range; maybe they do later). Here's the same table, but only showing the location of the $\mathcal P$-positions:

                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         

This behaviour is essentially the same for any slice of the cube, and I really don't see any formula that will predict it exactly.

$\endgroup$
  • $\begingroup$ Wow, very impressive :) $\endgroup$ – ParaH2 Oct 29 '15 at 20:42
  • $\begingroup$ @Shadock Well, I didn't do these by hand ... ;) $\endgroup$ – Théophile Oct 29 '15 at 21:15
  • $\begingroup$ Hope to you haha :) $\endgroup$ – ParaH2 Oct 29 '15 at 21:58

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.