Тема Межрегиональная им. И. Я. Верченко (криптография)

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

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

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

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

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

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

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

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

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

Подсказки к задаче

Подсказка 1.

Сразу поймём, что нет никакого смысла рассматривать случаи, когда первый игрок заполняет ячеек меньше, чем k-1. Ведь Юра может оставить Кате всего лишь одну ячейку. Так что будем считать, что если он заполнил меньше k-1 ячейки, то Катя заполняет оставшиеся ячейки, кроме последней, нулями.

Подсказка 2.

Теперь если мы докажем, что числа на k-1 ячейках можно разбить на такие 2 группы, что суммы чисел в них будут отличаться не менее чем на 2022, то Катя сможет победить, поставив в последнюю ячейку число, уравнивающее суммы этих групп. Сейчас работать с числами не очень удобно. Попробуйте упорядочить их и разбить на подходящие группы.

Подсказка 3.

Если мы упорядочим числа и распределим в группы через один, то сумма в группах будет отличаться не более чем на 2022. Победа!

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

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

Ответ: Катя

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

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

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

Задача 2#68240

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

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

Подсказки к задаче

Подсказка 1

Посмотрите, сколько способов есть заменить маленький символ в пароле? А цифру? А заглавную букву? И помните про условие, что обязательно должна быть заглавная буква и цифра)

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

Раскладываем пароль "по слоям": цифра + заглавная + строчная и смотрим, какие ограничения есть по замене в каждой позиции. Цифр две, поэтому одну из них можно заменить произвольно на любой знак из $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.$

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

Подсказки к задаче

Подсказка 1

Делать вычисления по этим таблицам точно не хочется, поэтому давайте подумаем. Посмотрите внимательно на строчки и столбцы таблиц...что в них есть примечательного?

Подсказка 2

В каждой строчке и в каждом столбце по одному разу использовано каждое число от 0 до 6) Что это может значить?

Подсказка 3

Например, для любого x от 0 до 6 найдется такой y, что каждая из этих операций с x и y даст результат который мы хотим, причём y будет однозначно задаваться по таблице) Раскрутите эту идею.

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

Если код составлен из чисел от $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

В этой задачи нам описали какой-то алгоритм и просят понять, что могло быть результатом этого алгоритма. В таких задачах полезно поискать инварианты (то, что не меняется в результате работы алгоритма) или свойства: как данный алгоритм работает для некоторых схожих входных данных. Обратите внимание на то, что в алгоритме как бы описаны взаимодействия между объектами: символ с места A переходит в символ с местов B, а какой математический объект позволяет нам показывать связи между объектами?

Подсказка 2

Правильно, можно использовать граф, попробуйте нарисовать его для правила из "примера", а затем для двойной перестановки и посмотрите, как он изменился. Если не сразу понятно, на что обращать внимание, то придумайте своё правило для перестановки чисел и проделайте те же действия.

Подсказка 3

Можно заметить, что циклы длины 2n распадаются на 2 цикла длины n, а каждый цикл длины 2n+1 остаётся длины 2n+1 (взаимосвязи между объектами другие, но длина та же). Ага! Из каждого объекта при какой-то операции получается по 2 объекта, на что это похоже?

Подсказка 4

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

Подсказка 5

Верно, если мы посмотрим, что происходит с циклами длины 2 * (2n+1) (длина которых делится на 2, но не делится на 4), то они просто превращаются в нечётные циклы, а так как мы не знаем, сколько изначально было циклов нечётной длины, то про их итоговую чётность мы ничего сказать не можем. Почему бы тогда не посмотреть на циклы чётной длины, ведь они могут получиться только из циклов кратных 4. А сколько тогда циклов чётной длины будет?

Подсказка 6

Да, циклов чётной длины чётное количество, иначе бы не выполнялось утверждение о том, что из циклов длины 2n получаются 2 цикла длины n. Осталось посмотреть, какие из перестановок из пункта "а" противоречат данному утверждению, а для остальных найти пример!

Подсказка 7

Давайте сразу определимся, что "за n попыток можно с гарантией подобрать пароль" значит, что какие бы случайные n попыток мы не сделали, хотя бы одна из них даст нам наш пароль. Понятно, что тогда надо посчитать общее количество двойных перестановок, оно и будет ответом. Остаётся только понять, что на самом деле мы доказали критерий существования двойных перестановок (Двойная перестановка существует тогда и только тогда, когда циклов чётной длины чётное количество, попробуйте показать, почему это работает и в обратную сторону).

Подсказка 8

Попробуйте разбить подсчёт на более простые случаи. Если всего 6 элементов в графе, то сколько циклов и какой длины может быть при условии, что это двойная перестановка? Всегда при подсчёте задавайте себе вопросы: а важен ли порядок? А есть ли граничные случаи и все ли их я рассмотрел?

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

Приведенное в условии правило перестановки букв, или перестановку, будем обозначать греческой буквой $σ.$ Перестановку $σ$ можно интерпретировать как отображение множества цифр ${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)

Подсказки к задаче

Подсказка 1

Всего существует 4⁸ последовательностей длины 8, составленных из букв криптоландского алфавита. Подумайте, как удобнее всего почитать число тех последовательностей, которые являются словами.

Подсказка 2

Все последовательности разбиваются на три непересекающихся множества: 1. Не содержащие буквы a; 2. Содержащие букву а и хотя бы одну пару аа; 3. Содержащие букву а и не содержащие ни одной пары аа. При этом очевидно, что элементы 1 и 2 множеств являются словами, а 3 - нет. Посчитать число элементов второго множества выглядит либо очень сложной задачей, либо вовсе нереальной. Тогда удобнее всего найти число последовательностей, являющихся словами, будет просто вычтя из 4⁸ число элементов 3 множества. Подумайте, каким образом их можно сосчитать.

Подсказка 3

Для n букв а в слове возможно найти число способов расставить их в последовательности длины 8 по формуле: число сочетаний из 8+1-n по n. Кроме того у нас есть еще 3^(8-n) способов расставить b, c, d на оставшиеся места. Подумайте, какое максимально значение может принимать n.

Подсказка 4

При n ≥ 5 гарантировано будет существовать пара aa. Значит, они нам не подходят. Теперь найдем число последовательностей для n = 1, 2, 3, 4, сложим их и таким образом получим количество элементов 3 множества.

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

Множество всех последовательностей длины $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

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

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Заметим, что если мы определили числа в верхнем левом квадрате 3 на 3, то мы определили всю таблицу. Понятно, что картинка тогда восстанавливается, но не будет ли противоречий при каких-то заполнениях квадрата 3 на 3 на диагонали?

Подсказка 3

Конечно, противоречия могут быть. Поэтому надо добавить еще два линейных равенства на диагонали. А значит, у нас есть 9 переменных и два равенства. Отсюда 7 свободных переменных, а потому вариантов 3⁷.

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

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

Ответ:

$2187$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел