Maths Olympiad Prep

Library / /53 of 65

Combinatorics Difficulty 6.7 National Olympiad Prove it Romania

Let x1,x2,,x5x_1, x_2, \dots, x_5 be real numbers. Find the least positive integer nn with the following property: if there exist nn distinct sums of the form xp+xq+xrx_p + x_q + x_r (with 1p<q<r51 \le p < q < r \le 5) which are equal to 00, then x1=x2==x5=0x_1 = x_2 = \dots = x_5 = 0.
Bulgaria, 2003

Solution

If the numbers are 1,1,1,1,21, 1, 1, 1, -2, (or 1,1,1,2,21, 1, 1, -2, -2) there are 66 sums that are equal to 00 without the numbers themselves being 00. Therefore, knowing 66 sums (or less) to be 00 is not enough to conclude that the numbers are all 00.

Now we prove that 77 is enough. Suppose we are given that 77 sums are equal to 00. These sums contain, in total, 2121 terms, while there are only 55 numbers. By the Pigeonhole Principle it follows that there is a number that appears (at least) 55 times. Suppose x1x_1 appears (at least) 55 times. x1x_1 is involved in 66 sums, so there is only one sum, say x1+x4+x5x_1 + x_4 + x_5, that is not necessarily 00. All the other ones are 00: x1+x2+x3=x1+x2+x4=x1+x2+x5=x1+x3+x4=x1+x3+x5=0x_1 + x_2 + x_3 = x_1 + x_2 + x_4 = x_1 + x_2 + x_5 = x_1 + x_3 + x_4 = x_1 + x_3 + x_5 = 0. The first three equations simplify to x3=x4=x5x_3 = x_4 = x_5, and then comparing the first and the last equation gives x2=x3=x4=x5x_2 = x_3 = x_4 = x_5.

Finally, x1x_1 only participates in at most 66 sums; the seventh one gives x2=x3=x4=x5=0x_2 = x_3 = x_4 = x_5 = 0, and it follows immediately that x1=x2=x3=x4=x5=0x_1 = x_2 = x_3 = x_4 = x_5 = 0.

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.