Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
You haven't defined the game completely. Who wins the game when it is played this way? –  Thomas Andrews Dec 25 '12 at 14:22
    
The player that has no $p$ to subtract loses. Added to the question –  Mod Dec 25 '12 at 14:25

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.