РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 7592 Добавить в вариант

Шляпник решил отправить по почте Зайцу свой пароль от компьютера (слово из 7-ми букв). Перед отправкой он его зашифровал следующим образом. Каждую букву слова он заменил пятизначной комбинацией в соответствии с таблицей из задачи 6 (считается, что $Е=\ddot E правая круглая скобка .$ Данные из таблицы считываются сверху вниз. Так, например, буква Б заменяется на $00001 .$ В результате у него получилась последовательность a₁, ..., a₃₅, где $a_i принадлежит левая фигурная скобка 0; 1 правая фигурная скобка .$ Затем Шляпник построил еще одну последовательность y₁, ..., y₃₅, также состоящую из 0 и 1. Он наугад записал первые четыре члена последовательности y₁, y₂, y₃, y₄ и выбрал четыре неотрицательных целых числа c₁, c₂, c₃, c₄. Оставшиеся члены последовательности y₅, ..., y₃₅ он подсчитал по формуле

$y_n плюс 4=r_2 левая круглая скобка c_1 y_n плюс c_2 y_n плюс 1 плюс c_3 y_n плюс 2 плюс c_4 y_n плюс 3 правая круглая скобка ,$

где r₂(b)  — остаток от деления числа b на 2. Затем он вычислил $b_i=r_2 левая круглая скобка a_i плюс c_i правая круглая скобка ,$ $i=1, \ldots, 35.$ Получившуюся последовательность b₁, ..., b₃₅. Шляпник разбил на фрагменты длиной 5, каждый из которых он преобразовал в буквы согласно таблице. Заяц получил строку ГОШРОХБ. Помогите ему определить пароль.

Спрятать решение

Решение.

Поскольку

$r_2 левая круглая скобка a умножить на b правая круглая скобка =r_2 левая круглая скобка r_2 левая круглая скобка a правая круглая скобка умножить на r_2 левая круглая скобка b правая круглая скобка правая круглая скобка ,$ $r_2 левая круглая скобка a плюс b правая круглая скобка =r_2 левая круглая скобка r_2 левая круглая скобка a правая круглая скобка плюс r_2 левая круглая скобка b правая круглая скобка правая круглая скобка ,$

можно далее считать, что числа $c_0, c_1, c_2, c_3 принадлежит левая фигурная скобка 0, 1 правая фигурная скобка .$ Представим первые две буквы полученной строки в виде последовательности b₁, ..., b₁₀: 0001101110. Тогда, предположив, что первые буквы пароля это «РЕ», получим, что a₁, ..., a₁₀: 1000000101, и можно вычислить y₁, ..., y₁₀:

$b_i=r_2 левая круглая скобка y_i плюс a_i правая круглая скобка равносильно y_i=r_2 левая круглая скобка b_i плюс a_i правая круглая скобка .$

Получим 1001101011. Используя рекуррентную формулу для членов последовательности y₅, ..., y₁₀, придем к системе уравнений

$система выражений y_5=r_2 левая круглая скобка c_0 y_1 плюс c_1 y_2 плюс c_2 y_3 плюс c_3 y_4 правая круглая скобка , y_6=r_2 левая круглая скобка c_0 y_2 плюс c_1 y_3 плюс c_2 y_4 плюс c_3 y_5 правая круглая скобка , y_7=r_2 левая круглая скобка c_0 y_3 плюс c_1 y_4 плюс c_2 y_5 плюс c_3 y_6 правая круглая скобка , y_8=r_2 левая круглая скобка c_0 y_4 плюс c_1 y_5 плюс c_2 y_6 плюс c_3 y_7 правая круглая скобка конец системы . равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_2 правая круглая скобка , 0=r_2 левая круглая скобка c_0 плюс c_1 плюс c_3 правая круглая скобка конец системы . равносильно$
$равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_0 плюс c_1 плюс c_3 правая круглая скобка конец системы . равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_0 правая круглая скобка конец системы . равносильно система выражений 0 = r_ 2 левая круглая скобка c_ 3 правая круглая скобка , 0 = r_ 2 левая круглая скобка c_ 2 плюс c_ 3 правая круглая скобка , 1 = r_ 2 левая круглая скобка c_ 1 плюс c_ 3 правая круглая скобка , 1 = r_ 2 левая круглая скобка c_ 0 правая круглая скобка конец системы . равносильно система выражений 0=r_2 левая круглая скобка c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 правая круглая скобка , 1=r_2 левая круглая скобка c_1 правая круглая скобка , 1=r_2 левая круглая скобка c_0 правая круглая скобка . конец системы .$ $система выражений y_5=r_2 левая круглая скобка c_0 y_1 плюс c_1 y_2 плюс c_2 y_3 плюс c_3 y_4 правая круглая скобка , y_6=r_2 левая круглая скобка c_0 y_2 плюс c_1 y_3 плюс c_2 y_4 плюс c_3 y_5 правая круглая скобка , y_7=r_2 левая круглая скобка c_0 y_3 плюс c_1 y_4 плюс c_2 y_5 плюс c_3 y_6 правая круглая скобка , y_8=r_2 левая круглая скобка c_0 y_4 плюс c_1 y_5 плюс c_2 y_6 плюс c_3 y_7 правая круглая скобка конец системы . равносильно$
$равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_2 правая круглая скобка , 0=r_2 левая круглая скобка c_0 плюс c_1 плюс c_3 правая круглая скобка конец системы . равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_0 плюс c_1 плюс c_3 правая круглая скобка конец системы . равносильно$
$равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_0 правая круглая скобка конец системы . равносильно система выражений 0 = r_ 2 левая круглая скобка c_ 3 правая круглая скобка , 0 = r_ 2 левая круглая скобка c_ 2 плюс c_ 3 правая круглая скобка , 1 = r_ 2 левая круглая скобка c_ 1 плюс c_ 3 правая круглая скобка , 1 = r_ 2 левая круглая скобка c_ 0 правая круглая скобка конец системы . равносильно система выражений 0=r_2 левая круглая скобка c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 правая круглая скобка , 1=r_2 левая круглая скобка c_1 правая круглая скобка , 1=r_2 левая круглая скобка c_0 правая круглая скобка . конец системы .$ $система выражений y_5=r_2 левая круглая скобка c_0 y_1 плюс c_1 y_2 плюс c_2 y_3 плюс c_3 y_4 правая круглая скобка , y_6=r_2 левая круглая скобка c_0 y_2 плюс c_1 y_3 плюс c_2 y_4 плюс c_3 y_5 правая круглая скобка , y_7=r_2 левая круглая скобка c_0 y_3 плюс c_1 y_4 плюс c_2 y_5 плюс c_3 y_6 правая круглая скобка , y_8=r_2 левая круглая скобка c_0 y_4 плюс c_1 y_5 плюс c_2 y_6 плюс c_3 y_7 правая круглая скобка конец системы . равносильно$
$равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_2 правая круглая скобка , 0=r_2 левая круглая скобка c_0 плюс c_1 плюс c_3 правая круглая скобка конец системы . равносильно$
$равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_0 плюс c_1 плюс c_3 правая круглая скобка конец системы . равносильно система выражений 1=r_2 левая круглая скобка c_0 плюс c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_1 плюс c_3 правая круглая скобка , 1=r_2 левая круглая скобка c_0 правая круглая скобка конец системы . равносильно$
$равносильно система выражений 0 = r_ 2 левая круглая скобка c_ 3 правая круглая скобка , 0 = r_ 2 левая круглая скобка c_ 2 плюс c_ 3 правая круглая скобка , 1 = r_ 2 левая круглая скобка c_ 1 плюс c_ 3 правая круглая скобка , 1 = r_ 2 левая круглая скобка c_ 0 правая круглая скобка конец системы . равносильно система выражений 0=r_2 левая круглая скобка c_3 правая круглая скобка , 0=r_2 левая круглая скобка c_2 правая круглая скобка , 1=r_2 левая круглая скобка c_1 правая круглая скобка , 1=r_2 левая круглая скобка c_0 правая круглая скобка . конец системы .$

В силу отмеченного ранее можно считать, что $c_0=1,$ $c_1=1,$ $c_2=0,$ $c_3=0.$ Тогда закон рекурсии для последовательности y₁, ..., y₃₅ имеет вид:

$y_n плюс 4=r_2 левая круглая скобка y_n плюс y_n плюс 1 правая круглая скобка .$

Теперь, используя фрагмент последовательности y₁, ..., y₁₀ можно вычислить и всю оставшуюся последовательность y₁₁, ..., y₃₅:

1100010011010111100010011.

Для нахождения пароля остается преобразовать буквы полученной строки в последовательность из 0 и 1, а затем воспользоваться формулой: $a_ i = r_2 левая круглая скобка y_ i плюс b_ i правая круглая скобка .$ Получим строку a₁₁, ..., a₃₅:

0000000011001010110110010,

преобразовывая которую согласно таблице, придем к последовательности букв АГЕНТ. В итоге искомым паролем является слово РЕАГЕНТ.

Ответ: PEAГЕНT.

Межрегиональная олимпиада школьников им. И. Я. Верченко, 10 класс, 2 тур (заключительный), 2017 год

Классификатор: Анализ. Последовательности

Спрятать решение · Помощь