Game for mathematicians about differentiation of polynomials and subtractions in their coefficients.
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.
Solution 1:
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.
Solution 2:
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.