За­ме­тим, что (т. к. цифры раз­ные). Кроме того числа и долж­ны да­вать оди­на­ко­вые остат­ки при де­ле­нии на 9. Это воз­мож­но толь­ко тогда, когда крат­но 3. За­ме­тим, что   — не под­хо­дит, т. к.   — дву­знач­ное. Пе­ре­би­рая 12, 15, 18, 21, 24, по­лу­ча­ем

Ответ: 195.

Пусть Тогда все члены по­сле­до­ва­тель­но­сти будут иметь вид Сте­пе­ни будут по­вто­рять­ся с пе­ри­о­дом 6: 0, 0, 1, 2, 2, 1, 0, 0, ... Сте­пе­ни х тоже будут по­вто­рять­ся с пе­ри­о­дом 6: 0, 1, 1, 0, −1, −1, 0, 1, ... По­сколь­ку 2018 дает оста­ток 2 при де­ле­нии на 6, то Чтобы все члены по­сле­до­ва­тель­но­сти были це­лы­ми не­об­хо­ди­мо чтобы k было крат­но x, наи­мень­шее такое k равно 2020.

Ответ: 2020.

Остат­ки от де­ле­ния числа на 7, где при равны 0, 1, 1, 6, 1, 6, 6 со­от­вет­ствен­но. По­это­му остат­ки от де­ле­ния суммы на 7 могут рав­нять­ся толь­ко 0, 1, 2, 5 и 6. При оста­ток от де­ле­ния на 7 пра­вой части дан­но­го урав­не­ния равен 4, зна­чит, Пе­ре­би­рая по­лу­ча­ем ответ.

Ответ:

Пре­об­ра­зу­ем ис­ход­ное вы­ра­же­ние:

По­сколь­ку и то воз­мож­ны сле­ду­ю­щие слу­чаи либо От­ку­да либо

Ответ:

По­сколь­ку

де­лит­ся на 10, то числа и за­кан­чи­ва­ют­ся на одну и ту же цифру, то есть по­сле­до­ва­тель­ность по­след­них цифр дан­ных в усло­вии чисел пе­ри­о­ди­че­ская с пе­ри­о­дом Если вы­пи­сать пер­вые 20 чисел, то их по­след­ние цифры равны: 1, 3, 6, 0, 5, 1, 8, 6, 5, 5, 6, 8, 1, 5, 0, 6, 3, 1, 0, 0. Таким об­ра­зом, 20 это наи­мень­ший пе­ри­од. На этом пе­ри­о­де цифра 5 встре­ча­ет­ся 4 раза. Зна­чит, всего она встре­тит­ся

Ответ: 404.

За­ме­тим, что при Число

де­лит­ся на 18, если сле­до­ва­тель­но, целое число. По­сколь­ку число не­чет­ное, число r долж­но быть чет­ным при Тогда   — целое число.

Пер­вый слу­чай. Если и то

целое при и по­это­му го­дят­ся и Тогда до­пу­сти­мое зна­че­ние остат­ков и

Вто­рой слу­чай. Если то есть то

По­сколь­ку в этом слу­чае k де­лит­ся на 3 (слу­чай 1), ни­ка­ких новых ре­ше­ний для r не воз­ни­ка­ет.

Ответ: и

Solution. As 204 and −5 have the same remainder of division by 19,

Now we proceed in the following way

Raising both sides of the last relation to the power of 224, we get

Multiplying both sides by we finally find that

It means that the remainder of division of by 19 is equal to 8.

В силу того, что 204 и −5 дают оди­на­ко­вые остат­ки от де­ле­ния на 19,

Далее про­дол­жа­ем так:

Воз­во­дя обе части по­след­не­го со­от­но­ше­ния в 224 сте­пень, мы по­лу­ча­ем

Умно­жая обе части на в ко­неч­ном счёте на­хо­дим

Это озна­ча­ет, что оста­ток от де­ле­ния на 19 равен 8.

Ответ: 8.

I спо­соб. При­сво­им цве­там остат­ки от де­ле­ния на 3 про­из­воль­ным об­ра­зом. Все опе­ра­ции с ними также будем про­из­во­дить по мо­ду­лю 3. Тогда опе­ра­ция, про­из­во­ди­мая ро­бо­том, та­ко­ва: если уни­что­жа­ют­ся ку­би­ки цве­тов a и b, то по­яв­ля­ет­ся кубик цвета

