Два числа

Вася составил семизначное число, использовав каждую цифру от 1 до 7 ровно по одному разу. Коля сделал то же самое. Оказалось, что Васино число больше, чем Колино. Докажите, что Васино число не делится на Колино число.

Ю. Бурман

Эта задача была предложена на олимпиаде факультета математики Высшей школы экономики. Можно попробовать предложить ее ученикам и в более сложной формулировке: «Могли ли мальчики составить числа так, чтобы Васино число делилось на Колино?» После определенного числа попыток не может не возникнуть подозрение, что такие числа составить нельзя. Тем самым мы приходим к нашей задаче.
Попробуем доказать «от противного». Пусть Васино число делится на Колино число. Заметим, что частное не может быть равно 1, т.к. в условии сказано, что числа мальчики получили различные (Васино число больше, чем Колино). Частное не может быть больше 8. Это следует из того, что Колино число не меньше, чем 1234567, а 1234567∙9 – число уже восьмизначное.
Теперь нам поможет известный совет: «В задачах на делимость переходи к остаткам». Остаток от деления на 2 вроде бы не поможет – одно число может быть четным, но и другое число тоже. А остаток от деления на какое число у Васиного и у Колиного чисел совпадает? Конечно на 9. Потому что остаток от деления числа на 9 равен остатку от деления на
9 суммы цифр этого числа. А сумма цифр у Васиного числа и у Колиного числа одинаковая: 1 + 2 + … + 7 = 28 = 1 (mod 9). Осталось заметить, что если Колино число умножить на 2, 3, 4, …, 8, то остаток от деления на 9 полученного числа будет равен 2, 3, …., 8 соответственно и не будет равен 1 – остатку от деления на 9 Васиного числа.