ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66715
Темы:    [ Теория чисел. Делимость (прочее) ]
[ Десятичная запись числа ]
Сложность: 5
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Назовём девятизначное число красивым, если все его цифры различны. Докажите, что существует по крайней мере 1000 красивых чисел (или: не менее 2018), каждое из которых делится на 37.

Решение

Всякое девятизначное число $M$ равно сумме $10^6A + 10^3B + C = 999\cdot(1001A + B) + (A + B + C)$, где $A, B, C$ — числа, образованные тремя первыми, тремя следующими и тремя последними цифрами числа $M$. Разобьём цифры от $1$ до $9$ на три тройки с суммой $15$ в каждой. Если мы на первые места в числах $A, B, C$ поставим три цифры из одной тройки, на вторые — из другой, на третьи — из оставшейся, сумма $A + B + C$ будет равна $15\cdot 111 = 45\cdot 37$. Так как и $999$ делится на 37, то красивое число $M$ при такой расстановке цифр будет кратно 37. Поскольку три цифры по трём местам можно расставить шестью способами и назначить три тройки на первое, второе и третье места тоже можно шестью способами, всего у нас получается $6\cdot6\cdot6\cdot 6 = 1296$ красивых чисел, кратных 37. Теперь достаточно указать три тройки цифр с равными суммами. Например, это {1, 5, 9}, {2, 6, 7}, {3, 4, 8}.

Дополнение. В варианте старших классов надо было доказать, что красивых чисел не менее 2018. Приведём несколько решений этой задачи. Будем записывать красивое число $\overline{a_8\ldots a_0}$ в виде таблицы (см. рис.).

Так как $10^6 - 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^3 = 216$ красивых чисел, кратных $d$ (если первый столбец содержит нуль, то на 72 числа меньше).

1-е решение. Рассмотрим таблицу.

Суммы в её столбцах одинаковые. Поэтому соответствующее красивое число кратно $111$. Переставляя столбцы местами, получим $6\cdot 216$ красивых чисел, кратных $111$. Так как по строкам суммы тоже одинаковые, то, отразив эту табличку относительно диагонали, получим ещё столько же чисел, а всего — 2592 красивых числа, кратных $111$, а значит, кратных и $37$.

Замечание. Приведённая таблица называется магическим квадратом. Помимо содержащихся в нём двух способов скомпоновать из различных цифр три равные суммы по три слагаемых есть ещё ровно $6$ способов сделать это. И все они получаются из магического квадрата! Покажем это. Уменьшим в нём цифры $1, 2, 3$ на единицу. Получим два способа, дающих по $1296 - 2\cdot 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$.

2-е решение. Поищем красивые числа, кратные 999. Заметим, что $100\cdot 8 + 10\cdot 18 + 19 = 999$. Легко найти пять разбиений ненулевых цифр на столбцы с суммами $19, 18, 8$ справа налево (левый столбец не указываем, он получается автоматически): 982, 765; 973, 864; 964, 873; 874, 963; 865, 972. Учитывая циклические сдвиги столбцов, всего получим $5\cdot 3\cdot 216 = 3240$ красивых чисел, кратных $999$.

Замечание. Другие красивые числа, кратные $999$, можно получить, дополняя все цифры до $9$. При этом $5\cdot 72$ чисел будут начинаться с нуля, их надо отбросить. Всего получится $6120$ красивых чисел, кратных $999$. Нетрудно показать, что других красивых чисел, кратных $999$, нет!

Третий способ (навеяно идеей Алиева Рашида, 10 кл., г. Махачкала). Рассмотрим таблицу справа. Числа, читаемые в строках, делятся на $37$, поскольку отличаются на $111$. Поэтому соответствующее таблице девятизначное число кратно $37$. Осуществляя циклические сдвиги внутри строк, получим $27$ таблиц, каждая из которых даёт по $216$ красивых чисел, кратных $37$ (см. лемму). Для девяти из этих таблиц надо вычесть по $72$ числа. Всего получается $24\cdot 216 = 5184$ красивых числа, кратных $37$.

Замечания.

1. Ещё столько же красивых чисел получится из таблицы справа. Из указанных шести трёхзначных чисел можно составить ещё две такие таблицы. Следовательно, этот метод даёт $20736$ красивых чисел, кратных $37$.

2. Всего существует $89712$ красивых чисел, кратных $37$, из них $34416$ чисел кратны $111$.

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

олимпиада
Название Турнир городов
номер/год
Дата 2018/19
Номер 40
вариант
Вариант осенний тур, базовый вариант, 8-9 классы
задача
Номер 5
олимпиада
Название Турнир городов
номер/год
Дата 2018/19
Номер 40
вариант
Вариант осенний тур, базовый вариант, 10-11 класс
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .