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

Задания

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

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

Для зашифрования осмысленного слова его буквы заменили числами 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=a y левая круглая скобка \bmod n правая круглая скобка .$ Используя условие задачи для первой буквы открытого и шифрованного текста, получим равенство

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

Заметим, что $7 умножить на 5=3 левая круглая скобка \bmod 32 правая круглая скобка .$ Тогда

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

что равносильно равенству

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

Значит,

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

В итоге получаем, что $x=5 z в степени левая круглая скобка \prime правая круглая скобка левая круглая скобка \bmod 32 правая круглая скобка .$ Остается воспользоваться полученным соотношением для остальных букв. Получится слово ГВОЗДЬ.

Ответ: ГВОЗДЬ.

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

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

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

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