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

Заметим, что число имеет вид откуда сумма цифр этого числа равна двум, то есть оно не кратно 9. При это число имеет вид откуда оно кратно 9.

Число, не делящееся на 9, не может делиться на число, кратное 9. Значит, не делится на при любых натуральных и

Запишем десятичную запись числа :

Так как сумма цифр делится на 9, само число также делится на 9.

Рассмотрим несколько самых маленьких чисел с суммой цифр 27 и проверим их делимость на 27:

Видим, что число 1899 не делится на 27, хотя сумма его цифр кратна 27, следовательно, Лосяш не прав.

Пусть — некоторое число, а — сумма его цифр. Так как сумма цифр числа 3804 равна , число 3804 делится на 3, но не делится на 9. Тогда какое-то одно из чисел и должно делиться на 3, а второе нет, но если делится на 3, то и тоже, если же делится на три, то и будет делиться на 3. В обоих случаях, произведение будет делиться на 9, что противоречит условию.

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

Эта сумма должна делиться на 3, так как 21 делится на 3, также должен делиться на 3.

По условию задачи то есть Единственное число, удовлетворяющее этому условию и кратное 3, — это 6. Таким образом, в пинкоде 6 двоек и 1 тройка. Эту тройку мы можем разместить на любой из семи позиций, а остальные заполнить двойками, так что Пину нужно перебрать всего 6 кодов.

Так как число делится на сумма цифр также должна делиться на Вычислим сумму цифр:

Ближайшее к 55 число, кратное девяти — это 63, в этом случае Очевидно, что это единственно возможный вариант, так как может принимать значения только от 0 до 9.

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

Поймем какой остаток дает при делении на Заметим

В силу цикличности, нечетные степени дают остаток

Т.к. итоговое число состоит из одной цифры и дает остаток при делении на это число —

Пусть - итоговое шестизначное число. Пусть также и . Заметим, что если Боря своим третьим ходом поставит цифру из множества , Аня выиграет, поскольку полученное число будет делиться на 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. Поэтому именно оно и будет написано на доске, когда Дмитрий Алексеевич перестанет заниматься своим бесполезным делом.