Skip to main content
OlympiadHQ

Browse · MathNet

Print

Open Contests

Estonia counting and probability

Problem

The numbers 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 and the smallest possible number is . After the second step the largest possible number is and hence the number left on the blackboard in the end cannot be larger than .

The number can be left on the blackboard, for example when in the beginning the numbers are written in the order . Then after the first step there are the numbers , and after the second step the numbers . On each following step the number of zeroes decreases by one and in the end only the number remains.
Final answer
2010

Techniques

Invariants / monovariants