Olympiad Maths Prep

Library / /28 of 55

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+\dots+2018" and will change it to expression "-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.

Looking for a route rather than 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.