Skip to main content
OlympiadHQ

Browse · MathNet

Print

National Olympiad of Argentina

Argentina counting and probability

Problem

Given several integers, it is allowed to replace two of them by their nonnegative difference. The operation is repeated until only one number remains. If the initial numbers are , what can be the last number remaining?
Solution
The operation replaces and by which is even if and have the same parity and odd otherwise. So the number of odd numbers either remains unchanged or decreases by after each step. Initially is odd (), so the last number will be odd, and clearly between and . Conversely each odd number in this range can end up as the last one after a sequence of operations. Let be such a number, ; then . Separate the pair and divide the remaining numbers into pairs of consecutive integers: Apply the operation to each of these pairs to obtain ones. They can be grouped in pairs, and each of these yields a zero. The last pair gives . So we obtain and several zeros, after which it is clear that the last number will be .
Final answer
All odd integers from 1 to 2009 inclusive

Techniques

Invariants / monovariantsIntegers