Остатки и делимость по модулю 11

Пусть имеет в своей записи цифру, тогда

где — это какое-то -значное число. Значит, после перестановки 3 в начало мы получим число

По условию получаем равенство

Следовательно, можем понять как выглядит

По условию должно делиться на 99, а следовательно оно делиться на 11. Значит, по признаку делимости на 11, знакопеременная сумма цифр числа должна делиться на 11. Но видно из его записи, когда чётно, то знакопеременная сумма равна 3, когда нечётно, то знакопеременная сумма равна 6. Следовательно, на 11 делиться не может.

В итоге делаем вывод, что чисел, подходящих под условия задачи, не существует.

На этом примере мы вспомним два признака делимости: на 11 и на 9. Для первого слова сразу видно, что вторая его часть получена из первой “переворотом”. Применим признак делимости на 11: число делится на 11 тогда и только тогда, когда знакопеременная сумма его цифр делится на 11. В нашем случае знакопеременная сумма равна

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

Про второе число его важное свойство менее заметно. Но догадаться можно, просто перебирая признаки делимости: ведь мы не верим, что это число будет обязательно делиться на 2 или на 5? Значит, надо думать про делимость на 3 или на 9. И тут мы видим, что все буквы в слове НАХОДЧИВЫЙ различны! Значит, как бы мы ни заменяли буквы цифрами, у нас получится число, в котором по разу встречаются все цифры от 0 до 9, и сумма цифр этого числа будет равна 45. Таким образом, число будет делиться на 9.

Напишем на десяти карточках цифру 2, а на оставшихся девяти — цифру 1. Известно, что натуральное число делится на 11 тогда и только тогда, когда знакочередующаяся сумма , составленная из цифр данного числа, кратна 11. В числе, составленном из десяти цифр 2 и девяти цифр 1, выполняются неравенства . Сумма всех цифр нечётна (она равна 21), поэтому также нечётно. От -7 до 11 есть только одно нечётное число, кратное 11 — это число 11. Но для имеется единственная возможность – когда на нечётных местах стоят двойки, а на чётных – единицы.

Рассмотрим некоторое четырехзначное число без цифр 0 и 9 в десятичной записи. Пусть оно равно . Рассмотрим число . Заметим, что сумма этих двух чисел делится на 101. Оба эти числа четырехзначные и не содержат цифр 0 и 9 в десятичной записи. Таким образом некоторые числа разбились на пары, а некоторое перешли сами в себя. Но любое число, которое перешло само в себя имеет вид , то есть делится на 101. Мы разбили все числа на группы, в каждой из которых сумма делится на 101, но тогда и вся сумма делится на 101.

Разобьем числа на блоки по 2, 3, 5 цифр соответственно. Тогда легко видеть, что каждое число будет делится на свой блок. То есть первое число будет делиться на 11, второе — на 111, третье — на 11111.

Так как число должно делиться на то оно должно делиться на и

делится на при любом выборе поэтому число делится на

По признаку делимости на разность должна делиться на

т.е. должно делиться на

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

Для нахождения достаточно выяснить делимость на числа

1) Делимость на 3 числа возможна в трех случаях:

2) Делимость на 3 числа возможна в трех случаях:

Остальные случаи симметричны рассмотренным. Таким образом, на каждую из найденных пар и приходится по 3 возможных значения

Так как при указанном изменении последней цифры должно получиться число, делящееся на 11 , то искомое число должно отличаться от него на Наименьшее трехзначное число, кратное 11, это 110. Но соседние с ним числа 109 и 111 требуемым свойством не обладают. Действительно, если изменить в числе 109 вторую цифру на 1, то можно получить только 119 , а это число на 11 не делится. Если изменить в числе 111 первую цифру на 1, то можно получить только 211, а это число на 11 не делится.

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

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

