Тема Верченко (криптография)

Верченко - задания по годам → .04 Верченко 2023

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела верченко (криптография)

Разделы подтемы Верченко - задания по годам

Верченко 2020 и ранее

Верченко 2021

Верченко 2022

Верченко 2023

Верченко 2024

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#68238

Найдите все восьмизначные числа $A = aa-...a-, 12 8$ $a ∈ {1,2,...,9} i$ такие, что $8⋅A+ a = B, 8$ где $B =b-b-...b 12 8$ , $b = 10 − a . i i$ Решение обоснуйте.

Источники: Верченко-2023 (см. v-olymp.ru)

Показать ответ и решение

Заметим, что

108−-1- A+ B =1◟1.◝.◜.1 ◞0 = 9 ⋅10. 8

Тогда из условия $8⋅A +a8 = B$ получим

9A +a8 = 11...10. ◟-◝8◜ ◞

Следовательно, по признаку делимости на 9

a8 = 1◟+1-+◝.◜..+-1◞= 8. 8

Разделим число $1◟1.◝8.◜.1 ◞0 − 8$ на $9$ . Получим число $12345678.$

Ответ: 12345678

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#68239

На координатной плоскости в точках $A(2,4),B(8,8),C(8,0),D (14,1)$ и $E(8,1)$ расположены вышки сотовой связи. Будем говорить, что абонент находится в зоне действия данной вышки, если расстоянии до неё меньше, чем до любой другой вышки. Найдите площадь зоны действия вышки $E.$

Источники: Верченко-2023 (см. v-olymp.ru)

Показать ответ и решение

Для начала требуется отобразить точки на координатной плоскости. Так как по условию задачи требуется найти площадь зоны действия вышки $E$ , то соединим отрезками точку $E$ с точками $A,B,C,D$ . Далее проведём через полученные отрезки серединные перпендикуляры и выделим область, полученную пересечением таких перпендикуляров (отмечены на рис. оранжевым цветом). Таким образом, получаем трапецию (см. рисунок ниже), которая демонстрирует область зоны действия вышки $E$ :

$PIC$

Осталось посчитать площадь полученной трапеции. Пересечение срединных перпендикуляров дало нам 4 точки с координатами $F(6,4.5),H (11,0.5),K(4,0.5),G(11,4.5)$ . Площадь данной трапеции

S = 12 ⋅(HK + FG)⋅HG = 12 ⋅(5+ 7)⋅4= 24

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 3#68240

Пароли в системе составляются из букв английского алфавита (26 букв) и цифр. При этом требуется, чтобы в пароле содержались цифра и заглавная буква. Пользователь допускается в систему, если предъявленный им пароль отличается от установленного не более чем в одном символе. Сколько паролей, соответствующих требованиям составления, позволят войти в систему, если для пользователя был установлен пароль Tw38dttf (не совпадающих с установленным паролем)?

Источники: Верченко-2023 (см. v-olymp.ru)

Показать ответ и решение

Раскладываем пароль "по слоям": цифра + заглавная + строчная и смотрим, какие ограничения есть по замене в каждой позиции. Цифр две, поэтому одну из них можно заменить произвольно на любой знак из $26+ 26+ 10 − 1= 61$ . Если менять заглавную T, то только на заглавную: $26− 1= 25$ вариантов. Строчные можно на любые, это ещё $5⋅61= 305$ вариантов. Итого $2⋅61+ 25+5 ⋅61 =452$ вариантов.

Ответ: 452

Ошибка.
Попробуйте повторить позже

Задача 4#68241

Пусть $x =(x ,...,x ) 1 8$ — двоичный вектор длины 8. Обозначим $xd$ — циклический сдвиг вектора $x$ на $d$ позиций вправо. Например, если $x =(1,0,0,0,0,0,0,0),$ то $2 x = (0,0,1,0,0,0,0,0).$ При этом считаем, что $0 x = x.$ Под суммой векторов $x= (x1,...,x4)$ и $y =(y1,...,y4)$ будем понимать вектор

x +y =(x1⊕ y1,x2⊕ y2,x3⊕ y3,x4⊕ y4)

Здесь $⊕$ — стандартная операция сложения битов: $0 ⊕0 =1⊕ 1= 0,$ $0⊕ 1= 1⊕0 =1.$ Пусть

1 4 x= v+ v + v

Найдите $d1,...,dn$ такие, что при любом исходном векторе $v$ выполняется равенство

v =xd1 + ⋅⋅⋅+ xdn

Источники: Верченко-2023 (см. v-olymp.ru)

Показать ответ и решение

Заметим, что $xd+8n = xd$ для любого натурального числа $n$ . Вектору $x = (x ,...,x) 1 8$ взаимно однозначно соответствует многочлен

7 8 x(t)= x1+ x2t+ ...+ x7t + x8t

Тогда циклический сдвиг вектора $x$ на $d$ позиций вправо равносилен умножению многочлена $x(t)$ на $td$ и приведению степеней мономов по модулю $8$ .

