ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35699
Темы:    [ Группа перестановок ]
[ НОД и НОК. Взаимная простота ]
[ Криптография ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Шифрпреобразование простой замены в алфавите  A = {a1, a2, ..., an},  состоящем из n различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причём разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита A. Если слово СРОЧНО зашифровать простой заменой с помощью ключа:

то получится слово ВЗДАБД. Зашифровав полученное слово с помощью того же ключа еще раз, получим слово ЮШЫЧЯЫ. Сколько всего различных слов можно получить, если указанный процесс шифрования продолжать неограниченно?


Подсказка

Число различных слов, которые можно получить в указанном процессе шифрования с начальным словом СРОЧНО, совпадает с наименьшим номером цикла шифрования, дающем это начальное слово.


Решение

Поскольку разные буквы заменяются разными, то при зашифровании разных слов получаются разные слова. С другой стороны, одинаковые буквы заменяются на одинаковые, следовательно, из одинаковых слов получаются одинаковые. Таким образом, число различных слов, которые можно получить в указанном процессе шифрования с начальным словом СРОЧНО, совпадает с наименьшим номером цикла шифрования, дающего это начальное слово. Так как буква С повторяется в каждом цикле шифрования, номер которого кратен 5, а буквы Р, О, Ч, Н - в каждом цикле, номера которых кратны 13, 7, 2 и 3 соответственно, то слово СРОЧНО появится впервые в цикле с номером, равным  НОК(2, 3, 5, 7, 13) = 2730.


Ответ

2730 слов.

Источники и прецеденты использования

web-сайт
URL cryptography.ru
Название Сайт "Криптография"
задача

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .