Beto plays the following game with his computer: initially the computer randomly picks $30$ integers from $1$ to $2015$, and Beto writes them on a chalkboard (there may be repeated numbers). On each turn, Beto chooses a positive integer $k$ and some if the numbers written on the chalkboard, and subtracts $k$ from each of the chosen numbers, with the condition that the resulting numbers remain non-negative. The objective of the game is to reduce all $30$ numbers to $0$, in which case the game ends. Find the minimal number $n$ such that, regardless of which numbers the computer chooses, Beto can end the game in at most $n$ turns.
Problem
Source: Iberoamerican 2015 #6
Tags: combinatorics
elVerde
07.02.2016 19:20
Let's remove the upper bound of $2015$ on the chosen integers for now, and prove by induction of $k$ that the choice $\{1,2,2^2,...,2^k\}$ requires $k+1$ turns to be fully reduced. This is clear for $k=0$. Now let $k\geq 1$ and suppose that $\{1,2,2^2,...,2^{k-1}\}$ requires $k$ turns. Then obviously $\{1,2,2^2,...,2^k\}$ requires at least $k$ turns. Suppose $k$ turns are sufficient. By the induction hypothesis, in each of these $k$ turns we must reduce at least one of the numbers of $\{1,2,2^2,...,2^{k-1}\}$. If we tag $2^k$ along with each of these reductions we see that in these $k$ turns we can reduce $2^k$ by at most $1+2+2^2+\cdots+2^{k-1}=2^k-1<2^k$, and thus cannot completely reduce it to $0$. This means we need at least one more turn. It's clear what to do to reduce $\{1,2,2^2,...,2^k\}$ in $k+1$ turns. We know that $2^{10}<2015<2^{11}$. If the computer chooses $\{1,2,2^2,...,2^{10}\}\cup A$ where $|A|=19$ and $A\subset\{1,2,3,...,2015\}$, by the previous discussion Beto needs at least $10+1=11$ turns. Hence $n\geq 11$. Now we show $n=11$ works. Suppose that the computer chooses $\{a_1,a_2,...,a_{30}\}$ where $1\leq a_i\leq 2015<2^{11}$. We can write $a_i=2^{10}\delta_{i,10}+2^9\delta_{i,9}+\cdots+2^1\delta_{i,1}+\delta_{i,0}$ with $\delta_{i,j}\in\{0,1\}$ for the binary representation of $a_i=(\delta_{i,10}\delta_{i,9}\cdots\delta_{i,0})_2$. Now it's clear what we should do. In the first turn we substract $2^{10}$ from all $a_i$ such that $\delta_{i,10}=1\Leftrightarrow a_i\geq 2^{10}$ (or we skip this turn if there are none, thus requiring even less turns). Afterwards we have $a_i<2^{10}$. In the second turn we subtract $2^9$ from all $a_i$ such that $\delta_{i,9}=1\Leftrightarrow a_i\geq 2^9$, etc... In the eleventh turn we have $a_i\in\{0,1\}$ and we are left to subtract $1$ from all $a_i=1\Leftrightarrow\delta_{i,0}=1$, ending the game in $11$ steps. Thus $n=11$. It's also clear how to generalize this for a choice of $k$ numbers in $\{1,2,...,m\}$. The value of $n$, the minimum numbers of turns required, in this case is $n=\min\{\lfloor\log_2m\rfloor+1,k\}$.