Задача М465‍‍‍

Имеется тысяча билетов с номерами 000, 001, $\ldots$‍,‍ 999 и сто ящиков с номерами 00, 01, $\ldots$‍,‍ 99. Билет разрешается опускать в ящик, если номер ящика можно получить из номера этого билета вычёркиванием одной из цифр. Докажите, что

1. можно разложить все билеты в 50 ящиков;
2. нельзя разложить все билеты менее, чем в 40 ящиков;
3. нельзя разложить все билеты менее, чем в 50 ящиков.

Пусть вообще имеется $10^k$‍‍ билетов с $k$‍‍-значными номерами от 00$\ldots$‍‍0 до 99$\ldots$‍‍9. Билет разрешается опускать в ящик, номер которого можно получить из номера этого билета вычёркиванием некоторых $k-2$‍‍ цифр.

4. Докажите, что при $k=4$‍‍ все $10\,000$‍‍ четырёхзначных билетов можно разложить по 34 ящикам.
5. Найдите минимальное количество ящиков, в которые можно разложить $k$‍‍-значные билеты. Попробуйте решить эту задачу для $k=4$‍,‍ 5, 6, $\ldots$‍‍