Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 6.6 National olympiad Prove it Romania

On a line, there are 51 positive integers whose sum is 100. Prove that, for all positive integers kk, 1k991 \le k \le 99, one can find either a succession of numbers on the line whose sum is kk, or a succession of numbers whose sum is 100k100-k.

Solution

Let a1,a2,,a51a_1, a_2, \dots, a_{51} be the 51 numbers with a1+a2++a51=100a_1 + a_2 + \dots + a_{51} = 100. On a circle of total length 100 we place 100 points such that the length of the arc between any two neighboring points (of these 100) is equal to 1. We fix one of these points and denote it by A1A_1. Then, we mark on the circle points A2,A3,,A51A_2, A_3, \dots, A_{51}, in this order, such that the length of each arc AiAi+1A_iA_{i+1} is aia_i for all i=1,50i = 1, 50. Clearly, the length of the arc A51A1A_{51}A_1 will be a51a_{51}.

We color the points A1,A2,,A50A_1, A_2, \dots, A_{50} with blue, and the other 49 points with red. We prove that for all k[1,99]k \in [1, 99] we can find two blue points, AiA_i and AjA_j, such that the lengths of the two arcs determined by these two points are kk and 100k100-k. It is sufficient to prove this statement for k50k \le 50.

For k=50k = 50 we have 51 blue points, so there must be a pair of blue points that are diametrically opposed. For k<50k < 50, consider for each blue point AjA_j the points BB such that the length of the arc AjBA_jB is kk. There are two such points for each point AjA_j. If any of these points is blue, we have found an arc AiAjA_iA_j of length kk. Assume all these points BB are red; each of these points BB has been considered at most twice, but each blue point uses two red ones. Thus, 51 blue points require 51 red ones, but only 49 are available. We conclude that our assumption was false, therefore an arc AiAjA_iA_j of length kk must exist.

Now we cut the circle at A1A_1 and turn it into a line segment. For all kk, we might have thus cut one of the arcs AiAjA_iA_j, either the one of length kk or the one of length 100k100-k, but not both. Thus, for all kk, either a line segment AiAjA_iA_j of length kk, or one of length 100k100-k, must exist.

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.