Emptying a Big Number of Boxes

Problem

emptying boxes

Solution 1

At every step of the task we shall group the boxes with the same number of marbles into one group. Assume at some point there were $n$ such groups (there were $2018$ of them, to start with). We choose $k$ groups and remove from each box in those groups the same number of marbles. Note that

  1. The number of stones in the untouched $n-k$ groups remain the same.
  2. The boxes in the $k$ groups will still belong to $k$ different groups.

It follows that after the undertaken step, the number of groups is at least $\displaystyle \max\{k,n-k\}\ge\frac{n}{2},$ meaning that at every step the number of groups falls at most by a factor of $2.$

There is a strategy of reducing the number of groups almost by a factor of $2$ so that the number of steps required to empty the boxes is $\displaystyle 11=\lceil\log_{2} 2018\rceil.$

The strategy is this: consider the boxes with more than $\displaystyle \frac{2018}{2}=1009$ and remove $1009$ marbles from each. As the result, there will be two boxes with $1,$ two boxes with $2$ marbles, ..., two boxes with $1009$ marbles - the total of $1009$ groups of boxes. Next, consider all the boxes with more than $\displaystyle \lfloor\frac{1009}{2}\rfloor=504$ marbles and remove $504$ marbles from each. There will be now $505$ groups of boxes. Following this pattern, after every step we shall have the following number of groups:

$2018,1009,505,253,127,64,32,16,8,4,2,1.$

After ten steps, we get a single group, i.e., the case where all boxes hold the same amount of marbles ($1$ in fact) and can be emptied in one - the eleventh - move.

Solution 2

Considering the number of boxes $(2108)$ in base $2,$ we can consider steps that remove each individual bit, so taking $2^x,$ with $x \le \log_2(2108)$ gives the answer of $11.$

Acknowledgment

This is a modification of problem M1241 from the Russian Kvant magazine. The original problem and the solution are by N. Agakhanov.

Solution 2 is by Mihai Ciucu.

|Contact| |Front page| |Contents| |Algebra| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny

72087742