Maths Olympiad Prep

Library / /327 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it

Suppose that 20022002 numbers, each equal to 11 or 1-1, are written around a circle. For every two adjacent numbers, their product is taken; it turns out that the sum of all 20022002 such products is negative. Prove that the sum of the original numbers has absolute value less than or equal to 10001000. (The absolute value of xx is usually denoted by x|x|. It is equal to xx if x0x \ge 0, and to x-x if x<0x < 0. For example, 6=6,0=0|6| = 6, |0| = 0, and 7=7|-7| = 7.)

Solution

1. Let x x be the number of +1 +1 's and y y be the number of 1 -1 's among the 2002 numbers. Therefore, we have:
x+y=2002 x + y = 2002

2. Consider the product of every two adjacent numbers. If two adjacent numbers are the same (both +1 +1 or both 1 -1 ), their product is +1 +1 . If they are different (one +1 +1 and one 1 -1 ), their product is 1 -1 .

3. Let P P be the sum of the products of all adjacent pairs. We are given that P P is negative:
P=(product of adjacent numbers)<0 P = \sum (\text{product of adjacent numbers}) < 0

4. To find P P , note that there are x x pairs of adjacent +1 +1 's, y y pairs of adjacent 1 -1 's, and 2002(x+y)=20022002=0 2002 - (x + y) = 2002 - 2002 = 0 pairs of adjacent +1 +1 and 1 -1 . Therefore:
P=x(+1)+y(+1)+(2002xy)(1) P = x \cdot (+1) + y \cdot (+1) + (2002 - x - y) \cdot (-1)
Simplifying, we get:
P=x+y(2002xy)=x+y2002 P = x + y - (2002 - x - y) = x + y - 2002

5. Since x+y=2002 x + y = 2002 , we substitute:
P=20022002=0 P = 2002 - 2002 = 0
This contradicts the given condition that P<0 P < 0 . Therefore, our assumption must be incorrect.

6. Reconsider the problem. The correct approach is to count the number of +1 +1 and 1 -1 pairs. Let a a be the number of pairs (+1,+1) (+1, +1) and b b be the number of pairs (1,1) (-1, -1) . Then:
P=a+b(2002ab) P = a + b - (2002 - a - b)
Simplifying, we get:
P=2(a+b)2002 P = 2(a + b) - 2002

7. Given P<0 P < 0 , we have:
2(a+b)2002<0    a+b<1001 2(a + b) - 2002 < 0 \implies a + b < 1001

8. Since a+b a + b is the number of pairs of the same sign, the number of pairs of different signs is 2002(a+b) 2002 - (a + b) . Therefore, the number of +1 +1 's and 1 -1 's must be balanced such that:
xy x \approx y

9. Let S S be the sum of the original numbers:
S=xy S = x - y
Since x+y=2002 x + y = 2002 and xy x \approx y , we have:
S=xy1000 |S| = |x - y| \leq 1000

The final answer is S1000 \boxed{ |S| \leq 1000 }

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.