Problem 7, Combinatorics – Mattia Giuri's bizarre blog

I proposed this problem in the last mathematical competition hosted on the Italian ‘gasmatematica’ website.

The numbers from 000 to 999 must be put into some boxes, numbered from 00 to 99. If the label of a box is equal to a number with one digit removed, then the number can be put in that box. For instance, 035 can be put in boxes 03, 05 and 35.

If all the numbers can be put in k boxes, find the minimum value of k.

The proof is divided in two parts: proving $k \leq 50$ and proving $k \geq 50$ .

First of all, a set of boxes that works can be constructed as follows:

I take the numbers from 0 to 4 (set A) and from 5 to 9 (set B). For each of the two sets, I consider all the couples that can be made by two of their elements: 00, 01, …, 44 for the first and 55, 56, …, 99 for the second.

The total number of couples is $2 \cdot 5^2 = 50$ .

Why does it work? Well consider a number, then two of its digits must be in the same set (A or B), and since we have all the possible couples from each of the sets covered, it’s always possible to find a collocation for any number.

So $k \leq 50$

Now, let’s say that the number of boxes which label begins with the digit 1 is the smallest, and it’s x. Denote such boxes by $1a_i(i = 1, ..., m)$ . Let C be the set of all the $a_i$ , then for every 2 digits a, b not in C consider the number 1ab. Since boxes 1a and 1b don’t exist by our choice of a and b, box ab must exist. This reasoning works for each of the $(10-m)^2$ ordered couples (a, b).

Now, by our choice of m, we know that there are at least m boxes starting with a number in C. Hence we can conclude:

$k \geq m^2 + (10-m)^2 \geq \frac{1}{2}[m + (10-m)]^2 = 50$

by the AM-QM inequality, with equality case when $m = 10-m = 5$

Hence, the minimum is 50.