1) Дана последовательность чисел С1, С2,.....,Сn,...в которой Сn есть последняя цифра числа n^n. Докажите, что эта последовательность периодическая и ее наименьший период равен 20. 2) Исходное сообщение, состоящее из букв русского алфавита и знака пробела (-) между словами, преобразуется в цифровое сообщение заменой каждого его символа парой цифр согласно тому, что А-01, Б-02,В-03,..(Е=Ё)..(И=Й)...Ш-24, Щ-25, Ь-26, Ы-27,Э-28,Ю-29,Я-30,(-)-31 Для зашифрования полученного цифрового сообщения используется отрезок последовательности С1, С2,.....,Сn,... , начинающийся с некоторого члена Сk. При зашифровании каждая цифра сообщения складывается с соответствующей цифрой отрезка и заменяется последней цифры полученной суммы. Восстановите сообщение: 2339867216458160670617315588

задан 9 Ноя '17 17:23

10|600 символов нужно символов осталось
1

1) Нас интересуют значения n^n по модулю 10, и они станут известны, если найти значения по модулю 2 и по модулю 5. Первое очевидно: там получаются 1, 0, ... с периодом 2. Для второго случая, если n делится на 5, то значение равно нулю. В остальных случаях основание n заменяем остатком от деления на 5, а показатель -- остатком от деления на 4 с учётом малой теоремы Ферма: a^4=1(mod 5) при a не кратном 5. Отсюда ясно, что число 20 будет периодом. То, что оно будет минимальным периодом, следует из того, что ни 20/2=10, ни 20/5=4 периодами не будут, что легко проверить. Второе очевидно сразу, а первое следует из сравнения последних цифр 2^2 и 12^{12}: это 4 и 6 соответственно.

Вычисления последней цифры n^n в пределах первой двадцатки осуществляются несложно. Вот сам период (при n от 1 до 20): 1, 4, 7, 6, 5, 6, 3, 6, 9, 0, 1, 6, 3, 6, 5, 6, 7, 4, 9, 0.

2) Теперь нужно рассмотреть 20 случаев сдвига, беря последовательность длиной 28, по длине сообщения. Далее надо произвести вычитание по модулю 10, и получить в одном из случаев что-то осмысленное. Желательно при этом не перебирать слишком много вариантов. Здесь можно опираться на то, что цифры разгаданного сообщения с нечётными номерами должны принимать значения от 0 до 3.

На мест цифр 2, 3, 8, 7 в сообщении (под номерами 1, 3, 5, 7), может стоять одна из следующих цифр периода соответственно: 9012, 0123, 5678, 4567. Просматривая период, мы сразу видим, что там есть только два места, которые могут подойти: 1, 3, 5, 7 (через один символ) -- если начать читать с позиции k=11, или 9, 1, 7, 5 -- если начать читать с k=19. Но второй вариант не проходит по следующей цифре (номер 9).

Производя вычитание из i-й цифры сообщения (i+10)-ой цифры периодической последовательности, имеем 17, 03, 30, 08, 26, 31, 15, 14, 31, 16, 01, 05, 09, 14. Итоговая расшифровка: "связь по радио".

ссылка

отвечен 9 Ноя '17 18:35

Спасибо большое за решение, но возник вопрос : почему " цифры разгаданного сообщения с нечётными номерами должны принимать значения от 0 до 3" И я не поняла как мы пришли к выводу, что "На мест цифр 2, 3, 8, 7 в сообщении (под номерами 1, 3, 5, 7), может стоять одна из следующих цифр периода соответственно: 9012(?), 0123(?), 5678(?), 4567(?). Просматривая период, мы сразу видим, что там есть только два места, которые могут подойти: 1, 3, 5, 7 (через один символ)(почему именно эти цифры???)"

(10 Ноя '17 16:51) cdtn

@cdtn: коды букв начинаются с 0, 1, 2 или 3. Когда выписывается двузначное число для каждой буквы (в разгаданном сообщении), то на нечётных местах оказываются именно эти цифры.

Смотрим на цифру 2 в зашифрованном сообщении. Она появилась после того, как к цифре от 0 до 3 что-то прибавили. Это что-то могло принимать значения 2, 1, 0, 9. Эти цифры я выписал слитно. Аналогично смотрим, что соответствует другим цифрам.

По последнему: период нам дан, и мы его читаем с какого-то места через цифру. Первая -- из 9, 0, 1, 2. Таких мест немного, остальное не смотрим. Через цифру -- 0, 1, 2, 3, и т.д.

(10 Ноя '17 17:11) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,133
×68
×62
×31
×9

задан
9 Ноя '17 17:23

показан
1160 раз

обновлен
10 Ноя '17 17:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru