Problem 1179

Here, Abigail has too many possibilities: each time she can potentially get two different results, so if Tristan has a hope of winning, he would like that at the $n$-th turn, Abigail has only one possibility modulo $p: b_{n}$. Initially, he chooses $X=b_{0}$. Then, from $b_{n}$, to have only one possibility, he would like to choose $a_{n+1}$ such that $a_{n+1} b_{n} \equiv a_{n+1}+b_{n}(\bmod p)$, i.e., $a_{n+1} \equiv \frac{b_{n}}{1-b_{n}}(\bmod p)$. In particular, we will have $b_{n+1} \equiv \frac{b_{n}^{2}}{b_{n}-1}(\bmod p)$. It is noted that having $b_{n} \equiv 1(\bmod p)$ is a problem for Tristan.

Thus, let's give the following strategy for Tristan: Tristan chooses an $X$ that is not congruent to 0 or 1 $\bmod p$. He sets $b_{0}=X$. Then, as long as $b_{n}$ is not 1 modulo $p$, he sets $a_{n+1} \equiv \frac{b_{n}}{b_{n}-1}(\bmod p)$ and $b_{n+1} \equiv \frac{b_{n}^{2}}{b_{n}-1}(\bmod p)$. We can show by immediate induction that Abigail, after $n$ choices, will have written $b_{n}(\bmod p)$ on the board.

We can hope that for all $n, a_{n}$ is always defined and $b_{n}$ is always different from 0 and 1 modulo $p$. Note that if $b_{n} \neq 0,1(\bmod p), b_{n+1} \neq 0(\bmod p)$. Moreover, $b_{n+1} \equiv 1(\bmod p)$ is equivalent to $b_{n}^{2}-b_{n}+1 \equiv 0(\bmod p)$. This polynomial has a root modulo $p$ if and only if its discriminant, -3, is a square modulo $p$.

By quadratic reciprocity,

$$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=(-1)^{\frac{p-1}{2}}(-1)^{\frac{2(p-1)}{4}}\left(\frac{p}{3}\right)=\left(\frac{p}{3}\right)$$

In particular, this gives us the question $a$: since $p \equiv 2(\bmod 3),\left(\frac{-3}{p}\right)=-1$, so the equation $x^{2}-x+1 \equiv 0(\bmod p)$ has no solution: thus $b_{n+1}$ cannot be 1 modulo $p$, so Tristan wins.

For question $b$, unfortunately, we cannot ensure that the previous process works. One option is that $b_{n}$ quickly loops. Since $b_{n+1} \equiv b_{n}+a_{n+1} \equiv b_{n} a_{n+1}$, if $b_{n+1} \equiv b_{n}, a_{n+1} \equiv 0(\bmod p)$, so $b_{n+1} \equiv 0(\bmod p)$. The best we can hope for is to have a loop of size 2, i.e., $b_{2} \equiv b_{0}(\bmod p)$.

Now,

$$b_{2} \equiv \frac{b_{1}^{2}}{b_{1}-1} \equiv \frac{\frac{b_{0}^{4}}{\left(b_{0}-1\right)^{2}}}{\frac{b_{0}^{2}}{b_{0}-1}-1}$$

The equation (with $x \not \equiv 0(\bmod p)) x \equiv \frac{\frac{x^{4}}{(x-1)^{2}}}{\frac{x^{2}}{x-1}-1}$ is equivalent to $1 \equiv \frac{x^{3}}{x^{2}(x-1)-(x-1)^{2}} \equiv$ $\frac{x^{3}}{x^{3}-2 x^{2}+2 x-1}$, and thus to $2 x^{2}-2 x+1 \equiv 0(\bmod p)$, and this makes sense provided that $x$ is different from 0 and 1 modulo $x$ and $\frac{x^{2}}{x-1}$ is different from 0 or 1 modulo $p$.

The equation $2 x^{2}-2 x+1 \equiv 0(\bmod p)$ is a quadratic equation, which has a solution modulo $p$ if and only if its discriminant, which is -4, is a square modulo $p$. -4 is a square if and only if -1 is. In $b$, since $p \equiv 1(\bmod 4)$, -1 is indeed a square: there exists a root modulo $p$ of $2 x^{2}-2 x+1$, which we will denote by $y$. 0 and 1 not being roots, $y$ is different from 0 or 1. Moreover, we cannot have $\frac{y^{2}}{y-1} \equiv 0$ or 1 modulo $p$: for 0, this is clear, for 1, this would imply having $y^{2}-y \equiv 1$, so $2 y^{2}-2 x \equiv 2$. But $2 y^{2}-2 y \equiv-1$, and $2 \not \equiv-1(\bmod p)$. Thus, if we take $X=y$, we obtain by immediate induction that $b_{n} \equiv b_{0}$ if $n$ is even, $b_{1}$ if $n$ is odd, and is different from 0 and 1 for all $n \geqslant 0$. Thus Abigail cannot win: in both cases, Tristan wins.