Let $p$ be a prime number. Troy and Abed are playing a game. Troy writes a positive integer $X$ on the board, and gives a sequence $(a_n)_{n\in\mathbb{N}}$ of positive integers to Abed. Abed now makes a sequence of moves. The $n$-th move is the following: $$\text{ Replace } Y \text{ currently written on the board with either } Y + a_n \text{ or } Y \cdot a_n.$$Abed wins if at some point the number on the board is a multiple of $p$. Determine whether Abed can win, regardless of Troy’s choices, if $a) p = 10^9 + 7$; $b) p = 10^9 + 9$. Remark: Both $10^9 + 7$ and $10^9 + 9$ are prime. Proposed by Ivan Novak
Problem
Source: 9th EMC, 12th December 2020 - 20th December 2020. SENIOR league, P3.
Tags: number theory, game, prime numbers
Aryan-23
23.12.2020 01:28
Fun problem to work on ! Part a : The key observation is that $p=2 \pmod 3$. We claim that Troy can chose his sequence such that the number $y$ is always incongruent to $0,1$ mod $p$. Hence Alice can never win. Proceed by induction on the number of indices of the sequence. Its obvious that the claim holds for the base cases.Suppose after $k$ steps we have the number $y$ written on the blackboard. Working in $\mathbb F_p$, let $n=\tfrac {y}{y-1}$ be a solution to $y+n=ny$, we claim that $yn \not \equiv 0,1 \pmod p$. Then Troy can just choose $n$ as $a_{k+1}$ and win. Note that $$yn=1 \pmod p \implies \frac {y^2}{y-1} = 1 \pmod p$$$$ \iff y^2-y+1=0 \pmod p \implies y^3=1 \pmod p \stackrel {\text {orders}}{\implies} y =1 \pmod p (\rightarrow \leftarrow)$$ Hence we are done. $\square$ Part b : The key observation is that $p\equiv 1 \pmod 4$. Let $x=\tfrac {1+i}2$ be a solution to $2x^2-2x+1=0$ in $\mathbb F_p$ where $i^2=-1$. Note that $x\neq 1 \pmod p$. We claim that Troy wins again. Troy chooses $X=x$, $a_1=\tfrac {x}{x-1} $ and $a_2= \tfrac { \tfrac {x^2}{x-1} } { \tfrac {x^2}{x-1} -1 }$, we claim that the number obtained after 2 operations of Alice is the same as $x \pmod p$. To note this, we see that the second and third numbers on the blackboard after Alice's moves are $a=\tfrac {x^2}{x-1}$ and $b=\tfrac {x^4}{(x^2-x+1)(x-1)}$ respectively. We only need to check that $a\neq 1$ and $b=x$ mod p. Work in $\mathbb F_p$ henceforth. $$ \frac {x^2}{x-1} = 1 \iff x^2-x+1 =0 $$$$\iff 2x^2-2x+2=0 \iff 1=0 (\text {oops})$$ $$ \frac {x^4}{(x^2-x+1)(x-1)}= x \iff 2x^2-2x+1=0$$ Where we have used the definition of $x$. We are done. $\square$
alexiaslexia
13.01.2021 04:21
A playful (literally) problem to spend hours on. Play and experiment to win! Solution almost equal to above, so only a sketch: $\color{magenta} \rule{25cm}{3pt}$ $\color{magenta} \textbf{\text{Part a, Troy wins.}}$ Unironically hard (if you found part b first). Denote the set $Y_i$ to be the set of possible residue classes after operating for $X$ with $a_1, a_2,\ldots, a_i$. Troy are to construct a sequence with arbitrary $X \ne 0,1 \pmod p$, and \[ a_{i+1} \equiv \dfrac{a_i}{a_i-1} \pmod p, \, i \geq 0 \]with setting beforehand $a_0 = X$. This will yield $|Y_i| = 1$ with no repercussions since $a_{i+1} \ne 0$ for obvious reasons, and $a_{i+1} \ne 1$ since \[ \dfrac{{a_i}^2}{a_i-1} \equiv 1 \pmod p \Rightarrow a_i^2-a_i+1 \equiv 0 \pmod p \]which is impossible since $10^9+7 \equiv 2 \pmod 3$. So the sequence will keep going, since if $a_i \ne 0,1 \pmod p$, an $a_{i+1}$ is formable. $\color{green} \rule{25cm}{1.5pt}$ $\color{green} \textbf{\text{Part b, Troy also wins.}}$ This time $X$ won't be arbitrary, and there will be a clear pattern among the member (yes, singular) of $Y_i$; namely, the members will be 2-periodic. Let us wish to construct $x$ and $y$ so that $x \rightarrow y$ and $y \rightarrow x$. A very loose notation: $A \rightarrow B$ means if $A$ is on the board, $A+a_n = A \cdot a_n \equiv B \pmod p$. So, the term which transforms $x$ to $y$ should be $y-x$, and $y$ to $x$ be $x-y$. This means that \[ x(y-x) \equiv y \pmod p, \ y(x-y) \equiv x \pmod p \]Substracting the two equations and factoring out $x-y$, we get $x+y = 1$. Substituting $y = 1-x$, the equation(s) will now be \[ x(1-2x) \equiv 1-x \pmod p \Rightarrow (2x-1)^2+1 \equiv 0 \pmod p \]This is possible since $10^9 + 9 \equiv 1 \pmod 4$. $\blacksquare$ $\blacksquare$ $\blacksquare$
Starting from low primes, $p=2$ is instantly in Abed's favor, and also $p=3$. After a bit of experimentation, it seemed best to not let the possibilities of $X_i$ expand (my term for some element of the set $Y_i$, the set of possible numbers after the $i^{th}$ step.) Since if $X = 2$, and $a_1 = 2$, then $Y_i = \{4\}$, it would be best if $X_i$ is followed by a $2$ --- and this is certainly possible, by setting $a_2 = 3$.
For $p = 7$, however, it seemed more intricate for both Troy and Abed, as I was confused what the deal-breaker for any of the players would be. Since the best place to start was the initial term ($Y_0$ certainly has only one member, and the bigger they get, the more expansive they are), I decided to play around with $X$ in relation to $a_1$.
If $X = 2$,
\[ \begin{tabular}{c|c}
$a_1$ & $Y_1$ \\ \hline
1 & $\{2,3\}$ \\
2 & $\{4\}$ \\
3 & $\{5,6\}$ \\
4 & $\{6,1\}$ \\
5 & $\{0,3\}$ \\
6 & $\{1,5\}$ \\
\end{tabular} \]indicating that 5 is an unfavorable option, and 2 to be the only option where Troy can stall the expansion from $|Y_0|$ to $|Y_1|$. I did the same for $X = 3$, and it's hard to make a pattern out of it; except when $a_1 = 5$, $Y_1 = \{1\}$.
Then again, any move that forces $X$ to be $X$ requires $a_1 = 0$ or $1$, and that couldn't possibly be a favorable option --- they both expand the size of $Y_0$. So, the next viable option would be to force $X$ into some $t$, then somehow force $t$ back into $X$ for immediate effect. This was the heart of Part b; and had I considered the fact that
\[ \dfrac{X^2}{X-1} \ne 1 \pmod p \leftrightarrow X^2-X+1 \not\equiv 0 \pmod p \]I would've been done instantly (if $|Y_i|$ is forever $1$, regardless of periodicity, Abed is screwed for life.) Rather, I zoomed in on the periodicity analysis, because of mainly two reasons:
The nature of yes/no questions, and the fact that part (b) had a nice periodic construction;
The complement of part b's solution is when $p \equiv 3 \pmod 4$, which is known to be deal-breakers in many diophantine equations.
So an unconscious shift in mindset occured; that is proving if $p \equiv 3 \pmod 4$ then Abed has a cutting edge. While this is a very long detour, it provided grounds to question my strongly placed assumption to its core.
$\rule{25cm}{1pt}$
$\textbf{\text{Long Detour.}}$
Let the proposition that Troy has a strategy to be false. Then, there exists a group $C = Y_i$ so
\[ C \Rightarrow C+a_1 \Rightarrow C+a_1+a_2 \Rightarrow C+a_1+a_2+a_3 \Rightarrow C+a_1+a_2+a_3+a_4= C \]denoting $a_{i+1}$ by $a_1$ for simplicity. A first thing I tried was finding a specific $x \in C$ so that they will form a $0$ in some $C+a_1+\ldots+a_i$. This quickly turned downhill, as some weird terms such as
\[ x \equiv -a_1 - \dfrac{a_4}{a_2a_3} \pmod p \]can be a possibility which makes a $0$ on the final set (assuming it takes 4 operations to turn $C$ back into $C$.) The ordered multiplication and addition in that manner also creates unpredictable patterns.
$\rule{25cm}{1pt}$
My second option was to analyze the group's elements under said transformations. Since $C+a_1 = C \cdot a_1$ (why?), proceeding to the end we can easily get that
\[ \sum_{i=1}^{n} a_i \equiv 0 \pmod p, \, \prod_{i=1}^{n} a_i \equiv 1 \pmod p \]This is due to the rough analysis that $X + k = X$ for some set $X$ implies $k = 0$. However, the next difficulty was handling the equation $Xa + b = X$. Trying with small cases, assuming $0 \not\in C$, we can get that $b \not\in C$, and furthermore,
\[ b\cdot \left(\dfrac{a^n-1}{a-1}\right) \not\in C \]This may seem like an achievement, but for even $p = 5$, this doesn't function as well as I thought it would be. For example, when $C = \{1,3,4\}$, $C = aC+b$ doesn't seem to have a solution when $a = 2,3$, but they are equal when $(a,b) = (4,2)$. Analyzing $x \in C$ as $x = g^k$ where $g$ is a primitive root mod $p$ also doesn't seem to work due to the random nature of $a_i$'s additions/multiplications.
$\rule{25cm}{1pt}$
When all general approaches doesn't seem to work, now I resorted to the final stand --- that is to return to analyzing individual elements in relation to the identity $C = aC+b$. First, I considered the set $X \cdot a = X+a$, and out of all approaches, it seems that only
\[ \sum_{i=1}^{k} (x_i+a) = a \cdot \left( \sum_{i=1}^{k} x_i \right) \]and its product equivalent are promising; here $X = \{a_1,a_2,\ldots,a_k\}$. From that, we can be sure that
\[ \sum x_i = \dfrac{ka}{a-1} \]changing the initial sum from $\dfrac{ka}{a-1}$ into $\dfrac{ka^2}{a-1}$. Continuing from this, we would have to solve the equation
\[ \dfrac{ka^2}{a-1} = \dfrac{kb}{b-1} \]if we let the next term to be $b$. Here, $b = \dfrac{a^2}{a^2-a+1}$, and so the next term would be something like
\[ \dfrac{ka^4}{a^4-a^3+1} \]which isn't an expression I've ever seen in an NT problem before.
A final idea was to consider more complicated expressions --- any of the $2^n$ operations of (multiplication, addition) in the sequence $(a_1,a_2,\ldots,a_n)$ will force $C$ back to $C$. However, I couldn't comprehend why this would be useful, as that is just another way of saying (a.k.a. sugarcoats) the fact that $C_i + a_{i+1} = C_i \cdot a_{i+1}$. There, $n$ bases are available to work with, and each transformation by an $a_i$ isn't likely to connect with its $n-1$ peers.
As I looked back on it afterwards, all operations above are basically just analyzing sets based on some individual invariant, operated $n$ times. Then, a flipside of thought occured; what if the set itself is that individual invariant, and we can let $n$ to be dependent on the sequence (rather than force it to be periodic, just like in my assumptions that $C$ must eventually go back to itself in some $n$ moves.)
Trying this for $p = 7$, it seemed that all attempts of keeping $|Y_i| = 1$ will result in an eventual $X_i = 1$, rendering the attempt useless. However, trying it for larger $p \not\equiv 1 \pmod 4$, such as $p = 11$, such sequences do exist --- and what other mod to base it upon other than mod $3$? This was the final key to part (a), and I am finally done.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Final Comments: The second problem I've seen of which two distinct modular applications which are crucial: mod $3$ and mod $4$. This is similar in style with IMO 1993/3, which is already quite tricky with an unexpected Solution (though not an unexpected answer, like this problem.)