Bariz - Problem

Source: Turkey National Mathematical Olympiad 2018

Tags: combinatorics

grupyorum

02.12.2018 23:47

Initially, there are 2018 distinct boxes on a table. In the first stage, Yazan and Bozan, starting with Yazan, take turns make $2016$ moves each, such that, in each move, the person whose turn selects a pair of boxes that is not written on the board, and writes the pair on the board. In the second stage, Bozan enumerates the $4032$ pairs with numbers from $1,2,\dots,4032$, in whichever order he wants, and puts $k$ balls in each boxes written contained in the $k^{th}$ pair. Is there a strategy for Bozan that guarantees that the number of balls in each box are distinct?

The answer is yes. Let us call the boxes $x_1$ to $x_{2018}$, and wlog assume that Yazan writes the pair $(x_1, x_2)$ in the first move. In her moves, Bozan will connect $x_1$ to the remaining $2016$ boxes (If there is a pair that is already connected, then she will make a random move). When enumerating, Bozan will distribute the numbers from $1$ to $2015$ randomly among the pairs that do not contain $x_1$. Now, wlog assume that the amount of balls in the boxes other than $x_1$ are ordered $x_{2}\leq\ldots\leq x_{2018}$ Lastly, Bozan will enumerate the pair $(x_1, x_i)$ with $2014+i$. It works, because now Bozan has $x_{2}<\ldots<x_{2018}$ and $x_1=2016+\ldots+4032>1+\ldots+2015+4032\geq x_{2018}$, q.e.d.