1
$\begingroup$

I had come across a problem, where 2 people play a game where think of a number n, and turn by turn subtract a number $p$ from $n$ where $p$ is a prime and is $p < n$ and 1 is taken as prime here. Now tell the person that wins for a given $n$. It can be seen by making cases that for any $n$ that satisfies the condition , $n\equiv 1 \pmod{4} $ the first player that subtracts will lose and for all other $n$ the first player wins where both players will play optimally.The losing postion is when the current player cannot subtract any p from n.

The player that has no $p$ to subtract loses.

I just want a mathematical explanation or proof for this result of possible.

  • 0
    The player that has no $p$ to subtract loses. Added to the question2012-12-25

1 Answers 1

1

I claim that for all $m\geq0$ the positions $4m+1$ are losing positions, while the positions $4m+2$, $4m+3$, $4m+4$ are winning positions.

It is easily checked that this is true for $m=0$.

Fix an $m_0>0$ and assume the claim to be true for $0\leq m< m_0$. We now have to look at the positions $4m_0+1$, $4m_0+2$, $4m_0+3$, $4m_0+4$ in turn.

$4m_0+1$ would be a winning position if by subtracting $p$ from $4m_0+1$ we could reach a smaller losing position $4m+1$. Since $(4m_0+1)-(4m+1)$ is divisible by $4$ this is impossible. It follows that $4m_0+1$ is a losing position. but then the other three are winning positions, as one can reach the losing position $4m_0+1$ from each of these by subtracting $1$, $2$, or $3$.