Арифметика и кубики

Посчитаем для каждой цифры число кубиков, на которых она встречается хотя бы один раз.

Забавно, но этой информации достаточно чтобы почти точно получить ответ.

Наблюдение 1. Если каждая цифра от $$$1$$$ до $$$9$$$ встречается хотя бы $$$n$$$ раз, то можно выложить любое число длины $$$n$$$ и меньше, не содержащее нулей в записи.

Доказательство. Выложим первую цифру числа любым подходящим кубиком. Не сложно видеть, что теперь каждая цифра встречается хотя бы $$$n - 1$$$ раз. Повторим данное рассуждение ещё $$$n - 1$$$ раз.

Наблюдение 1$$$^+$$$. Если каждая цифра от $$$1$$$ до $$$9$$$ встречается хотя бы $$$n$$$ раз, а $$$0$$$ встречается хотя бы $$$n - 1$$$ раз, то можно выложить любое число длины $$$n$$$ или меньше.

Доказательство$$$^+$$$. Дословно применить предыдущее доказательство не получится: может оказаться, что в момент когда мы уже выложили $$$n - 1$$$ цифру из $$$n$$$, то все нули закончились, а нужно выложить ноль. Давайте сначала выложим все нулевые цифры, а потом остальные. Тогда такой проблемы не возникнет.

Оказывается, что если $$$n$$$ — минимальное число, не подходящее под условие леммы, то ответ является числом длины $$$n$$$, более того, он выглядит как одно из:

Поймём почему. Начнём с того, что поймём, чего же не хватило, чтобы увеличить $$$n$$$. Пусть нулей. Тогда $$$1000\ldots000$$$ является ответом.

Пусть нулей достаточно, а наименьшая цифры, которой не хватило — это $$$d$$$. Кстати несложно видеть, что любое число длины $$$n$$$ только из цифр $$$0$$$, $$$1$$$, ..., $$$d - 1$$$ всё ещё можно представить. А вот число $$$dddddd{\ldots}dddd$$$ уже точно не представить.

Число $$$d000\ldots00$$$ иногда тоже может являться ответом. Хотя и нулей и цифры $$$d$$$ достаточно много (обоих хотя бы по $$$n - 1$$$), но если их обоих ровно $$$n - 1$$$ и они находятся на одинаковых кубиках, то собрать $$$d000\ldots00$$$ не выйдет.

Может быть неочевидно, почему ответом не может быть что-то промежуточное: cколько-то $$$d$$$ и сколько-то $$$0$$$. Но всё достаточно просто, покажем, что если мы умеем выражать $$$d000{\ldots}000$$$, то можно и любое другое число из нулей и $$$d$$$, кроме всех $$$d$$$. Возьмём ответ для $$$d0000{\ldots}0000$$$. У нас есть достаточно много кубиков содержащих $$$d$$$ и не использованных сейчас для отображения $$$d$$$. Если этот кубик показывает сейчас $$$0$$$, то просто перевернём его. Если этот кубик не используется, просто заменим один из кубиков с $$$0$$$ на него.