Задача 78683

Темы:    [ Процессы и операции ] [ Разбиения на пары и группы; биекции ] [ Десятичная система счисления ] [ Объединение, пересечение и разность множеств ]

Сложность: 4+ Классы: 9,10,11

Условие

Дано натуральное число N. С ним производится следующая операция: каждая цифра этого числа заносится на отдельную карточку (при этом разрешается добавлять или выбрасывать любое число карточек, на которых написана цифра 0), и затем эти карточки разбивают на две кучи. В каждой из них карточки располагаются в произвольном порядке, и полученные два числа складываются. С полученным числом N₁ проделывается такая же операция, и т.д. Докажите, что за 15 шагов из N можно получить однозначное число.

Решение

Докажем, что достаточно даже 12 операций. Заметим, что если из набора карточек A мы можем получить одной операцией набор карточек A₁ , а из набора карточек B мы можем получить одной операцией набор карточек B₁ , то из объединения наборов карточек A B мы можем получить набор A₁ B₁ также одной операцией. Для этого достаточно приписать числа, которые мы складываем при выполнении второй операции, в конце чисел, которые мы складываем при выполнении первой операции, вставив между ними некоторое количество нулей. Поэтому мы можем разбивать произвольным образом цифры нашего числа на группы и производить операции с каждой группой параллельно. Разобьем все цифры исходного числа на 9 групп, состоящие из одинаковых цифр. Достаточно показать, что из числа, записываемого одинаковыми цифрами, за 7 операций можно получить однозначное число. Тогда из числа N мы сможем за 7 операций получить число, записываемое не более чем 9 ненулевыми цифрами. Последнее можно за 5 операций сделать однозначным: сначала разбить число на 5-значное и 4-значное, и сложить их; потом на – 3-значное и 2-значное, сложить их, и так далее , пока не получим однозначное. (Случай, когда мы на каком-то шаге получаем число, записываемое одними девятками, нужно разбирать отдельно.) Итак, пусть на дано число, записанное одинаковыми цифрами. Разобьем все цифры на несколько групп по 9 цифр и одну группу из менее 9 цифр. Тогда, действуя аналогично предыдущему, за 5 операций каждую из групп, кроме последней, можно превратить в группу из единственной карточки с цифрой 9 , а последнюю группу – в группу из единственной карточки с некоторой цифрой b . Пусть b 0 (при b=0 рассуждение аналогично). Объединим теперь наши группы. Произведем 6-ю операцию: 9999999..9+b=100000..000c , и 7-ю: 1+c=b – мы получили однозначное число.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	31
Год	1968
вариант
	1
Класс	9
Тур	2
задача
Номер	5