Let $n$ be an integer greater than 0. The numbers $1, 2, 3, \ldots, n$ are written on a blackboard. We decide to erase from the blackboard any two numbers, and replace them with their nonnegative difference. After this is done several times, a single number remains on the blackboard. For which values of $n$ can this number equal 0?
Trying on small cases, I think that the last number that remains can be 0 only when n is a multiple of 4. I tried using parity to prove that the last number that remains and n are of the same parity. Can someone help me out with it?
Best Answer
Key Observation
Parity of the sum of the numbers written on the board stays unchanged. Because, at each step you are turning $x,y$ into $|x-y|$ and $x+y\equiv x-y\equiv y-x\pmod2$ .
Necessary condition
In order to have the last number to be $0$, you need the sum of the numbers written in the beginning to be even. So, we want $$1+2+\ldots+n=\frac{n(n+1)}2$$ to be even. Notice, this happens iff $n\equiv 0,3\pmod4$.
To see this condition is sufficient, try to play with the numbers to get $0$ at the end. You said you did it for $4$. For $3$, $$1,(2,3)\mapsto1,(1)\mapsto 0$$ works.
Suppose you can get $0$ for $n$. Then, you can get $0$ for $n+4$ by repeating the same steps for the first $n$ numbers to get $$0,n+1,n+2,n+3,n+4$$ and then making $$n+4,n+2\mapsto 2\qquad n+3,n+1\mapsto 2\qquad 2,2\mapsto 0\qquad 0,0\mapsto 0$$
So, by induction, you can do it for any $n\equiv 0,3\pmod4$