Если то после каж­до­го про­хо­да пол­но­го круга ко­ли­че­ство ку­би­ков умень­ша­ет­ся вдвое, а их сумма ме­ня­ет знак. Зна­чит, в конце по­лу­чит­ся кубик цвета вне за­ви­си­мо­сти от места стар­та. Мы до­ка­за­ли, что сте­пе­ни двой­ки удач­ны.

Если где то рас­смот­рим рас­ста­нов­ку из од­но­го крас­но­го ку­би­ка и бе­ло­го. Если робот стар­ту­ет перед крас­ным ку­би­ком, то после d ходов оста­нут­ся один синий кубик и белых. Если робот стар­ту­ет не­по­сред­ствен­но после крас­но­го ку­би­ка, то через d ходов оста­нут­ся один крас­ный кубик и белых. Вы­ше­при­ве­ден­ные ар­гу­мен­ты для сте­пе­ни двой­ки по­ка­зы­ва­ют, что в этих двух си­ту­а­ци­ях ито­го­вые цвета будут раз­ны­ми, то есть N не­удач­но.

Ответ: Сте­пе­ни двой­ки.

II спо­соб. За­ме­тим сразу, что, если чётное число N удач­но, то и тоже. Дей­стви­тель­но, если в рас­ста­нов­ке N ку­би­ков робот будет на­чи­нать толь­ко с чётных по­зи­ций, то после ходов он будет по­лу­чать одну и ту же рас­ста­нов­ку, в ко­то­рой он стоит на все­воз­мож­ных по­зи­ци­ях. По­сколь­ку каж­дая рас­ста­нов­ка ку­би­ков может быть по­лу­че­на таким об­ра­зом, по­лу­ча­ем тре­бу­е­мое.

Рас­смот­рим две рас­ста­нов­ки, от­ли­ча­ю­щи­е­ся ровно в одном месте. За­пу­стим в них по ро­бо­ту па­рал­лель­но; тогда по­лу­ча­ю­щи­е­ся рас­ста­нов­ки все­гда будут от­ли­чать­ся ровно в одном месте. В част­но­сти, ито­го­вые цвета будут раз­лич­ны.

От­сю­да уже сле­ду­ет, что все нечётные (а зна­чит, по за­ме­ча­нию, и все N, кроме сте­пе­ней двой­ки) не­удач­ны. Дей­стви­тель­но, начнём с рас­ста­нов­ки с одним крас­ным и бе­лы­ми ку­би­ка­ми. Если робот стоял перед крас­ным ку­би­ком, через ход оста­нут­ся один крас­ный и белый кубик, робот стоит после крас­но­го. Если же робот стар­ту­ет не­по­сред­ствен­но после крас­но­го, через ход оста­нут­ся один синий и белых ку­би­ков, робот стоит не­по­сред­ствен­но после си­не­го. Как по­ка­за­но выше, ито­го­вые цвета в этих двух си­ту­а­ци­ях будут раз­ны­ми.

По­ка­жем те­перь, что, если N  — сте­пень двой­ки, то ито­го­вый цвет не за­ви­сит от места стар­та. Для этого сде­ла­ем ещё одно на­блю­де­ние по по­во­ду за­ме­ны цвета. Если цвет од­но­го ку­би­ка в рас­ста­нов­ке сме­нить на сле­ду­ю­щий в цик­ли­че­ском по­ряд­ке

то после од­но­го ис­поль­зо­ва­ния цвет сдви­нет­ся в про­ти­во­по­лож­ную сто­ро­ну. Зна­чит, если любая такая за­ме­на ис­ход­но­го ку­би­ка при­ведёт к сдви­гу цвета ито­го­во­го ку­би­ка в одну и ту же сто­ро­ну. Оста­лось за­ме­тить, что две рас­ста­нов­ки, от­ли­ча­ю­щи­е­ся по­во­ро­том, по­лу­ча­ют­ся из рас­ста­нов­ки всех белых ку­би­ков за оди­на­ко­вое ко­ли­че­ство замен «вперёд по циклу».

Как из­вест­но, найдётся такое m, что

По­ло­жим

Тогда

Оста­лось найти ре­ше­ние ука­зан­ной си­сте­мы в целых чис­лах. За­ме­тим, что

По­это­му при все числа будут це­лы­ми. Дей­стви­тель­но, де­лит­ся на   — на   — на и т. д.