Вектору $x =v +v1 +v4$ соответствует многочлен $x(t)= 1+ t+ t4$ . Таким образом, нахождение $d ,...,d 1 n$ таких, что $v =xd1 +...+ xdn$ равносильно нахождению многочлена $v(t)= td1 +...+ tdn$ со свойством $x(t)v(t)= 1$ (с учётом приведения степеней мономов по модулю $8$ ). Найти многочлен $v(t)$ можно методом неопределённых коэффициентов, но быстрее из следующего алгоритма:

2 8 2 4 4 8 8 x (t)= 1+t+ t = t, x (t)= t,x (t)= t= 1

Следовательно,

7 3 4 4 2 4 2 6 7 v(t)= x (t)= x(t)x (t)= (1+t+ t)tt = t +t + t

Ответ:

$v =x2+ x6+ x7$

Ошибка.
Попробуйте повторить позже

Задача 5#68242

Имеется устройство, которое строит последовательность чисел $x,x ,x ,... 0 1 2$ следующим образом: первые два члена $x 0$ и $x 1$ мы задаем самостоятельно, а последующие члены устройство вычисляет так: $x2 =x0+ 13⋅(x1+ k1),x3 = x1+ 13 ⋅(x2+ k2),...$ Здесь $k1,k2,...$ — – некоторая фиксированная ключевая последовательность. При этом все числа $x0,x1,x2,...$ и $k1,k2,...$ являются целыми, лежащими в пределах от 0 до 32 включительно. (Если в процессе вычислений получится число, превосходящее 32, то результат будет заменен его остатком от деления на 33; например, $16+ 13 ⋅2 =9.)$ С помощью этого устройства построили две последовательности $a0,a1,a2,...$ и $b0,b1,b2,...,$ по первым членам $a0 =1,a1 = 3$ и $b0 =1,b1 =12.$ Верно ли, что найдётся ключевая последовательность $k1,k2,...$ и некоторое целое $t,$ большее 0, такие, что выполняются условия:

a) $bt = at,bt+1 =at+1?$

б) $bt = at+1?$

Решение обоснуйте.

Источники: Верченко-2023 (см. v-olymp.ru)

Показать ответ и решение

а) Для всех $t≥1$

at+1 = at− 1+13(at+ kt),at−1 =at+1− 13(at+kt)

Поэтому, если $bt = at,bt+1 =at+1$ , то $bt−1 =at−1,...b1 = a1,b0 = a0$ , что противоречит условию.

б) Удобно перейти к разностям полублоков $zt = bt− at$ (везде далее действия с полублоками (умножение, сложение и вычитание) производятся по модулю $M$ ) и выяснить, может ли 1 появиться в ${z} t$ . Из уравнения шифрования

bt+1 = bt−1+ 13(bt+kt),t≥ 1

a =a + 13(a +k ),t≥ 1 t+1 t−1 t t

получаем после вычитания

zt+1 = zt−1+ 13zt,t≥1,

что последовательность разностей не зависит от ключа $kt$ . По условию $(z0,z1)= (0,9),(z0,z1,M )= 3$ , поэтому все члены последовательности будут делиться на $3$ , и единицы там не будет.

Ответ:

а) нет

б) нет

Ошибка.
Попробуйте повторить позже

Задача 6#68243

Для входа в университет Криптоландии у каждого студента есть карточка, на которой записана уникальная (у каждого студента своя) последовательность $x1,x2,x3,x4,x5,x6,x7$ из целых чисел от 0 до 5. При входе в университет студент прикладывает карточку к устройству, которое подсчитывает величины $A$ и $B$ по формулам:

A= ((x1 ∗x2)∗ x3)∗x4

B =(x5∘x6)∘x7

Операции $∗$ и $∘$ задаются таблицами (представляющими собой латинские квадраты: у них в каждой строке и каждом столбце числа не повторяются).

$PIC$

Например, $3∗2 =3,$ $2∘ 4=2.$ Студенту разрешат войти, если $A = B.$

Сколько самое большое может быть студентов в таком университете?

Показать ответ и решение

Если код составлен из чисел от $0$ до $m − 1$ , то для каждого числа

k∈ {0,...,m − 1}

число последовательностей $x1,x2,x3,x4$ , для которых $A = k$ , равно $m3$ , так как при любых заданных $x1,x2,x3$ значение $x4$ определяется в этом случае однозначно.

Аналогично, число последовательностей $x ,x,x 5 6 7$ для которых $B = k$ , равно $m2$ . Тогда общее число последовательностей $x ,x,x ,x,x ,x ,x 1 2 3 4 5 6 7$ , для которых $A= B =k$ , равно $m3m2 = m5$ . Суммируя по $k$ от $0$ до $m − 1$ , получаем ответ: $m6$ .

Ответ:

$66$

Предыдущая подтема

Следующая подтема