Архив задач олимпиады по математике и криптографии
Кодовый замок
При установке кодового замка каждой из 26 латинских букв, расположенных на его клавиатуре, сопоставляется произвольное натуральное число, известное лишь обладателю замка. Разным буквам сопоставляются не обязательно разные числа. После набора произвольной комбинации попарно различных букв происходит суммирование числовых значений, соответствующих набранным буквам. Замок открывается, если сумма делится на 26.
Докажите, что для любых числовых значений букв существует комбинация, открывающая замок.
Обозначим через S(n) остаток от деления на 26 суммы чисел, которые соответствуют первым n буквам алфавита (n=1,2,...,26) 0 Ј S(n) Ј 25.
Если среди чисел 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-й буквой.