Решение задачи 341

Условие:

Крош хочет порадовать Ёжика и вставить в торт к его дню рождения свечки в форме некоторого выражения, значение которого есть натуральное число меньшее 100 (возраст Ёжика). Более того, он собирается использовать одни и те же цифры каждый год. Также у Кроша есть свечка в виде знака "×". Необходимо, чтобы каждый год Крош смог составлять возраст Ёжика с помощью этих свечек. Какое наименьшее количество свечек-цифр ему для этого потребуется?

Решение:

Пример:

Заметим, что 10 свечек с цифрами 0,1,2,3,4,5,6,7,8,9 почти хватит. Можно составить любое натуральное число меньшее ста напрямую, за исключением чисел с двумя одинаковыми цифрами (11,22,33,44 и т. д.). Если мы добавим ещё одну свечку в формы цифры 1, то у нас выйдет составить любое число. Действительно, число вида nn мы представляем как 11×n (если n=1, то можно просто составить 11). Любое другое число составляется напрямую из двух (или одной) цифр. Значит 11 цифр Крошу точно хватит.

Оценка:

Заметим, что в каждом десятке от 10 до 99 есть хотя бы одно простое число. Очевидно, что простые числа необходимо составлять напрямую (не черед произведение двух чисел). Таким образом, любая цифра от 1 до 9 должна присутствовать. Оборатим внимание на число 50. Оно может быть представлено как: 50, 25×2, 10×5. В любом случае потребуется дополнительно либо цифра 0, либо ещё одна цифра 2. Таким образом, по крайней мере 10 цифр потребуется. Очевидно что с помощью 10 различных цифр или с помощью цифр от 1 до 9 с дополнительной двойкой число 11 никак не представить. Значит цифр у Кроша хотя бы 11.

Ответ: 11.