Ingrid and Erik are playing a game. For a given odd prime $p$, the numbers $1, 2, 3, ..., p-1$ are written on a blackboard. The players take turns making moves with Ingrid starting. A move consists of one of the players crossing out a number on the board that has not yet been crossed out. If the product of all currently crossed out numbers is $1 \pmod p$ after the move, the player whose move it was receives one point, otherwise, zero points are awarded. The game ends after all numbers have been crossed out.
The player who has received the most points by the end of the game wins. If both players have the same score, the game ends in a draw. For each $p$, determine which player (if any) has a winning strategy
This problem was proposed by Blastoor. Ingrid and Erik throughout the solution is replaced with Filips and Maris respectively.
For $p=3,5$, Filips wins. For $p=7$, the game ends in a draw. For all $p>7$, Maris wins.
Notice that a move is equivalent to multiplying the previous product by the newly chosen number. Additionally, as the given numbers are all residues$\pmod{p}$, we can use any complete residue set for our proof.
Case: $p>7$ $-$ Maris wins.
Proof: In this case, we will prove that Maris has a strategy that will give him at least $\Big\lceil \frac{p-5}{4} \Big\rceil$ points while limiting Filips's points to at most $1$. It is easy to see that for all primes $p>7$, this gives more points to Maris.
To achieve this, Maris can pair up the numbers in unordered pairs $(a,-b)$, where $b$ is the multiplicative inverse of $a\pmod{p}$, with one exception if $p=4k+1$. Then, the product of every such pair of numbers is $a\cdot(-b) \equiv -(ab) \equiv -1 \pmod{p}.$
To prove that this pairing exists, it is well-known that every residue$\pmod{p}$ has a unique multiplicative inverse. Therefore, if we take the negative of these multiplicative inverses, it is clear that every residue will still be paired up with a residue and these residues will be unique (explicit proof is identical to the proof of the uniqueness of multiplicative inverses).
As every residue is paired up with one unique residue, and for every residue $a$ that is paired up with $-b \pmod{p}$, residue's $-b$ negative multiplicative inverse is $a$, it can be concluded that every residue appears exactly once in the pairing and all of these pairs are disjoint. The only exception to this statement are residues that are paired up with themselves, in other words, residues $c$ that satisfy $c^2\equiv -1 \pmod{p}$.
However, it is well-known by Euler's criterion that $x^2\equiv -1 \pmod{p}$ has solutions only if $p=4k+1$. Moreover, by Lagrange's theorem $x^2\equiv -1 \pmod{p}$ has at most $2$ solutions. If there is a solution $c$, then clearly $-c$ is a solution as well, and the solutions are different as $2c \not\equiv 0 \pmod{p}$. Then in the case $p=4k+1$ we make one exception of choosing the pair $(c, -c)$, where $c^2 \equiv -1 \pmod{p}$. We can notice that the product of this pair is $c\cdot(-c)\equiv -c^2 \equiv 1 \pmod{p}.$
Now, as the pairing includes every residue$\pmod{p}$ and the $\frac{p-1}{2}$ pairs are disjoint, Maris can play symmetric with respect to the pairs. Notice that after every Maris's move the product will be either $1$ or $-1 \pmod{p}$. Additionally, as the product of every pair of numbers is $-1$ (with one exception for $p=4k+1$), the product of all crossed out numbers will be alternating between $1$ and $-1$ depending on the result after the previous Maris's move. This clearly gives Maris $\frac{p-3}{4}$ points if $p=4k+3$ and at least $\frac{p-5}{4}$ if $p=4k+1$ (the one exception of $(c, -c)$ might get the result stuck on $-1$ for one extra move).
As for Filips, he can gain a point only once if Maris follows the strategy. Suppose the product at the start of the game is $1$. Because the product will be $1$ or $-1$ after each Maris's move, Filips can only pick $1$ or $-1$ in such situation to make the product $1 \pmod{p}$. However, as $1\cdot(-1)\equiv -1 \pmod{p}$, numbers $1$ and $p-1$ will be paired up and Maris will immediately follow with the other one, leaving Filips with no chances of getting points later.
Case: $p=3,5$ $-$ Filips wins.
Proof: If $p=3$, then Filips picks $1$ in his first move, getting a point and leaving Maris with picking $2$, which makes the product $-1 \pmod{3}$ and gives zero points. Filips wins $1-0$.
If $p=5$, then Filips picks $1$ in his first move, which gives him one point. Then Maris can follow up by picking:
$4$, which makes the product $-1 \pmod{5}$ and gives him zero points. Then Filips can pick $2$, leaving Maris with $3$, and as $2\cdot 3 \equiv 1\pmod{5}$, the following move gives zero points to both of them, making Filips win $1-0$.
$2$ or $3$, which makes the product either $2$ or $3 \pmod{5}$. Then Filips can pick $3$ or $2$, respectively, to make the product $1 \pmod{5}$ after his move, getting another point and leaving Maris with picking $4$, which makes the product $-1 \pmod{5}$ and gives zero points. Filips wins $2-0.$
Case: $p=7$ $-$ draw.
Proof: In this case, it is sufficient to prove that both players have a strategy that guarantees at least as many points as their opponent's.
For Maris, he can follow the strategy for case $p>7$, as that would give him $\frac{p-3}{4}=1$ point and limit Filips's points to at most $1$. So Maris can guarantee not losing.
For Filips, he picks $1$ in the first move, which gives him one point. Then Maris can follow up by picking:
$6$, which makes the product $-1 \pmod{7}$ and gives him zero points. Then Filips can pick $2$. If Maris picks either $3$ or $5$, the product after his move won't be $1\pmod{7}$, leaving him with zero points and only one other chance to get a point, which guarantees at least a draw for Filips.
If Maris picks $4$, the product will be $1 \pmod{7}$, giving Maris one point. However, as the only numbers left will be $3$ and $5$, it is clear that after Maris's last move the product will be $-1\pmod{7}$, guaranteeing a draw for Filips.
$2,3,4$ or $5$, which does not make the product $1\pmod{7}$, giving Maris zero points. Then Filips can choose the multiplicative inverse of Maris's choice ($2\cdot4 \equiv 3\cdot 5\equiv 1 \pmod{7}$), giving Filips another point and leaving Maris with only two chances to get a point, which guarantees at least a draw.
Because both players can guarantee at least a draw, it is clear that no player can win.
This problem was indeed proposed by me.
Interestingly, it raised quite a big discussion about it being NT or combinatorics, although I myself prefer to label it as more number theoretical due to the use of quadratic residues and modulo inverses.
Well, by the existence of primitive roots, the problem immediately transform into:
We are given $0,1,2,\dots,p-2$ and we get a point whenever the sum is divisible by $p-1$.
This not only drastically simplifies all the discussion of quadratic residues etc., but also is very natural because in this version we can replace $p-1$ by an arbitrary even number.