|
|
 |
Условие
Назовём девятизначное число красивым, если все его цифры различны.
Докажите, что существует по крайней мере а) 1000; б) 2018 красивых чисел, каждое из которых делится на 37.
Решение
а) Всякое девятизначное число $M$ равно сумме $10^6A + 10^3B + C = 999(1001A + B) + (A + B + C)$, где $A, B, C$ – числа, образованные тремя первыми, тремя следующими и тремя последними цифрами числа $M$. Разобьём цифры от 1 до 9 на три тройки с суммой 15 в каждой. Если мы на первые места в числах $A, B, C$ поставим три цифры из одной тройки, на вторые – из другой, на третьи – из оставшейся, сумма $A + B + C$ будет равна 15·111 = 45·37. Так как и 999 делится на 37, то красивое число $M$ при такой расстановке цифр будет кратно 37. Поскольку три цифры по трём местам можно расставить шестью способами и назначить три тройки на первое, второе и третье места тоже можно шестью способами, всего у нас получается 64 = 1296 красивых чисел, кратных 37. Теперь достаточно указать три тройки цифр с равными суммами. Например, это {1, 5, 9}, {2, 6, 7}, {3, 4, 8}.
б) Будем записывать красивое число $\overline{a_8\ldots a_0}$ в виде таблицы (см. рис.).
Так как 106 – 1 = 999999 делится на 999, то $\overline{a_8\ldots a_0} = 10^8a_8 +\ldots + a_0 = 100(a_8+a_5+a_2) + 10(a_7+a_4+a_1) + (a_6+a_3+a_0)$ (mod 999).
Поэтому из красивого числа, кратного $d$, где $d$ – делитель числа 999, перестановками внутри столбцов можно получить 6³ = 216 красивых чисел, кратных $d$ (если первый столбец содержит нуль, то на 72 числа меньше).
Первый способ. Рассмотрим таблицу.
Суммы в её столбцах одинаковые. Поэтому соответствующее красивое число кратно 111. Переставляя столбцы местами, получим 6·216 красивых чисел, кратных 111. Так как по строкам суммы тоже одинаковые, то, отразив эту табличку относительно диагонали, получим ещё столько же чисел, а всего – 2592 красивых числа, кратных 111, а значит, кратных и 37.
Замечание. Приведённая таблица называется магическим квадратом. Помимо содержащихся в нём двух способов скомпоновать из различных цифр три равные суммы по три слагаемых есть ещё ровно 6 способов сделать это. И все они получаются из магического квадрата! Покажем это. Уменьшим в нём цифры 1, 2, 3 на единицу. Получим два способа, дающих по 1296 – 2·72 = 1152 числа. После этого, уменьшив цифры 4, 5, 6, получим ещё два способа. Наконец, уменьшим 7, 8, 9, получая ещё два способа. Всего таким методом получается 9504 красивых числа, кратных 111.
Далее нам понадобится
Лемма. Пусть $d$ – делитель числа 999. Если $100x + 10y + z$ кратно $d$, то и числа $100y + 10z + x$ и $100z + 10x + y$ кратны $d$.
Доказательство. $100y + 10z + x = 10(100x + 10y + z) - 999x$.
Второй способ. Заметим, что 100·8 + 10·18 + 19 = 999. Легко найти пять разбиений ненулевых цифр на столбцы с суммами 19, 18, 8 справа налево (левый столбец не указываем, он получается автоматически): 982, 765; 973, 864; 964, 873; 874, 963; 865, 972. Учитывая циклические сдвиги столбцов, всего получим 5·3·216 = 3240 красивых чисел, кратных 999.
Замечание. Другие красивые числа, кратные 999, можно получить, дополняя все цифры до 9. При этом 5·72 чисел будут начинаться с нуля, их надо отбросить. Всего получится 6120 красивых чисел, кратных 999. Нетрудно показать, что других красивых чисел, кратных 999, нет!
Третий способ (идея Алиева Рашида, 10 кл., г. Махачкала). Рассмотрим таблицу.
Замечание. Ещё столько же красивых чисел получится из таблицы
Замечания
1. Всего существует 89712 красивых чисел, кратных 37, из них 34416 чисел кратны 111.
2. 5 баллов.
3. В 8-9 кл. предлагался п.а), в 10-11 кл – п. б).
