|
|
 |
Условие
Дима придумал секретный шифр: каждая буква заменяется на слово длиной не больше 10 букв. Шифр называется хорошим, если всякое зашифрованное слово расшифровывается однозначно. Серёжа убедился (с помощью компьютера), что если зашифровать слово длиной не больше 10000 букв, то результат расшифровывается однозначно. Следует ли из этого, что шифр хороший? (В алфавите 33 буквы, под "словом" мы понимаем любую последовательность букв, независимо от того, имеет ли она смысл.)
Решение
Предположим, что это не так: некоторые шифровки декодируются неоднозначно. Выберем самую короткую такую шифровку. По условию в ней более 10000 букв.
Назовём полусловом несколько (но не ноль и не все) первых букв слова, кодирующего букву. Ясно, что различных полуслов не больше чем
9·33 = 297.
Декодирование шифровки определяется позициями между буквами, в которых она делится на слова, кодирующие буквы. Отметим эти позиции в первом случае красным, а во втором – синим цветом (красные и синие разделители нигде не совпадают, иначе можно было бы отбросить часть шифровки до или после этих разделителей, получив более короткую "неоднозначную" шифровку). Рассмотрим для каждого красного разделителя слово, образованное этим разделителем и последним синим разделителем, стоящим перед этим красным (или началом шифровки, если таких синих разделителей нет). Ясно, что это полуслово. Какие-то два таких полуслова совпадают (шифрующих слов у нас не менее 1001, поэтому красных разделителей – не менее 1000 > 297). Значит, кусок между соответствующими красными разделителями можно выкинуть, получив новую (более короткую) "неоднозначную" шифровку. Противоречие.
Ответ
Следует.
Замечания
8 баллов
