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

Проект МЦНМО
при участии
школы 57
Задача 98375
Темы:    [ Криптография ]
[ Принцип Дирихле (прочее) ]
[ Доказательство от противного ]
[ Принцип крайнего (прочее) ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Дима придумал секретный шифр: каждая буква заменяется на слово длиной не больше 10 букв. Шифр называется хорошим, если всякое зашифрованное слово расшифровывается однозначно. Серёжа убедился (с помощью компьютера), что если зашифровать слово длиной не больше 10000 букв, то результат расшифровывается однозначно. Следует ли из этого, что шифр хороший? (В алфавите 33 буквы, под "словом" мы понимаем любую последовательность букв, независимо от того, имеет ли она смысл.)


Решение

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


Ответ

Следует.

Замечания

8 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 1997/1998
Номер 19
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 5

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

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