Ответ: мог.

Из усло­вия сле­ду­ет, что числа и де­лят­ся на Так как а то

Ответ: 23.

Раз­ло­жим на мно­жи­те­ли: Пер­вый мно­жи­тель дол­жен да­вать оста­ток 1 при де­ле­нии на 3. У числа 72 толь­ко 4 де­ли­те­ля дают такой оста­ток: −8, −2, 1, 4. Они дают 4 ре­ше­ния.

Ответ: 4.

Раз­ло­жим на мно­жи­те­ли: Пер­вый мно­жи­тель дол­жен да­вать оста­ток 1 при де­ле­нии на 3. У числа 180 толь­ко 6 де­ли­те­лей дают такой оста­ток: −20, −5, −2, 1, 4, 10. Они дают 6 ре­ше­ний.

Ответ: 6.

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

За­ду­ма­ем­ся, а су­ще­ству­ет ли такое x₀? Усло­вие рав­но­силь­но квад­рат­но­му урав­не­нию в остат­ках: (в этом аб­за­це все срав­ни­мо­сти по мо­ду­лю 7), эк­ви­ва­лент­но

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

Что же нам дает ра­вен­ство Про­сит­ся от обоих ча­стей взять функ­цию f, а затем вос­поль­зо­вать­ся усло­ви­ем за­да­чи. Имеем:

Чтобы под­черк­нуть по­лу­чен­ное, обо­зна­чим и вы­бро­сим сред­нюю часть: От­сю­да сле­ду­ет (в этом аб­за­це все срав­ни­мо­сти по мо­ду­лю 11), от­ме­тим что это имен­но след­ствие а не рав­но­силь­ность. Вы­яс­ним, имеет ли срав­ни­мость ре­ше­ния, дей­ствуя стан­дарт­но А из­вле­ка­ет­ся ли квад­рат­ный ко­рень из −3 по мо­ду­лю 11? За­ме­тим что

Мы пе­ре­бра­ли все остат­ки, среди квад­ра­тов не на­шлось −3, зна­чит, ко­рень не из­вле­ка­ет­ся, зна­чит, урав­не­ние не имеет ре­ше­ний. Итак, тре­бу­е­мой функ­ции f не су­ще­ству­ет.

Ответ: нет.

Обо­зна­чим число, за­пи­сан­ное на ленте через Любое число при де­ле­нии на 9 даёт такой же оста­ток, как и его сумма цифр. Это озна­ча­ет, что как бы Миша ни раз­ре­зал ленту, сумма двух по­лу­чен­ных чисел будет иметь такой же оста­ток при де­ле­нии на 9, как и число то есть оста­ток все­гда один и тот же для кон­крет­но­го числа а. До­ка­жем вспо­мо­га­тель­ную лемму.

Лемма: если две раз­лич­ные сте­пе­ни семёрки имеют оди­на­ко­вый оста­ток при де­ле­нии на 9, то одно из них боль­ше дру­го­го хотя бы в 343 раза.

До­ка­за­тель­ство: Пусть числа 7^m и 7^k имеют оди­на­ко­вый оста­ток при де­ле­нии на Тогда

от­ку­да Но при это не­вер­но, зна­чит, а зна­чит что и тре­бо­ва­лось до­ка­зать.

Пред­по­ло­жим, что в числе a есть хотя бы 5 цифр Рас­смот­рим сумму чисел при двух раз­ре­зах:

Так как все цифры на ленте не равны нулю, то

За­ме­тим, что

и

По­сколь­ку то

из чего сле­ду­ет, что

С дру­гой сто­ро­ны,

а сле­до­ва­тель­но,

что про­ти­во­ре­чит лемме. Зна­чит, в числе a не более 4 цифр.

Пред­по­ло­жим, что на ленте на­пи­са­но число Оче­вид­но, что

зна­чит, число яв­ля­ет­ся дву­знач­ной сте­пе­нью семёрки, то есть Но число со­сто­ит из трёх или четырёх цифр и от­ли­ча­ет­ся от преды­ду­ще­го хотя бы в 343 раза, то есть оно не мень­ше, чем   — про­ти­во­ре­чие. Зна­чит, в числе a не более 3 цифр. Трёхзнач­ное число, ко­то­рое могло быть за­пи­са­но на ленте, это 445. Дей­стви­тель­но,

Ответ: 3.

