Признаки делимости и равноостаточности → .01 Остатки и делимость по модулю степеней двойки или пятёрки

Будем последовательно выбирать цифры от первого места к последнему.

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

• Если то или
• Если то или
• Если то или
• Если то или
• Если то или

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

Если кратно , то чётно, то есть , откуда кратно , что равносильно делимости на . В частности, отсюда следует, что кратно , откуда , а значит . Таким образом,

откуда кратно , кратно , то есть .

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

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

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

С одной стороны, это число оканчивается на цифру , то есть делится на . С другой, число дает при делении на такой же остаток, что и число, образованное последними двумя цифрами. В нашем случае число, образованное последними двумя цифрами, — это . Оно не делится на , значит, и исходное число не делится на . Итак, число делится на , но не делится на .

Заметим, что если число квадрат, то простые числа входят в него в четной степени. Значит, если квадрат делится на 5, то делится и на 25. Но перед нами число, которое делится на и не делится на . Значит, оно не квадрат.

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

Это число даёт остаток при делении на , однако квадраты могут быть сравнимыми только с по модулю , значит, искомое число не квадрат.

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

Предположим, что такое число существует. Тогда кратно 12, а значит, и 4. По признаку делимости на 4 кратно 4. Аналогично из того, что кратно 24, следует, что кратно 4. Значит, и делится на 4, что не так.

Делимость числа на 125 определяется тремя его последними цифрами. Следовательно, годится число .

Предположим, что и — удачные числа. В записи этих чисел не может быть цифры 0 (на 0 делить нельзя), поэтому, эти числа отличаются только последней цифрой, следовательно, одно из них оканчивается либо на 4, либо на 8. Далее можно рассуждать по-разному.

Первый способ. Пусть — произведение первых шести цифр числа . Так как соседние числа и взаимно просты и оба делятся на , то . Следовательно, каждая из первых шести цифр числа равна 1. Но число не делится на 4, а число 1111118 не делится на 8. Противоречие.

Второй способ. Среди этих четырёх чисел есть нечётные. Поскольку они делятся на произведение своих цифр, то все их цифры нечётны. Следовательно, первые шесть цифр каждого из четырёх чисел — нечётные. Но числа, оканчивающееся на или , где — нечётная цифра, не делятся на 4. Противоречие.

На что нам намекает условие этой задачи? Оканчиваться на 4 одинаковые цифры: с этим связан признак делимости на . При этом степень двойки, конечно, на 16 делится. А делится ли на 16 число, оканчивающееся на 4 одинаковые цифры? По признаку равноостаточности, можно посмотреть только на число, образованное последними 4 цифрами, пусть это . Но и 16 взаимно просты, значит, должно делиться на 16. Так как — цифра, то может быть равно только 0. Но на 0 степени двойки не заканчиваются, хотя бы потому, что степени двойки не делятся на 10.

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

Заметим, что если число квадрат, то простые числа входят в него в четной степени. Значит если квадрат делится на 5, то делится и на 25, но перед нами число, которое делится на 5 и не делится на 25. Значит оно не квадрат.

Число, которое делится на , должно оканчиваться на или на . Зеркальное число оканчиваться на не может, так как тогда оно должно и начинаться на . Итак, первая и последняя цифры — это . Вторая и третья цифра могут быть любыми — от сочетания до сочетания — всего вариантов. Так как четвертая цифра повторяет вторую, всего различных чисел будет .

По условию, эти числа записываются только цифрами Тогда трехзначные числа, кратные могут иметь на конце в точности вариантов: При этом на первом месте в каждом из этих вариантов может стоять одна из возможных цифр: В случае, если число двузначное, имеем вариантов. А также — однозначное натуральное число, кратное Итого,

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

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

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

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

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

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

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

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

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

Данные числа, расположенные в порядке возрастания, образуют арифметическую прогрессию с разностью 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 способов.

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

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

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

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

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

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

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

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