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

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

Пусть Аня первым ходом выберет цифру , а вторым ходом - цифру 9. Если Боря на первом или втором ходу выберет цифру из множества , то своим третьим ходом Аня заберет последнюю оставшуюся цифру из множества , и Боря вынужден будет взять свою цифру из , что приведет к его проигрышу. Значит, Боря вынужден взять первые две свои цифры и взяты из множества . Заметим, что Боря вынужден будет на последнем ходе выбрать либо цифру 1 , либо цифру 7 , которые дают одинаковый остаток 1 при делении на 3. Поэтому Ане достаточно подобрать цифру так, чтобы сумма цифр давала бы остаток 2 при делении на 3 . Поскольку и не влияют на остаток этой суммы, все зависит от остатка суммы . Покажем, как действовать Ане в каждом из случаев.

Если делится на 3 , то Аня выберет цифру из набора : поскольку до этого момента эти цифры мог выбирать только Боря, как минимум одна из этих трех цифр останется не выбранной.

Если дает остаток 1 при делении на 3 , Аня выберет цифру . Как мы помним, Боря не мог ее выбрать на первых двух ходах.

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

Таким образом, Аня выиграет.

Среди последовательных чисел на делится или Пусть среди Петиных чисел, делящихся на ровно под подписаны Васины числа, делящиеся на Тогда произведений, делящихся на будет не меньше, чем Это сами перемноженных чисел и оставшиеся числа делящиеся на в каждой из строчек. Если у Яны получилось последовательных натуральных чисел, число должно быть не больше откуда хотя бы Но тогда среди Яниных чисел будет хотя бы таких, которые делятся на а чисел, делящихся на среди двухсот последовательных натуральных чисел не больше -ёх. Противоречие.

Воспользуемся тем, что натуральное число даёт такой же остаток при делении на 9 как и у суммы цифр этого числа. Пусть количество цифр 5 в числе равно тогда количество цифр 4 равно и нечётно. Теперь посчитаем сумму цифр этого числа:

Тогда остаток при делении на 9 равен 4.

Сумма цифр числа даёт такой же остаток при делении на , что и само число. Поэтому если число имеет ненулевой остаток при делении на , то после сложения с суммой его цифр не получится кратное трём число: (mod ).

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

Давайте введём симметричные обозначения для девяти последовательных чисел: пусть первое число равно , тогда сумма

Заметим, что делится на , и значит, сумма цифр числа

должна делиться на . Тогда сумма оставшихся цифр хотя бы , и поэтому минимальное число . Для него подходит (досчитывать на олимпиаде необязательно, но нужно пояснить, почему это число целое и почему подходит).

