CombinatoricsDifficulty 6.4National OlympiadProve itUnited States
Problem:
Suppose that 2002 numbers, each equal to 1 or −1, are written around a circle. For every two adjacent numbers, their product is taken; it turns out that the sum of all 2002 such products is negative. Prove that the sum of the original numbers has absolute value less than or equal to 1000. (The absolute value of x is usually denoted by ∣x∣. It is equal to x if x≥0, and to −x if x<0. For example, ∣6∣=6, ∣0∣=0, and ∣−7∣=7.)
Solution
Solution:
Suppose that n of the original numbers are +1, so that the remaining 2002−n are −1, and their sum is 1⋅n+(−1)⋅(2002−n)=2n−2002. Also suppose that m of the products equal −1; then the remaining 2002−m equal 1, and the sum of the products is 1⋅(2002−m)+(−1)⋅m=2002−2m. Since this is negative, m>1001. Now, each product of −1 must come from a +1 and a −1 among the original numbers, and each −1 among the original numbers can contribute to at most two such products; hence the original numbers include more than 1001/2>500−1's. Thus, 2002−n≥501⇒n≤1501⇒2n−2002≤1000 Similarly, the original numbers include more than 500+1's, so n≥501⇒2n−2002≥−1000 Thus, −1000≤2n−2002≤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.