Anton and Britta play a game with the set $M=\left \{ 1,2,\dots,n-1 \right \}$ where $n \geq 5$ is an odd integer. In each step Anton removes a number from $M$ and puts it in his set $A$, and Britta removes a number from $M$ and puts it in her set $B$ (both $A$ and $B$ are empty to begin with). When $M$ is empty, Anton picks two distinct numbers $x_1, x_2$ from $A$ and shows them to Britta. Britta then picks two distinct numbers $y_1, y_2$ from $B$. Britta wins if $(x_1x_2(x_1-y_1)(x_2-y_2))^{\frac{n-1}{2}}\equiv 1\mod n$ otherwise Anton wins. Find all $n$ for which Britta has a winning strategy.
Problem
Source: 2022 Nordic Mathematical Olmpiad
Tags: combinatorial game theory, number theory
16.04.2022 04:07
Besides the problem,why is my LaTeX red?
16.04.2022 05:58
MathLover_ZJ wrote: Anton and Britta play a game with the set $M=\left \{ 1,2,\dots,n-1 \right \}$ where $n \geq 5$ is an odd integer. In each step Anton removes a number from $M$ and puts it in his set $A$, and Britta removes a number from $M$ and puts it in her set $B$ (both $A$ and $B$ are empty to begin with). When $M$ is empty, Anton picks two distinct numbers $x_1, x_2$ from $A$ and shows them to Britta. Britta then picks two distinct numbers $y_1, y_2$ from $B$. Britta wins if $(x_1x_2(x_1-y_1)(x_2-y_2)) ^{\frac{n-1}{2}} \equiv 1\mod n$ otherwise Anton wins. Find all $n$ for which Britta has a winning strategy.
16.04.2022 06:07
MathLover_ZJ wrote: Besides the problem,why is my LaTeX red? It”s because what you want to be the minus sign is not minus sign, it is a dash. I think you copy the problem from something then paste it here and the program think that the minus sign is a dash.
16.04.2022 10:06
Let the palyers be $A$(Anton) and $B$(Britta). If $n$ is not prime number, then at his first move, $A$ chooses prime divisor $q$ of $n$ and at the end he chooses $x_1=q$ and wins. If $n=p$, where $p$ is prime, then $B$ follows this strategy: If $A$ chooses number $t$ at his move, then $B$ choose $|p-t|$ after $A$'s this move. Since $p-1$ is odd and $A$ starts game, $B$ can follow this startegy until end. At the end, when $A$ picks $x_1,x_2$, $B$ picks $|p-x_1|,|p-x_2|$. So $(x_1x_2(x_1-y_1)(x_2-y_2))^{\frac{p-1}{2}}\equiv (2x_1x_2)^{p-1}=1 \pmod p$. So $B$ wins only when $n$ is prime.