Остатки и делимость по модулю степеней двойки или пятёрки

Пусть — данное число, — его остаток от деления на и от деления на Тогда число делится на и на то есть делится на

Значит, разность оканчивается либо на либо на А остаток Поэтому цифра в разряде тысяч может быть или Обе ситуации возможны, такие цифры имеют, например числа и (оба этих числа имеют остатки при делении на и на ).

Так как число четырёхзначное, то его сумма цифр не больше , а раз она делится на , то она в точности равна .

Число делится на поэтому может оканчиваться на , , или .

Если оно оканчивается на , то его сумма цифр не превосходит — не подходит.

Если оканчивается на , то его сумма цифр не превосходит — не подходит.

Если оно оканчивается на , то сумма двух первых цифр должна быть равна . Но тогда это могут быть только две цифры . Произведение цифр числа не делится на .

Получается, что восхитительное число может оканчиваться только на . Тогда сумма его первых двух цифр равна , причём одна из них должна быть равна , значит, вторая — . Оба числа и подходят.

Поскольку то сумма квадратов всех чисел на доске увеличивается в два раза с каждым ходом. Из формулы

ясно, что сумма квадратов последовательных целых чисел даёт остаток при делении на Значит, сумма квадратов последовательных целых чисел тоже даёт остаток при делении на

Таким образом, после первого хода сумма квадратов чисел на доске всегда будет делиться на и, следовательно, на доске никогда больше не появятся последовательных целых чисел.

Данные числа, расположенные в порядке возрастания, образуют арифметическую прогрессию с разностью 3. Следовательно, остатки от деления на 5 у этих чисел чередуются. Действительно, если какое-то из этих чисел делится на 5, то есть имеет вид , где , то следующее за ним число есть — и оно даёт остаток 3 от деления на 5 — далее , дающее остаток 1 от деления на 5, затем — , дающее остаток 4 от деления на 5 , затем , дающее остаток 4 от деления на 5; наконец, следующим является , которое снова делится на 5, после чего порядок остатков по чисел на 5 идут в порядке

Среди данных нам 100 чисел есть по 20 чисел, дающих остатки от деления на 5.

Сумма двух чисел может делиться на 5 в следующих случаях.

1) Оба числа делятся на 5. Всего карточек с такими числами 20 , и нужно выбрать 2 из них — есть способов.

сделать это.

2) Одно из чисел даёт остаток 1 от деления на 5 — тогда второе должно давать остаток 4 от деления на 5. Эту пару чисел можно выбрать способами.

3) Одно из чисел даёт остаток 2 от деления на 5 — тогда второе даёт остаток 3 , и, аналогично второму случаю, получаем 400 способов выорать 2 числа. В итоге выходит 990 способов.

Сначала заметим, что среди трехзначных чисел без нулей в записи хотя бы четных, значит, произведение чисел на карточках делится на Покажем, что оно также делится на после чего сможем сделать вывод, что оно делится на а значит, -я справа цифра ноль.

Во-первых, все числа, оканчивающиеся на дадут в произведение хотя бы одну пятерку. Таких чисел Кроме того, еще хотя бы по одной пятерке дадут числа причем хоть мы уже и считали один раз число оно даст две пятерки, поэтому здесь мы его тоже сосчитаем. В итоге получается еще пятерок, всего что и требовалось.

Переформулируем задачу: нам надо найти наименьшее натуральное число записываемое только нулями и единицами, делящееся на Тогда мы поделим его на и узнаем ответ.

Убедимся, что число подходит. Во-первых, так как число делится на то число, образованное его двумя последними цифрами, делится на Из чисел подходит только

Во-вторых, так как число делится на то в нем не менее трех единиц. А наименьшее число, содержащее три единицы и оканчивающееся на два нуля — это как раз Откуда получаем ответ

Докажем методом от противного, пусть такое бывает. В выражении каждая сумма из двух слагаемых участвует ровно один раз. Среди попарных сумм чисел ровно две делятся на но при этом только одна делится на Следовательно, где бы они не находились, одно произведение будет делиться на а другое не будет.

Замечание. Также можно решить задачу по модулю или

Пусть сторона квадрата тогда суммарный периметр прямоугольников будет С другой стороны, сумма четырех подряд идущих чисел не делится на так как они будут давать всевозможные остатки при делении на и сумма этих остатков что не делится на 

Первое решение.

После разложения на взаимнопростые множители нужно использовать критерии делимости для старого и нового (после вставки двух нулей) чисел.

) Сумма цифр при вставке двух нулей не меняется, поэтому не меняется и делимость на

) Знакопеременная сумма цифр также не меняется, поэтому не меняется и делимость на (или можно сказать, что суммы цифр на чётных и нечётных местах остались равны).

) Последняя цифра не изменилась, так как нули вставляют между цифрами, поэтому не изменилась и делимость на

Второе решение.

Обозначим число до вставленных цифр, у которого следующие цифры сделаем нулями, через (сразу заметим, что делится на , потому что у этого числа на конце нули), после — через

Тогда исходное число это а новое число равно

Из замеченной делимости на следует делимость числа на а это исходное число, которое тоже делится на по условию.

В итоге и полученная сумма делится на

Из первого условия нечётных чисел не более . Из второго условия чётных чисел не более . Поскольку всего чисел , то нечётных должно быть ровно . Сумма всех чисел это сумма чётных и нечётного числа нечётных, следовательно, она нечётна и не может равняться

Рассмотрим первые пять из этих семи чисел. Заметим, что разности между ними не меньше 1 и не больше 4, то есть не делятся на 5. Значит, эти числа дают разные остатки при делении на 5. Но так как чисел 5 штук, и остатков тоже 5, то эти пять чисел дают все возможные остатки при делении на 5, в том числе остаток 0. Значит, среди любых пяти последовательных чисел есть число, делящееся на 5. Тогда и среди семи последовательных чисел тем более есть число, делящееся на 5. Поэтому их произведение должно делиться на 5. Но число 123456789101112 не делится на 5, так как заканчивается не на 0 и не на 5, противоречие.

Натуральное число дает при делении на 4 такой же остаток, что и число, образованное последними двумя цифрами. Натуральное число, записываемое одними двойками, кроме числа 2, оканчивается на 22. Это число дает остаток 2 при делении на 4, то есть на 4 не делится. Число 2 также не делится на 4, значит, никакое число, записываемое только двойками, не делится на 4.

Меж тем любое число, записываемое одними четверками, кроме самого числа 4, оканчивается на 44, и по признаку делимости на 4 делится на 4. Само число 4 также, естественно, делится на 4. Итак, любое число, записываемое одними четверками, делится на 4. Но число, не делящееся на 4 (то есть число, записываемое одними двойками), не может делиться на число, которое делится на 4 (то есть число, записываемое одними четверками).

Произведение всех двузначных чисел, оканчивающихся на 5, делится на 25 (например, потому, что среди перемножаемых чисел есть само число 25). Посмотрим на результат Васи. Число, образованное последними двумя цифрами — это 65. Оно дается остаток 15 при делении на 25, то есть не делится на 25. С другой стороны, натуральное число дает такой же остаток при делении на 25, что и число, образованное последними двумя цифрами. В нашем случае получается, что Васин результат не делится на 25. Значит, Вася ошибся.