Let $p$ be an odd prime number. Ana and Ben are playing a game with alternate moves as follows: in each move, the player which has the turn choose a number, which was not choosen before by any of the player, from the set $\{1,2,...,2p-3,2p-2\}$. This process continues until no number is left. After the end of the process, each player create the number by taking the product of the choosen numbers and then add 1. We say a player wins if the number that did create is divisible by $p$, while the number that did create the opponent it is not divisible by $p$, otherwise we say the game end in a draw. Ana start first move. Does it exist a strategy for any of the player to win the game? Proposed by Dorlir Ahmeti, Kosovo
Problem
Source: Kosovo TST 2020 Problem 2
Tags: number theory, prime numbers
09.02.2020 01:30
Note that whoever pick $p$ does not win for sure. Since, we have an even no of numbers on the board $A$ can simply not pick $p$ in all her turns. So $B$ does not win for sure. Here is a strat for $A$. She first picks $p-1$. Consider $(1,p+1)$, ..., $(p-2,2p-2)$, $p$. Note that $A$ has to pick $p-2$ more numbers. That's easy. She can for sure pick one from each parenthesis pair. Indeed, if $B$ picks one from the pair $(i,p+i)$ then she can pick the other one unless she picked that already in which case she picks in a random untouched by her pair or the game ends. If $B$ pick $p$ she picks on an untouched pair. This way she will end up with a produc equivalent to $(p-1)! \mod p$. Hence, done by $Wilson's$. @below. I mean he cannot win. I will correct sorry
09.02.2020 01:46
vwu wrote: Note that whoever pick $p$ loses for sure. Since, we have an even no of numbers on the board $A$ can simply not pick $p$ in all her turns. So $B$ loses for sure. This statement is not true since if one can't win it doesn't mean that it will lose since you still left the draw chances. You can say that only $A$ can win if exist such strategy. And then the other part when you describe the strategy will complete the solution as it should.
30.03.2021 18:30
The answer is that Ana has the winning strategy. Obviously no one wants to pick out $p$ as one of their numbers. So we claim that Ben will always be forced to choose $p$. So now let Ana and Ben always choose a number that isn't $\equiv 0 \pmod{p}$. Since there are $2p-3$ numbers which aren't divisible by $p$, we say that $x+y=2p-3$. Where $x$ is the number of moves Ana has made and $y$ the number of moves Ben made. Since $2p-3 \equiv 1 \pmod{2}$, this implies that Ana will erase the last number that isn't divisible by $p$. Thus Ben will be forced to choose $p$. Now let's devise a strategy for Ana. Let's say that Ana's number if $x+1$, where $x$ is the product of the chosen numbers. First let's say that Ana chooses $p-1$ as her first number, and after each move she chooses the same number with the same remainder that Ben has chosen in the last move. Thus we see that: $$x+1 \equiv (p-1)(p-2)\dots 3.2.1 + 1\equiv (p-1)!+1 \equiv -1+1 \equiv 0 \pmod{p}$$thus Ana always wins.
24.03.2024 21:29
I claim that Ana has winning startegy. The Wilson theorem can helps us. $1 \equiv p+1 \equiv 1(\text{mod p})$ $2 \equiv p+2 \equiv 2(\text{mod p})$ . . . $p-1 \equiv 2p-2 \equiv p-1(\text{mod p})$ So it doesn't matter that ana choses $j$ or $p+j$ and ben has to stop her but it never been achievable because every player should choose $p-1$ number. If $j$ selected by ben then ana can select $p+j$ By, Wilson theorem $x1*.....*x_{p-1} +1 \equiv 0(\text{mod p})$