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

Комбинаторика на Верченко

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

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

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

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

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

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

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

Задача 1#90274

Катя и Юра играют в следующую игру. Имеется пустая таблица из одной строки, состоящая из $k= 20232$ пустых ячеек: ( $a ,...,a 1 k$ ), которые игроки заполняют числами от 0 до 2022. Первым ходит Юра, который выбирает число $t$ такое, что $1≤t≤ k− 1$ и заполняет $t$ ячеек. Второй ходит Катя, которая заполняет оставшиеся ячейки. Победитель определяется по следующему правилу: если в результате получается «счастливая» комбинация чисел - полностью заполненная таблица, в которой числа можно разбить на две непересекающиеся группы, суммы чисел в которых одинаковы, то выигрывает Катя, в противном случае выигрывает Юра. Например, комбинация ( $7,5,3,4,6$ ) не является «счастливой», так как в ней присутствует нечетное число нечетных чисел. С другой стороны, комбинация $(4,5,1,6,8)$ является «счастливой», так как $4 +8= 5+ 1+ 6$ . У кого из игроков имеется выигрышная стратегия? Ответ обосновать.

Источники: Верченко - 2024, 11.1 (см. ikb.mtuci.ru)

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

Очевидно, что достаточно рассмотреть случай, когда игрок, делающий первый ход, заполняет максимально возможное число ячеек, равное $k− 1$ . Расположим эти $k− 1$ число в порядке не убывания: $ai1 ≤ai2 ≤ ⋅⋅⋅≤ aik−1$ . Здесь в индексах указаны номера позиций, на которых стоят эти числа в таблице. Образуем два множества позиций, которые заполнены: ${i1,i3,...}$ и ${i2,i4,...}$ , беря указанные числа через одно. Тогда суммы чисел на этих позициях могут отличаться друг от друга не более, чем на 2022. Поэтому оставшуюся незаполненной позицию можно заполнить числом от 0 до 2022 так, чтобы получилась «счастливая» комбинация.

Ответ: Катя

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

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

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

Задача 2#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

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

Задача 3#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$

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

Задача 4#71012

Петя использует для работы в интернете пароли из шести символов. Опасаясь злоумышленников, он решил в каждом пароле изменить порядок следования символов, используя для этого одно и то же правило, которое записал в книжечку. Правило могло выглядеть, например, так:

( ) 1 2 3 4 5 6 3 6 4 5 1 2

То есть первый символ ставится на третье место, второй - на шестое и так далее. В своем пароле для почты qwerty Петя переставил буквы по правилу из книжечки, а затем, для большей надежности переставил буквы по этому же правилу еще раз. (Если использовать правило как в примере, то из qwerty после первой перестановки получится tyqerw, а после второй — rwtqey).

a) Какие из нижеследующих комбинаций


yetrqw	eyrtqw	yrwteq	rewqyt	qwtyre	tywreq

могли быть получены двойной перестановкой букв в пароле qwerty? (используя, возможно, другие правила указанного вида)

б) Петя потерял книжечку! Он помнит, что первоначально пароль был qwerty, но правило, по которому были в нём дважды переставлены буквы, не помнит. За какое наименьшее число попыток можно с гарантией подобрать утерянный пароль?

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

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

Приведенное в условии правило перестановки букв, или перестановку, будем обозначать греческой буквой $σ.$ Перестановку $σ$ можно интерпретировать как отображение множества цифр ${1,2,3,4,5,6}$ в себя. Например, тот факт, что первая буква перешла на третье место, можно записать как $σ(1)= 3,$ а также изобразить стрелочкой из 1 в 3:

$PIC$

Видно, что если бы мы перестановку $σ$ применяли многократно, то буквы на 2-й и 6-й позициях постоянно менялись бы местами, а буквы на позициях 1, 3, 4, 5 переставлялись бы по циклу. Поэтому перестановка $σ$ может символически быть записана в виде произведения циклов:

( ) σ = 1 2 3 4 5 6 = (1345)(26)= 4∗2 3 6 4 5 1 2

Запись $4∗ 2$ отражает цикловую структуру перестановки $σ,$ показывая, что в ней один цикл длины 4 и один цикл длины 2.

Посмотрим теперь более детально на то, что произойдет, если по правилу $σ$ переставить буквы еще раз. Так 1 при первом применении правила $σ$ перешла в 3: $σ(1)=3,$ а при повторном применении 3 перешла в 4: $σ(3)= 4.$ Значит, в результате двойной перестановки 1 переходит в 4. Будем это записывать как $σ(σ(1))= 4$ или же $2 σ (1) =4.$ Поэтому правило двойной перестановки букв, представляющее собой квадрат перестановки $σ,$ выглядит так:

$PIC$

Заметим, что после повторной перестановки 2 и 6 вернутся на свои места, то есть цикл $(2,6)$ распадется на два тривиальных цикла $(2)$ и $(6),$ а цикл $(1345)$ превратится в два цикла $(1,4)$ и $(3,5).$ Таким образом, при повторном применении перестановки циклы четной длины $2n$ распадаются на два цикла, длины $n$ каждый. Несложно проверить, что при этом циклы нечетной длины сохраняются. Справедливо утверждение.

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

