Задача 35699

Темы:    [ Группа перестановок ] [ НОД и НОК. Взаимная простота ] [ Криптография ]

Сложность: 4- Классы: 9,10,11

Условие

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

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

Подсказка

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

Решение

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

Ответ

2730 слов.

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

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