Olympiad Maths Prep

Library / /5 of 6

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Turkey

There are 20182018 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 40324032 written pairs on the table. After that Braker numerates box pairs by numbers 1,2,,40321, 2, \dots, 4032 and for each k=1,2,,4032k = 1, 2, \dots, 4032 puts kk balls into each box belonging to pair numbered kk. 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 (A1,A2)(A_1, A_2). At each move Braker chooses pairs containing box A1A_1 (if possible). By doing that he can guarantee that all pairs (A1,Ai)(A_1, A_i), i=2,3,,2018i = 2,3,\ldots,2018 are on the table. Braker numerates all 20152015 pairs not containing A1A_1 randomly by numbers 1,2,,20151,2,\ldots,2015 and accordingly puts balls into these boxes. Let t(Ai)t(A_i) be the total number of balls in the box AiA_i after this procedure. Without loss of generality, assume that
t(A2)t(A3)t(A2018) t(A_2) \le t(A_3) \le \dots \le t(A_{2018})
After that Braker for each i=2,3,,2018i = 2,3,\ldots,2018 numerates (A1,Ai)(A_1, A_i) by 2014+i2014 + i and accordingly distributes balls. Hereby we get
t(A2)<t(A3)<<t(A2018). t(A_2) < t(A_3) < \dots < t(A_{2018}).
For each i=2,3,,2018i = 2,3,\ldots,2018 the box AiA_i received balls at most 20162016 times and only in one case the number of balls was more than 20152015. Therefore,
t(A1)=2016+2017++4032>20162016+4032>t(Ai) t(A_1) = 2016 + 2017 + \dots + 4032 > 2016 \cdot 2016 + 4032 > t(A_i)
and as a result any two boxes contain different number of balls.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.