• Пусть мы меняем нули на позициях одной чётности. Тогда сумма поставленных нами ненулевых цифр точно не меньше и не больше , а при этом должна быть кратна , поскольку остальные цифры в знакопеременную сумму дают . Отсюда сумма поставленных нами цифр в точности должна быть равна , причём тогда сумма всех цифр будет равна и кратна . Тогда и число будет делиться на . Способов выбрать две позиции одной чётности с учётом порядка (потому что мы будем ставить разные цифры, ведь не делится пополам, а при постановке разных цифр нам уже важно, в каком они стоят порядке: получаются разные числа) будет (первая позиция любая, а вторая из оставшихся позиций той же чётности номера), умножая это на количество разбиений числа в сумму двух цифр уже без учёта порядка (), имеем способов.
• Теперь рассмотрим позиции разной чётности. Теперь из признака делимости на поставленные нами две цифры должны быть равны (чтобы знакочередующаяся сумма цифр давала ноль и делилась на ), а сумма цифр полученного числа будет равна , где , и должна делиться на , отсюда подойдёт только . Осталось выбрать две позиции разной чётности без учёта порядка (ведь мы ставим одинаковые цифры и числа получаются одинаковые, хоть мы поставим , хоть ) способами (первая позиция любая, а вторая любая из позиций с номерами другой чётности).

В качестве ответа имеем .

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

Обозначим через и сумму цифр, стоящих на чётных и нечётных местах соответственно. Из признаков делимости на 9 и на 11 следует, что кратно 9, а кратно 11. Но все цифры чётные, поэтому делится на 18, а — на 22. Также заметим, что . Если , то . Но из этого следует, что , чего не может быть в силу чётности и . Если , то в нашем числе будет не менее 7 цифр, поскольку 8·6 = 48 < 54. Пусть . Тогда или . В первом случае одно из чисел и равно 29, а другое – 7, чего не может быть. Во втором случае . Заметим, что 18 нельзя представить в виде суммы менее чем трёх чётных цифр, поэтому наше число хотя бы шестизначное. Осталось заметить, что наименьшее шестизначное число, удовлетворяющее условиям задачи, — это 228888. Действительно, первая цифра не может быть меньше 2, вторая — тоже, поскольку если она равна 0, то общая сумма цифр не больше .

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

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

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

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

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

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

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

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

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

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

Данное число должно делиться на то есть иметь сумму цифр, кратную и делиться на то есть иметь знакочередующуюся сумму цифр, кратную

Сумма цифр числа равна Значит, то есть или так как и — цифры.

Знакочередующаяся сумма равна

то есть Так как и — цифры, то или Из первого ограничения на и ( или ) мы знаем, что и или разной четности, или одной четности соответственно, а значит, и или и

Тогда

или

Но — цифра, значит, вторая система не имеет решений. Получили единственное решение:

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

Согласно признаку делимости на после го хода на доске возникнет число, кратное тогда и только тогда, когда совпадает с одним из Расположим эти остатки по кругу по часовой стрелке от до и изобразим последовательность ходов как процесс перемещения по кругу по неповторяющимся остаткам При этом первый игрок м ходом "прибавляет"к любое число от до а второй — любое число от до Таким образом, кроме повтора уже встречавшегося остатка, первому игроку запрещён ход против часовой стрелки на а второму — ход по часовой стрелке на После го хода свободными останутся остатков. Игрок гарантированно может сделать ход, если есть хотя бы два свободных остатка, значит, первые восемь ходов игроки сделать смогут, а й ход сделать нельзя никогда.

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

Свободные остатки расположены подряд: Тогда второй выписывает число с остатком (занимает остаток ), первый — а второй и выигрывает.

Остатки расположены так: два рядом — и один отдельно — Тогда второй занимает один из остатков далее либо первый занимает остаток второй — и выигрывает, либо первый занимает а второй — один из оставшихся и выигрывает.

Никакие два остатка не стоят рядом: Тогда второй может занять один из них и после хода первого, второй может занять последний свободный остаток и выиграть.