Maths Olympiad Prep

Library / /28 of 31

Combinatorics Difficulty 6.5 National olympiad Prove it Estonia

The numbers 1,2,,20121, 2, \ldots, 2012 are written on the blackboard in some order, each of them exactly once. Between each two neighboring numbers the absolute value of their difference is written and the original numbers are erased. This is repeated until only one number is left on the blackboard. What is the largest possible number that can be left on the blackboard?

Solution

The largest number on the blackboard cannot increase on any step, because the absolute value of the difference of two nonnegative numbers cannot be greater than the maximum of these two numbers. Since in the beginning all the numbers are different and positive, after the first step the largest possible number is 20112011 and the smallest possible number is 11. After the second step the largest possible number is 20102010 and hence the number left on the blackboard in the end cannot be larger than 20102010.

The number 20102010 can be left on the blackboard, for example when in the beginning the numbers are written in the order 2012,1,2,3,,20112012, 1, 2, 3, \ldots, 2011. Then after the first step there are the numbers 2011,1,1,,12011, 1, 1, \ldots, 1, and after the second step the numbers 2010,0,0,,02010, 0, 0, \ldots, 0. On each following step the number of zeroes decreases by one and in the end only the number 20102010 remains.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.