Рассмотрим первую комбинацию уеqwrt из пункта а). Она получена из qwerty перестановкой $( ) 1 2 3 4 5 6 = (1324561), 3 4 2 5 6 1$ которая представляет собой цикл длины 6. Поскольку циклов четной длины здесь нечетное количество (всего один), то, согласно утверждению, такая комбинация двойной перестановкой букв получиться не могла. Аналогично исследуются и остальные комбинации в пункте а).

Проведем подсчет общего числа перестановок, являющихся полными квадратами. Их цикловые структуры могут быть следующие:

$1∗ 1∗1∗1∗ 1∗1.$ Это перестановка, оставляющая все на своих местах (тождественная перестановка). Она единственна.
$1∗ 5.$ Мы должны выбрать 5 элементов из шести, чтобы составить цикл дины 5. Это можно сделать 6-ю способами. Из пяти элементов цикл длины 5 можно организовать $(5− 1)!$ способами (действительно, организуем цикл из пяти элементов $a1,a2,a3,a4,a5;$ элемент $a1$ может перейти в любой из четырех (т.к. в себя нельзя), элемент $a2$ переходит в один из оставшихся трех и т.д. В итоге получаем $4 ⋅3 ⋅2 ⋅1$ способов). Таким образом, здесь $6⋅4!= 144$ перестановок.
$2∗ 2∗1∗1.$ Выбрать два элемента из шести для первого цикла длины 2 можно $2 C6$ способами. Для второго цикла длины 2 есть $2 C4$ способа. Итого $2 2 C 6 ⋅C4 = 90.$ От порядка следования циклов результат не зависит, поэтому 90 еще следует разделить на два. Всего 45 перестановок с такой структурой.
$3∗ 3.$ Здесь мы 6 элементов десятью способами $( ) 12C36 = 10$ разбиваем на две тройки и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.
$3∗ 1∗1∗1.$ Здесь мы двадцатью способами $( ) C36 = 20$ выбираем тройку и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.

В итоге, имеется $1+144+ 45+40+ 40= 270$ перестановок длины 6, представляющих собой полный квадрат.

Ответ:

a) yetrqw, tywreq;

б) 270

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

Задача 5#71371

В Криптоландии используется алфавит, состоящий из четырёх латинских букв $a,b,c,d.$ Любая последовательность букв алфавита будет словом криптоландского языка при выполнении единственного ограничения: если в последовательности есть хоть одна буква " $a$ то тогда в ней обязательно должны встретиться две буквы " $a$ "подряд.

Например, последовательности $baacda,aabb,ddd$ являются словами, а последовательности $bcadda,abba$ — не являются. Найдите число слов длины 8 в криптоландском языке.

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

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

Множество всех последовательностей длины $8$ состоит из $48$ последовательностей. Это множество разбивается на три непересекающихся между собой подмножества:

1.: Последовательностей, не содержащих $a.$
2.: Последовательностей, содержащих $a,$ но не содержащих двух подряд идущих таких букв.
3.: Последовательностей, содержащих $a$ , в которых встречаются две подряд идущие такие буквы.

Чтобы решить задачу, нужно найти число последовательностей во втором подмножестве и вычесть его из числа $48.$

В свою очередь, множество последовательностей второго типа можно разбить на непересекающиеся подмножества, в которые входят последовательности, содержащие $1,2,3,4$ букв " $a$ ".

Поскольку число последовательностей длины $8$ , содержащих ровно $t$ отдельно стоящих букв $a$ , равно $Ct8+1−t(4− 1)8−t,$ то общее число последовательностей второго типа будет равно

4∑ t 8−t C9−t3 =38070 t=1

В итоге получаем

48 − 38070 =27466

Ответ: 27466

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

Задача 6#99581

Ключом шифрсистемы служит таблица $4 ×4,$ в каждую ячейку которой записана одна из цифр $0,1,2.$ При этом должны делиться на $3$ сумма цифр в каждой строке, сумма цифр в каждом столбце, а также суммы цифр на каждой из двух диагоналей таблицы $4× 4.$

Один из возможных вариантов ключа:


1	1	2	2

2	1	1	2

0	0	1	2

0	1	2	0

А сколько всего существует различных ключей?

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

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

Указанную в условии таблицу $4 ×4$ , можно построить следующим образом: положим элементы верхнего левого угла размеров $3× 3$ произвольным образом, после чего заметим, что все оставшиеся элементы определяются однозначно из линейных (по модулю $3$ ) соотношений для строк и столбцов (при этом элемент в правом нижнем углу будет равен сумме по модулю $3$ всех остальных элементов квадрата). Плюс к этому имеем два линейных соотношения для элементов диагоналей. Таким образом, общее число независимого выбора переменных $ai,j,i,j = 1,2,3$ равно $7.$ Следовательно, общее число ключей равно $7 3 = 2187.$

Ответ:

$2187$