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

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

Условие

При установке кодового замка каждой из 26 латинских букв, расположенных на его клавиатуре, сопоставляется произвольное натуральное число, известное лишь обладателю замка. Разным буквам сопоставляются не обязательно разные числа. После набора произвольной комбинации попарно различных букв происходит суммирование числовых значений, соответствующих набранным буквам. Замок открывается, если сумма делится на 26. Докажите, что для любых числовых значений букв существует комбинация, открывающая замок.


Подсказка

Докажите, что искомая комбинация может быть найдена как несколько последовательных букв алфавита.


Решение

Обозначим через S(n) остаток от деления на 26 суммы чисел, которые соответствуют первым n буквам алфавита  (n = 1, 2, ..., 26).  Если среди чисел S(1), S(2), ..., S(26) есть нуль:  S(t) = 0,  то искомой ключевой комбинацией является цепочка первых t букв алфавита. Если среди чисел S(1), S(2), ..., S(26) нет нуля, то найдутся два одинаковых числа:  S(k) = S(m)  (считаем, что  k < m).  Тогда искомой ключевой комбинацией является участок алфавита, начинающийся с (k+1)-й и заканчивающийся m-й буквой.

Замечания

Ср с задачей 103964.

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

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

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

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