За­ме­тим, что Сле­до­ва­тель­но, По­сколь­ку и по­лу­ча­ем, что

От­сю­да Чтобы число де­ли­лось на­це­ло на 12, не­об­хо­ди­мо и до­ста­точ­но, чтобы число k да­ва­ло оста­ток 5 при де­ле­нии на 12, то есть Сле­до­ва­тель­но, По усло­вию по­это­му

Ответ: 37.

По усло­вию

При­рав­няв пра­вые части, най­дем

Чтобы чис­ли­тель по­след­ней дроби де­лил­ся на 77, по­ло­жим Пе­ре­бо­ром или с по­мо­щью ал­го­рит­ма Ев­кли­да легко найти, что Итак, Под­ста­вим это вы­ра­же­ние во вто­рое урав­не­ние (1): По­сколь­ку за­клю­ча­ем, что

Ответ: 29.

За­ме­тим, что для спра­вед­ли­во ра­вен­ство

Кроме того Числа 31 и (−1) при де­ле­нии на 32 дают один и тот же оста­ток 31, то есть (Здесь тра­ди­ци­он­но r₃₂(x)  — оста­ток от де­ле­ния числа x на 32.) Зна­чит,

В ре­зуль­та­те по­лу­ча­ем фор­му­лы, не­по­сред­ствен­но вы­ра­жа­ю­щие ис­ко­мые числа x₀, x₁, x₂, x₃, x₄ через дан­ные в усло­вии y₀, y₁, y₂, y₃, y₄:

От­сю­да на­хо­дим За­шиф­ро­ван­ное слово  — ЛЕМMA.

Ответ: ЛЕМMA.

Если ре­шать за­да­чу пе­ре­бо­ром, то при­дет­ся про­ве­рить 81 пару клю­чей (K₁, K₂). Чтобы пе­ре­бор умень­шить, вос­поль­зу­ем­ся тем, что цифра A может при­ни­мать толь­ко зна­че­ния 0, 1, 2, 3. Для этого вы­ра­зим A (а за­од­но и B) через A₂, B₂, K₁, K₂. По усло­вию

и

(Здесь и далее усло­вим­ся для крат­ко­сти вме­сто пи­сать про­сто то есть рав­ны­ми для нас будут числа, да­ю­щие оди­на­ко­вый оста­ток при де­ле­нии на 10; на­при­мер, От­сю­да

За­ме­тим сразу, что Так как, если то (с цифры 3 на­чи­на­ет­ся толь­ко буква Я). Тогда, со­глас­но (1), но среди цифр A₂ троек нет.

Итак, Сле­до­ва­тель­но, цифры каж­до­го из чисел 59 28 77 64 95 64 90 41 64 удо­вле­тво­ря­ют (со­глас­но (2)) од­но­му из сле­ду­ю­щих ра­венств:

Под­ста­вим в эти ра­вен­ства цифры числа 90 из шифр­тек­ста:

Ра­вен­ство не­воз­мож­но, так как в этом слу­чае Сле­до­ва­тель­но, K₁ не­чет­но, но тогда для (число 95 из шифр­тек­ста) про­из­ве­де­ние K₁, а в левых ча­стях (4) пя­тер­ки нет. По­это­му воз­мож­ны толь­ко два слу­чая 1) или 2) Рас­смот­рим их по­дроб­нее.

Пер­вый слу­чай. При

Со­от­но­ше­ния (4) при­ни­ма­ют вид:

Под­ста­вив в эти со­от­но­ше­ния цифры числа 64, по­лу­чим, что либо  (6)

Для числа 59 из (5) най­дем, что Зна­че­ния 5 и 7 не го­дят­ся, так как они не удо­вле­тво­ря­ют ни од­но­му из ра­венств (6). Таким об­ра­зом, и, так как то удо­вле­тво­ряю или 8.

Вто­рой слу­чай. При

Со­от­но­ше­ния (4) при­ни­ма­ют вид:

