Maths Olympiad Prep

Library / /8 of 17

Combinatorics Difficulty 5.8 AIME, harder Prove it Argentina

Given are 51 natural numbers written in a row. Their sum is 100. An integer is representable if it can be expressed as the sum of several consecutive numbers in the given row. Prove that for each k{1,2,,100}k \in \{1, 2, \dots, 100\} one of the numbers kk and 100k100-k is representable.

Solution

Let the given row be a1,,a51a_1, \dots, a_{51}. Take a circle γ\gamma of length 100. Mark 51 blue points on it so that they determine 51 consecutive arcs of lengths a1,,a51a_1, \dots, a_{51}. One may imagine each number aia_i written next to an arc of γ\gamma with length aia_i. So, starting from a certain blue point BB, the numbers are arranged around γ\gamma as in the given row.

The claim that kk or 100k100-k is representable is equivalent to saying that there is an arc α\alpha of length kk with blue endpoints. Indeed consider α\alpha and its complementary arc α\alpha', of length 100k100-k. Point BB cannot be interior to both α\alpha and α\alpha', hence kk or 100k100-k equals the sum of several consecutive numbers in the initial row.

We show that for each k50k \le 50 there is an arc of length kk with blue endpoints (once this is proven, the case k>50k > 50 follows trivially). Mark 49 more red points on γ\gamma so that the total of marked 100 points, blue and red, yields a division into arcs of length 1. Now k=50k=50 is almost immediate. To each blue point assign its diametrically opposite point (the number 100 of division points is even). The 51 assigned points are distinct. Since there are 49<5149 < 51 red points, some assigned point is blue, which is enough.

The essential case k<50k < 50 needs an appropriate modification. For each blue point XX write down the endpoints of the arc with length 2k2k and midpoint XX (this arc is "proper", it does not overlap itself). One obtains a list of 251=1022 \cdot 51 = 102 points. It is clear that no point occurs in it more than twice.

Therefore the list contains at least 51 distinct points. There are only 49<5149 < 51 red points. Hence some blue point is listed, completing the argument.

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 and solution reproduced as published; topic and difficulty added by this site.