Browse · MathNet
Print58th Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
60 participants took part in the Olympiad. They were offered 8 tasks, evaluated from 0 to 7 points each. Prove, that in total there are 3 participants, whose results differ in not more than 1 point. Would the statement be true, if 58 took part in the Olympiad?
Result of a participant at Olympiad is the total amount of the points he got.
Result of a participant at Olympiad is the total amount of the points he got.
Solution
Minimal amount of points, that was possible to earn equals to , maximum – to . Consider such segments in points: , , , ..., and points. If at least 3 students are in at least one of these segments, the statement is proved. If not, then for each of these segments there are not more than two students. There are segments, so not more than might have taken part in the Olympiad. This contradiction ends the proof of the first part.
For the second part. If exactly participants got each of points , , , ..., . Then there are no three, difference of whose results is not more than point. And in total there are exactly participants.
For the second part. If exactly participants got each of points , , , ..., . Then there are no three, difference of whose results is not more than point. And in total there are exactly participants.
Final answer
Yes for sixty participants; no for fifty-eight participants. A counterexample for fifty-eight is two participants at each even total from zero to fifty-six.
Techniques
Pigeonhole principle