Для числа 59 по­лу­ча­ем, что Зна­чит, Ва­ри­ант не го­дит­ся, так как K₁ не­чет­но (из-за того, что Окон­ча­тель­но

Для каж­дой из най­ден­ных пар клю­чей

по фор­му­лам (2), (3) вос­ста­но­вим ис­ход­ный текст. Осмыс­лен­ное слово ОБ­РЕ­ТЕ­НИЕ по­лу­чит­ся для пары (6, 3).

Ответ: ОБ­РЕ­ТЕ­НИЕ.

Если ре­шать за­да­чу пе­ре­бо­ром, то при­дет­ся про­ве­рить 81 пару клю­чей (K₁, K₂). Чтобы пе­ре­бор умень­шить, вос­поль­зу­ем­ся тем, что цифра A может при­ни­мать толь­ко зна­че­ния 0, 1, 2, 3. Для этого вы­ра­зим A (а за­од­но и B) через A₂, B₂, K₁, K₂. По усло­вию

и

(Здесь и далее усло­вим­ся для крат­ко­сти вме­сто пи­сать про­сто то есть рав­ны­ми для нас будут числа, да­ю­щие оди­на­ко­вый оста­ток при де­ле­нии на 10; на­при­мер, От­сю­да

По­сколь­ку цифры каж­до­го из чисел 49 97 32 20 52 77 20 37 85 72 удо­вле­тво­ря­ют (со­глас­но (2)) од­но­му сле­ду­ю­щих че­ты­рех ра­венств:

а) Под­ста­вим в эти ра­вен­ства цифры числа 20 из шифр­тек­ста: и

б) Под­ста­вив в со­от­но­ше­ния (4) цифры числа

с) Ана­ло­гич­но для 52:

Те­перь для каж­до­го зна­че­ния суммы ука­зан­но­го в пунк­те а), най­дем с по­мо­щью (5) со­от­вет­ству­ю­щее зна­че­ние K₁, а потом для пары и K₁ про­ве­рим спра­вед­ли­вость (6).

1)  При Из Зна­че­ния 0 и 4 не го­дят­ся, так как про­из­ве­де­ние K₁K₂ сей­час не­чет­но. Зна­че­ние 7 не удо­вле­тво­ря­ет (6). В итоге нашли одну воз­мож­ную пару клю­чей

2)  При Из Зна­че­ния 1 и 5 оче­вид­но не го­дят­ся (не вы­пол­нит­ся ра­вен­ство Воз­мож­ные пары клю­чей Пара (8,5) не удо­вле­тво­ря­ет (6).

3)  При Из Зна­че­ние 5 оче­вид­но не го­дит­ся (не вы­пол­нит­ся ра­вен­ство Воз­мож­ные пары клю­чей

Усло­вию (6) удо­вле­тво­ря­ют толь­ко пары (2, 2) и (2, 7).

4)  При Из (5) Зна­че­ние 0 и 6 оче­вид­но не го­дят­ся (не вы­пол­нит­ся ра­вен­ство Остав­ши­е­ся воз­мож­ные пары клю­чей обе не удо­вле­тво­ря­ют (6).

Таким об­ра­зом, пред­сто­ит рас­смот­реть сле­ду­ю­щие три пары клю­чей (K₁, K₂): (1, 9), (2, 5), (2, 2) и (2, 7). Для них по фор­му­лам (2), (3) вос­ста­но­вим ис­ход­ный текст. Осмыс­лен­ное слово ХО­ЛЕ­СТЕ­РИН по­лу­чит­ся для пары (2, 7).

Ответ: ХО­ЛЕ­СТЕ­РИН.

Не­труд­но по­нять, что длина слова а также не­слож­но найти оста­ток Пре­об­ра­зу­ем за­шиф­ро­ван­ный текст в по­сле­до­ва­тель­ность чисел:

Из усло­вия сле­ду­ет, что Рас­смот­рим раз­ность

Имеем: За­ме­тим, что От­ку­да на­хо­дим Зна­чит,

Зна­чит, или Рас­смот­рим пер­вый слу­чай. Со­глас­но пра­ви­лу за­шиф­ро­ва­ния

То есть

Ана­ло­гич­но про­дол­жая, по­лу­чим по­сле­до­ва­тель­ность 20, 24, 16, 20, 21, 28, 16. Что со­от­вет­ству­ет не­осмыс­лен­но­му слову ФШР­ФХБР.

Рас­смот­рим вто­рой слу­чай Имеем

Окон­ча­тель­но по­лу­чим, ис­ход­ную по­сле­до­ва­тель­ность чисел 4, 8, 0, 4, 5, 12, 0. Со­глас­но таб­ли­це ей со­от­вет­ству­ет слово ДИА­ДЕ­МА.

Ответ: ДИА­ДЕ­МА.