A little boy wrote the numbers $1,2,\cdots,2011$ on a blackboard. He picks any two numbers $x,y$, erases them with a sponge and writes the number $|x-y|$. This process continues until only one number is left. Prove that the number left is even.
Problem
Source:
Tags: invariant, combinatorics proposed, combinatorics
13.03.2011 22:26
By doing this process, the parity of the sum is invariant because after each operation, the sum diminishes by twice the smaller number taken for the process. So, the initial sum is even implies that the final number(the final sum) is even as well.
13.03.2011 22:30
Let $N$ be the sums of the squares of the remaining numbers on the blackboard. Originally $N$ is even. The transformation $x,y\to |x-y|$ never affects the parity of $N$ as the difference is $2xy$ (from $x^2+y^2+\ldots$ to $x^2-2xy+y^2\ldots$). So the square of the last number is even, and so is even itself.
15.03.2011 23:37
Obel1x wrote: A little boy wrote the numbers $1,2,\cdots,2011$ on a blackboard Do you really think that a little boy can do that ?
16.03.2011 18:10
Thalesmaster wrote: Obel1x wrote: A little boy wrote the numbers $1,2,\cdots,2011$ on a blackboard Do you really think that a little boy can do that ? In a recent British MO, it said there were $2010^{2010}$ students at a camp! Sometimes maths problems neglect a sense of realism, I think
28.03.2011 17:29
The sum of the numbers on the board is invariant and originally even. The result follows directly
28.03.2011 17:35
Pascal96 wrote: The sum of the numbers on the board is invariant and originally even. The result follows directly modulo $2$
04.07.2016 14:05
Obel1x wrote: A little boy wrote the numbers $1,2,\cdots,2011$ on a blackboard. He picks any two numbers $x,y$, erases them with a sponge and writes the number $|x-y|$. This process continues until only one number is left. Prove that the number left is even. If the problem asks "What could be the last number on the board?", are all even numbers achievable?
08.08.2016 16:15
dattranquoc101201 wrote: If the problem asks "What could be the last number on the board?", are all even numbers achievable? Obviously all even numbers aren't achievable.Because the processes are finite or the sum of the numbers decrease after each operation.
30.04.2023 14:39
Let $S=1+2+3+...+2011$ $S= \frac{2011 \cdot 2012}{2} = 2011 \cdot 1006 = 2023066$, which is even Consider 3 cases: $x>y \Rightarrow S-x-y+(x-y)=S-2y$, which is even $x<y \Rightarrow S-x-y+(y-x)=S-2x$, which is even $x=y \Rightarrow S-2x+(x-x)=S-2x$, which is even Therefore the last number on the board is always even $\blacksquare$