РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 7680 Добавить в вариант

Для зашифрования осмысленного слова его буквы заменили числами x₁, x₂, ..., x_n по таблице. Затем выбирали четные натуральные числа p и q и для каждого числа $x_i$ из соотношений $x_i=y_i плюс p z_i,$ $z_i=y_i плюс q x_i$ нашли целые числа y_i и z_i. Потом по формулам $z_i в степени левая круглая скобка \prime правая круглая скобка =r_32 левая круглая скобка z_i правая круглая скобка ,$ $i=1, \ldots, n$ получили числа $z_1 в степени левая круглая скобка \prime правая круглая скобка ,$ ..., $z_n в степени левая круглая скобка \prime правая круглая скобка$ (где r₃₂(a)h  — остаток от деления числа a на 32), которые вновь заменили буквами согласно таблице. В результате получили вот что: ЖЯЮЦКР. Найдите исходное слово, если известно, что оно начинается на букву В.

А	Б	В	Г	Д	Е Ё	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31

Спрятать решение

Решение.

Рассмотрим произвольную букву открытого и шифрованного текстов. Для соответствующих им (по таблице) чисел x и $z в степени левая круглая скобка \prime правая круглая скобка$ выполняются равенства $x=y плюс p z$ и $z=y плюс q x,$ при некотором y, p и q. При этом по условию $z в степени левая круглая скобка \prime правая круглая скобка =r_32 левая круглая скобка z правая круглая скобка .$ Используя свойство сравнений по модулю целого числа, получим:

$x минус z в степени левая круглая скобка \prime правая круглая скобка =p z в степени левая круглая скобка \prime правая круглая скобка минус q x левая круглая скобка \bmod 32 правая круглая скобка$ или $x левая круглая скобка 1 плюс q правая круглая скобка =z в степени левая круглая скобка \prime правая круглая скобка левая круглая скобка 1 плюс p правая круглая скобка левая круглая скобка \bmod 32 правая круглая скобка .$

Для дальнейшего решения будем пользоваться следующим свойством: если наибольший общий делитель чисел a и n равен 1, то сравнение $x=y левая круглая скобка \bmod n правая круглая скобка$ равносильно $a x=\ay левая круглая скобка \bmod n правая круглая скобка .$ Используя условие задачи для первой буквы открытого и шифрованного текста, получим равенство

$2 левая круглая скобка 1 плюс q правая круглая скобка =6 левая круглая скобка 1 плюс p правая круглая скобка левая круглая скобка \bmod 32 правая круглая скобка .$

Заметим, что сравнение $6 t=2 левая круглая скобка \bmod 32 правая круглая скобка$ имеет 2 решения по модулю 32: $t=11 левая круглая скобка \bmod 32 правая круглая скобка ,$ $t=27 левая круглая скобка \bmod 32 правая круглая скобка .$ Тогда получим, что

$11 умножить на левая круглая скобка 1 плюс q правая круглая скобка = левая круглая скобка 1 плюс p правая круглая скобка левая круглая скобка \bmod 32 правая круглая скобка$ или $27 умножить на левая круглая скобка 1 плюс q правая круглая скобка = левая круглая скобка 1 плюс p правая круглая скобка левая круглая скобка \bmod 32 правая круглая скобка$

для каждого t. Таким образом, $x=11 z в степени левая круглая скобка \prime правая круглая скобка левая круглая скобка \bmod 32 правая круглая скобка$ или $x=27 z в степени левая круглая скобка \prime правая круглая скобка левая круглая скобка \bmod 32 правая круглая скобка$ соответственно.

Остается воспользоваться полученными соотношениями для остальных букв. Осмысленное слово получается только при втором варианте. А значит, исходное слово ВЕКТОР.

Ответ: BEKTOP.

Аналоги к заданию № 7668: 7674 7680 Все

Межрегиональная олимпиада школьников им. И. Я. Верченко, 11 класс, 2 тур (заключительный), 2021 год

Классификатор: Разное. Сборная солянка

Спрятать решение · Прототип задания · Помощь