Ошибка.
Попробуйте повторить позже
Дана последовательность , состоящая из и Пусть — количество чисел от до таких, что и Докажите, что число последовательностей указанного вида, для которых нечетно, находится по формуле
Источники:
Подсказка 1
В задаче есть параметр k, учитывая который строятся последовательности. Увеличив k, несложно построить новую последовательность, не "сломав" старую. Попробуем решить задачу индукцией по k! Докажем, что если утверждение выполняется при k-1, но оно выполняется и при k.
Подсказка 2
Если последовательность из 2k элементов удовлетворяет условию, то какой тогда будет эта последовательность без последнего пары a_k, b_k? Что будет с четностью N?
Подсказка 3
Нам подходят такие последовательности длины 2(k-1), где N четно, а_k = 0 и b_k = 1. А если N нечетно, то какой может быть пара (a_k;b_k)?
Применим метод математической индукции по параметру . При формула очевидна. Докажем, что если она верна при , то верна и при
Искомое число равно числу последовательностей
(1) |
в которых количество таких, что и четно (в этом случае пара может быть только плюс количество последовательностей вида (1) в которых количество чисел таких, что и нечетно, умноженному на 3 (так как пара может быть любой из пар В итоге по предположению индукции нужное число последовательностей будет удовлетворять равенству
Ошибка.
Попробуйте повторить позже
Имеется устройство, которое строит последовательность чисел следующим образом: первые два члена и мы задаем самостоятельно, а последующие члены устройство вычисляет так: Здесь — – некоторая фиксированная ключевая последовательность. При этом все числа и являются целыми, лежащими в пределах от 0 до 32 включительно. (Если в процессе вычислений получится число, превосходящее 32, то результат будет заменен его остатком от деления на 33; например, С помощью этого устройства построили две последовательности и по первым членам и Верно ли, что найдётся ключевая последовательность и некоторое целое большее 0, такие, что выполняются условия:
a)
б)
Решение обоснуйте.
Источники:
Пункт а), подсказка 1
У вас есть равенство двух членов одной последовательности двум другим. А как можно выразить, например предыдущий член последовательности через два соседних? Попробуйте так прийти к противоречию)
Пункт б), подсказка 1
Мы понимаем, что последовательности устроены одинаковым образом, так еще и ключевая последовательность у них одинаковая. Что можно сделать, чтобы вообще исключить эту последовательность?
Пункт б), подсказка 2
Вычесть одну последовательность из другой! По факту, в этой последовательности тогда нужно будет понять, есть там единица, или нет. В таком случае посмотрите на первые члены и на то, по какому модулю у нас все происходит и придите к противоречию)
а) Для всех
Поэтому, если , то , что противоречит условию.
б) Удобно перейти к разностям полублоков (везде далее действия с полублоками (умножение, сложение и вычитание) производятся по модулю ) и выяснить, может ли 1 появиться в . Из уравнения шифрования
получаем после вычитания
что последовательность разностей не зависит от ключа . По условию , поэтому все члены последовательности будут делиться на , и единицы там не будет.
а) нет
б) нет
Ошибка.
Попробуйте повторить позже
Знаками открытого и шифрованного текстов являются пары целых от 0 до 31. Для зашифрования используется секретный ключ (целое число от 0 до 31), заданная таблично функция а также функция которая паре целых чисел ставит в соответствие пару (причем если число или превышает 31 , то их заменяют остатком от деления на 32 Знак шифрованного текста получается из знака открытого текста путем 128-кратного применения функции
Известно, что знак открытого текста преобразовался в знак зашифрованного текста знак преобразовался в — в и, наконец, в Найдите ключ
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
9 | 1 | 30 | 4 | 24 | 12 | 8 | 23 | 18 | 7 | 16 | 15 | 21 | 26 | 10 | 17 | 19 | 22 | 13 | 28 | 14 | |
21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
11 | 2 | 29 | 3 | 6 | 27 | 0 | 5 | 25 | 31 | 20 |
Источники:
Подсказка 1
Применять 128 раз одну и ту же функцию очень сложно...поэтому было бы хорошо, если мы сразу могли понимать, а что у нас получается на каждой итерации? Может ли в итоге у двух разных пар получиться один и тот же знак?
Подсказка 2
Если две пары отличаются одним применением функции, то и их знаки тоже отличаются одним применением функции. Как это связать с условием?
Подсказка 3
Попробуем найти такие пары чисел, которые удовлетворяют утверждению из подсказки 2. Теперь мы знаем, какие пары отличаются применением функции g! Несложно найти k)
Необходимо заметить, что из равенств
следует равенство
Необходимым условием выполнения равенств являются равенства Среди приведенных в задаче пар знаков открытого и шифрованного текстов есть знаки, удовлетворяющие этому условию: одна пара и вторая пара То есть
Из условия задачи возможность найти ключ — воспользоваться равенствами
Убедимся, что при этих условиях оба равенства дают одинаковое значение ключа
Получаем, что
Ошибка.
Попробуйте повторить позже
На вход устройства подается лента с записанными на ней нулями и единицами:
За один такт устройство считывает с ленты с позиций (на первом такте ) три значения . Если то устройство на новой ленте печатает 1 , иначе — 0 . Затем устройство сдвигается на одну позицию вправо, и процедура повторяется. Найдите разности и если известно, что а на новой ленте было напечатано следующее: (для примера на рисунке изображен случай
Источники:
Подсказка 1
Да, можно и перебрать d_1 и d_2, но это будет долго) Попробуем сократить перебор! Что мы вообще умеем делать? Мы умеем брать конкретные элементы ленты и считать их сумму, если расстояния между ними это d_1 и d_2. Какие "удобные" элементы хочется взять?
Подсказка 2
Рассмотрим систему неравенств, которая соответствует выходных знакам вида 1...1 на расстоянии d_1. С помощью нее мы сможем дать ограничения на элементы, находящиеся на расстоянии d_1. Таким образом мы сможем перебрать и методом "пристального взгляда на ленту" найти d_1. Аналогично с d_2!
Число возможных вариантов и , можно для каждого варианта проверять, что соответствие входных и выходных символов, а можно предложить более быстрый способ, заключающийся в нахождении сначала (максимум 10 вариантов), а затем . Для этого достаточно заметить следующее.
Если рассмотреть систему, соответствующую выходным знакам на расстоянии вида в произвольном такте работы
то если , то
Это позволяет отбраковать опробуемый вариант Устанавливаем, что
Аналогично, если рассмотреть систему, соответствующую выходным знакам на расстоянии вида в произвольном такте работы
тогда если то
Это позволяет отбраковать опробуемый вариант (с учётом найденного ранее Находим