Browse · MathNet
PrintArgentina_2018
Argentina 2018 counting and probability
Problem
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 one of the numbers and is representable.
Solution
Let the given row be . Take a circle of length 100. Mark 51 blue points on it so that they determine 51 consecutive arcs of lengths . One may imagine each number written next to an arc of with length . So, starting from a certain blue point , the numbers are arranged around as in the given row.
The claim that or is representable is equivalent to saying that there is an arc of length with blue endpoints. Indeed consider and its complementary arc , of length . Point cannot be interior to both and , hence or equals the sum of several consecutive numbers in the initial row.
We show that for each there is an arc of length with blue endpoints (once this is proven, the case follows trivially). Mark 49 more red points on so that the total of marked 100 points, blue and red, yields a division into arcs of length 1. Now 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 red points, some assigned point is blue, which is enough.
The essential case needs an appropriate modification. For each blue point write down the endpoints of the arc with length and midpoint (this arc is "proper", it does not overlap itself). One obtains a list of 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 red points. Hence some blue point is listed, completing the argument.
The claim that or is representable is equivalent to saying that there is an arc of length with blue endpoints. Indeed consider and its complementary arc , of length . Point cannot be interior to both and , hence or equals the sum of several consecutive numbers in the initial row.
We show that for each there is an arc of length with blue endpoints (once this is proven, the case follows trivially). Mark 49 more red points on so that the total of marked 100 points, blue and red, yields a division into arcs of length 1. Now 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 red points, some assigned point is blue, which is enough.
The essential case needs an appropriate modification. For each blue point write down the endpoints of the arc with length and midpoint (this arc is "proper", it does not overlap itself). One obtains a list of 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 red points. Hence some blue point is listed, completing the argument.
Techniques
Pigeonhole principleColoring schemes, extremal arguments