При число делится на тогда и его сумма цифр делится на Предположим, что десятичная запись состоит из одних троек, тогда количество троек в записи делится на Значит, наше число делится на (каждый “блок” из троек делится на то есть и на поэтому число не является степенью тройки — противоречие.

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

Обозначим наше число через . Распишем его как сумму степеней десятки, умноженную на соответствующий разряд:

Заметим, что число в любой степени дает остаток при делении на и . Поэтому любое слагаемое, например , дает такой же остаток, что и просто цифра . Значит, всё число дает такой же остаток при делении на и , что и , то есть сумма цифр.

Комментарий. Разумеется, количество разрядов в числе не важно. Мы доказываем признак равноостаточности для четырехзначных чисел, чтобы нам не пришлось использовать слишком общие рассуждения.

Посчитаем сумму цифр числа без звездочки, у нас получится 40. Ближайшие числа, большие 40 и делящиеся на 3, — это 42, 45 и 48. Сумма цифр не может быть больше или равна 50, так как нет цифр, больших 9. Поэтому все варианты цифры, которую можно написать вместо звездочки, — это 2, 5 или 8.

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

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

Чтобы результат делился на 18, он должен делиться на 9 и на 2. Рассмотрим сначала делимость на 9. Чтобы результат делился на 9, сумма его цифр также должна делиться на 9. У исходного числа сумма цифр равна 4. Сумму цифр 18 и более, приписав лишь одну цифру, получить не получится, значит, чтобы получить сумму, делящуюся на 9, можно приписать только цифру 5. Итак, для делимости на 9 справа необходимо приписать цифру 5. Но число 20205 не будет делиться на 18, так как оно нечетное. Значит, приписать к числу 2020 одну цифру справа так, чтобы результат делился на 18, нельзя.

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

Этого можно добиться, только прибавив цифру : ближайшее число, большее , делящееся на , — , и как раз его мы и получим. А суммы больше получить нельзя, так как мы прибавляем цифру, и ее значение меньше . Значит, на месте звездочки находилась цифра .

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

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

Далее, мы из числа, делящегося на 9, будем вычитать сумму его цифр, которая также по признаку делимости делится на 9. Таким образом, число на доске после первого действия и до самого конца будет делиться на 9. Значит, и появившееся однозначное ненулевое число делится на 9. Такое число всего одно — это само число 9. Поэтому именно оно и будет написано на доске, когда Дмитрий Алексеевич перестанет заниматься своим бесполезным делом.

Обозначим делимое через а сумму его цифр через Тогда должно быть верно равенство

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

Число поэтому мы можем отдельно воспользоваться признаками делимости на 9 и на 25.

Начнем с признака равноостаточности при делении на 25: число дает такой же остаток при делении на 25, что и число, образованное его последними двумя цифрами. В нашем случае, чтобы число делилось на 25, оно должно оканчиваться либо на 00, либо на 25, либо на 50, либо на 75. Так как по условию число состоит только из нулей и единиц, подходит лишь 00. Итак, мы выяснили, что число оканчивается на 00.

Теперь, определив однозначно последние две цифры, чтобы сделать число минимальным, нужно минимизировать число без двух последних цифр. Воспользуемся признаком равноостаточности при делении на 9: число дает такой же остаток при делении на 9, что и его сумма цифр. В нашем случае необходимо, чтобы число делилось на 9, поэтому и сумма цифр должна делиться на 9. Нули в записи не меняют сумму цифр числа, поэтому сумму цифр, делящуюся на 9, мы можем получить только из единиц. Если сумма цифр числа будет 18 или больше, то нам придется использовать хотя бы 18 единиц, и тогда в числе будет 20 или больше знаков, а у нас есть пример на меньшее число. Если сумма цифр числа равна 9, то нужно использовать девять единиц. Так как наличие нулей в записи на делимость не повлияет, но лишь увеличит количество знаков в числе, а значит и его значение, то минимальным подходящим числом является 111111111. Приписав к этому числу два нуля в конец, мы получаем искомый ответ.

Замечание. Обратите внимание на два важных момента. Во-первых, мы можем минимизировать число без двух последних цифр только потому, что они определились однозначно. Если бы у нас получилось несколько вариантов последних двух цифр, то мы бы не могли так просто их отбросить, пришлось бы рассматривать несколько случаев и в каждом искать минимум, а уже потом выбирать самое маленькое число.

Во-вторых, было бы грубой ошибкой написать, что число тем меньше, чем меньше его сумма цифр. Это не правда: но Обратите внимание, как мы обошли эту проблему при написании решения: мы отдельно сказали, что случай с суммой цифр 18 или более нам не подходит, так как у нас есть пример на меньшее количество знаков. А уже потом объяснили, почему при сумме цифр 9 наше число минимальное.

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

Далее, после того, как число поделили на , его сумма цифр по прежнему равна , то есть делится на . Значит, после того, как число поделили на , оно всё еще делится на . Это означает, что исходное число делилось на . Тогда и сумма цифр исходного числа делилась на . Итак, делится на .

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

Замечание. Приводить пример таких чисел, конечно, не требуется, но сказанное в условии вполне возможно: например, .

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

Разложим . Пусть число (наш ответ), состоящее из единиц делится на оба множителя (это необходимое и достаточное условие, так как эти два множителя взаимно просты). Деля его на в столбик, видно, что делится на (каждый раз сносится по единиц). Кроме того, из признака делимости на следует, что кратно . Значит, минимальное . Заметим, что оно подходит: делится на (в столбик видно) и на по признаку делимости.