Skip to main content
OlympiadHQ

Browse · MathNet

Print

58th 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.
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.
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