Maths Olympiad Prep

Library / /189 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

The expression  1  2 3  2012\circ \ 1\ \circ \ 2 \ \circ 3 \ \circ \dots \circ \ 2012 is written on a blackboard. Catherine places a ++ sign or a - sign into each blank. She then evaluates the expression, and finds the remainder when it is divided by 2012. How many possible values are there for this remainder?

Proposed by Aaron Lin

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. We start with the expression ±1±2±3±±2012\pm 1 \pm 2 \pm 3 \pm \cdots \pm 2012. We need to determine the number of possible remainders when this expression is divided by 2012.

2. Consider the sum of the sequence 1+2+3++20121 + 2 + 3 + \cdots + 2012. The sum of the first nn natural numbers is given by:
S=n(n+1)2 S = \frac{n(n+1)}{2}
For n=2012n = 2012, we have:
S=2012×20132=2012×1006.5 S = \frac{2012 \times 2013}{2} = 2012 \times 1006.5

3. Since we are placing either a ++ or - sign in front of each number, the sum can range from S-S to SS. However, we are interested in the remainders when this sum is divided by 2012.

4. Notice that each number kk in the sequence can be paired with k1k-1 to form either k(k1)k - (k-1) or (k1)k(k-1) - k, which simplifies to 11 or 1-1. This means we can form pairs that contribute ±1\pm 1 to the total sum.

5. There are 1006 such pairs (since 2012/2=10062012/2 = 1006). Therefore, the possible sums are all even numbers from 2012×1006-2012 \times 1006 to 2012×10062012 \times 1006.

6. To find the possible remainders when divided by 2012, we need to consider the sums modulo 2012. Since the sums are even, the remainders must also be even.

7. The possible even remainders modulo 2012 are 0,2,4,,20100, 2, 4, \ldots, 2010. This forms an arithmetic sequence with the first term a=0a = 0 and common difference d=2d = 2.

8. The number of terms in this sequence is given by:
n=201002+1=1006 n = \frac{2010 - 0}{2} + 1 = 1006

9. Therefore, there are 1006 possible even remainders when the expression is divided by 2012.

The final answer is 1006\boxed{1006}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.