Maths Olympiad Prep

Library / /34 of 86

Combinatorics Difficulty 6.4 National Olympiad Prove it United States

Problem:

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 \geq 0, and to x-x if x<0x<0. For example, 6=6|6|=6, 0=0|0|=0, and 7=7|-7|=7.)

Solution

Solution:

Suppose that nn of the original numbers are +1+1, so that the remaining 2002n2002-n are 1-1, and their sum is
1n+(1)(2002n)=2n2002. 1 \cdot n + (-1) \cdot (2002-n) = 2n - 2002.
Also suppose that mm of the products equal 1-1; then the remaining 2002m2002-m equal 11, and the sum of the products is
1(2002m)+(1)m=20022m. 1 \cdot (2002-m) + (-1) \cdot m = 2002 - 2m.
Since this is negative, m>1001m > 1001. Now, each product of 1-1 must come from a +1+1 and a 1-1 among the original numbers, and each 1-1 among the original numbers can contribute to at most two such products; hence the original numbers include more than 1001/2>5001001/2 > 500 1-1's. Thus,
2002n501n15012n20021000 2002 - n \geq 501 \Rightarrow n \leq 1501 \Rightarrow 2n - 2002 \leq 1000
Similarly, the original numbers include more than 500500 +1+1's, so
n5012n20021000 n \geq 501 \Rightarrow 2n - 2002 \geq -1000
Thus, 10002n20021000-1000 \leq 2n - 2002 \leq 1000, which is what we need.

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.