Maths Olympiad Prep

Library / /106 of 189

Combinatorics Difficulty 5.9 AIME, harder Prove it Ukraine

Andrii chooses a sign in front of each number in the expression ±1±2±3±±2018\pm 1 \pm 2 \pm 3 \pm \dots \pm 2018. How many different positive values can Andrii obtain as a result of the computed expression?

Solution

Clearly, the expression cannot equal 00, since it contains 10091009 odd numbers. We want to show that the expression can be any odd number between 11 and 1+2+3++20181+2+3+\dots+2018.

Take some configuration. Find the first from the left consecutive numbers with signs "-" and "+". The switching of these signs decreases the value of the expression by 22. We will start with the following expression: "+1+2+3++2018""+1+2+3+\dots+2018" and will change it to expression "1+2+3++2018""-1+2+3+\dots+2018" that is less by 22 as described above. By following the described algorithm, we will obtain all the numbers decreased by 22.

When we get the expression

+1 - 2 - 3 - ... - 2018, for which the algorithm doesn't work, the last step will be to switch to the smallest expression -1 - 2 - 3 - ... - 2018.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.