1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Unless I don't understand something, the list 1,2,3 can have 2 and 3 erased and replaced with 1. Then 1 and 1 are erased to give 0. This would be a counterexample to your claim $n$ must be a multiple of 4. $\endgroup$ – Laars Helenius Jun 5 '16 at 2:14
  • $\begingroup$ Yes you are correct. I realize my mistake now. Thank you. $\endgroup$ – Gayatri Jun 5 '16 at 3:41
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Pair the numbers $(2,3)$, $(4,5)$ etc. to get $(n+1)/2$ ones or the numbers $(1,2)$, $(3,4)$ etc. to get $n/2$ ones. If $(n+1)/2$ or $n/2$ is an even natural number, you can thus get zero. $\endgroup$ – Aravind Jun 5 '16 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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