Skip to main content
OlympiadHQ

Browse · MathNet

Print

26th Turkish Mathematical Olympiad

Turkey counting and probability

Problem

There are distinguishable boxes on the table. Starting Writer, Writer and Braker take turn writing a box pair to the table (each pair can be written at most once). They stop when there are written pairs on the table. After that Braker numerates box pairs by numbers and for each puts balls into each box belonging to pair numbered . Can Braker guarantee that any two boxes will contain different number of balls?
Solution
Yes, Braker can guarantee that any two boxes will contain different number of balls. Suppose that Writer at the first move writes a pair . At each move Braker chooses pairs containing box (if possible). By doing that he can guarantee that all pairs , are on the table. Braker numerates all pairs not containing randomly by numbers and accordingly puts balls into these boxes. Let be the total number of balls in the box after this procedure. Without loss of generality, assume that After that Braker for each numerates by and accordingly distributes balls. Hereby we get For each the box received balls at most times and only in one case the number of balls was more than . Therefore, and as a result any two boxes contain different number of balls.
Final answer
Yes

Techniques

Games / greedy algorithms