Натуральное число n назовём небольшим, если в его десятичной записи встречаются только цифры 0, 1 или 2. При каком наименьшем k любое натуральное число можно представить в виде суммы не более k небольших чисел?

Question

Вопрос:

Натуральное число n назовём небольшим, если в его десятичной записи встречаются только цифры 0, 1 или 2. При каком наименьшем k любое натуральное число можно представить в виде суммы не более k небольших чисел?

Фотография

Ответ ассистента

Accepted Answer

Пусть число $N$ записано в десятичной системе счисления. Это значит, что $N = d_m 10^m + d_{m-1} 10^{m-1} + \dots + d_1 10^1 + d_0 10^0$, где $d_i$ — цифры числа (от 0 до 9). Мы хотим представить число $N$ как сумму «небольших» чисел (чисел, состоящих только из цифр 0, 1, 2). Рассмотрим произвольную цифру $d_i$ в разряде $10^i$. Ее можно представить как сумму цифр 0, 1, 2. Максимальная цифра — 9. Сколько слагаемых нужно, чтобы получить 9, используя только 0, 1, 2? Так как $9 = 2 + 2 + 2 + 2 + 1$, нам нужно минимум 5 чисел, чтобы получить 9 в одном разряде. Например: $9 \cdot 10^i = (2+2+2+2+1) \cdot 10^i = 2\cdot 10^i + 2\cdot 10^i + 2\cdot 10^i + 2\cdot 10^i + 1\cdot 10^i$. Все числа (200...0, 100...0) являются «небольшими» по условию задачи. Таким образом, любая цифра $d_i$ в любом разряде может быть представлена как сумма не более чем 5 «небольших» чисел. Значит, для любого числа $N$ нам достаточно $k=5$ слагаемых, чтобы представить его в виде суммы «небольших» чисел. Ответ: 5.

Ответ ассистента

Другие решения