Текстовые задачи на конструктивы в комбе → .02 Процессы и алгоритмы

"Спрятать"один бит, например, от всех абонентов, но сделать его доступным для пары можно следующим общим способом: выбрать некоторый бит пусть выдать это уравнение а уравнение — уравнение — произвольные, но зафиксированные значения). Ни ни не могут достоверно получить значение бита из имеющихся у них уравнений, но вместе они смогут его вычислить:

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

Этот способ можно распространить и на пары абонентов проверяя при этом, что пары абонентов не смогут найти ни одного бита.

По условию, числа прибавляются к битам открытого текста, а результат заменяется остатком от деления на 2. Заменим на остатки сразу: если четное, и если нечетное. Это не помешает нам вычислить остаток от деления на 32, так как если число четное, остаток будет четным, иначе — нечетным.

Посмотрим, какие последовательности мы получим в зависимости от четности чисел Д и М:

1.

Числа Д, М — нечетные. Тогда

2.

Числа Д, М имеют разную четность. Тогда

3.

Числа Д, М — четные. Тогда В этом случае текст Машиной записки остался бы без изменения, что, очевидно, не так.

Далее необходимо в первых двух случаях полностью вычислить последовательность вычесть ее из зашифрованного текста (ЗТ) и убедиться, что читаемый вариант получается во втором случае (см. таблицу).

Первое решение.

Сначала покажем, что расстояние до ближайшего целого числа от числа вида (где — иррациональное и — любое фиксированное число) можно выбором сделать сколь угодно малым.

Рассмотрим чисел

Их дробные части попадают в один из промежутков

Тогда по принципу Дирихле найдутся два числа

дробные доли которых попали в один и тот же промежуток. Их разность

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

Следовательно, существует такое число

что

Выберем натуральное число так, что выполняется одно из двойных неравенств

(здесь обозначает дробную часть ). Тогда найдётся такое целое число что

т.е.

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

где

Значит, расстояние от целого числа до числа меньше Увеличивая значение можно сделать это расстояние сколь угодно малым.

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

Пусть кузнечик находится в точке Выберем такое натуральное число что расстояние от до ближайшего целого меньше Если кузнечик сделает прыжков влево, он будет находиться на расстоянии менее от какого-то целого числа, независимо от того, сколько при этом он совершил прыжков вправо на Поскольку точка находится левее середины нашего отрезка, то, прыгая на вправо, кузнечик обязательно окажется на расстоянии менее от точки а на исходной прямой — на расстоянии, меньшем от точки

Второе решение.

Независимо от своего начального положения кузнечик рано или поздно окажется на промежутке

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

А если то он будет прыгать влево на пока не перепрыгнет точку и не окажется на промежутке

При дальнейших прыжках кузнечик уже не покинет промежутка оказавшись на он прыгает влево на и попадает на а оказавшись на он прыгает вправо на и попадает на

Если склеить промежуток в окружность той же длины то указанные прыжки кузнечика на этой окружности будут уже прыжками в одну сторону на (или в другую сторону на что на данной окружности — одно и то же).

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

Сначала заметим, что за три взвешивания на чашечных весах можно получить только 27 результатов за каждое взвешивание на чашечных весах можно получить только 3 результата — левая чашка легче правой, чашки уравновешены, правая чашка Но так как количество вариантов фальшивой монеты и ее относительного веса равно то должно выполняться неравенство Следовательно,

Пусть

Докажем методом от противного, что определить фальшивую монету и одновременно её относительный вес требуемым способом невозможно. Для этого предположим противное, то есть то, что есть такой способ.

Заметим, что так как за одно взвешивание на чашечных весах можно получить только 3 результата легче правой, чашки уравновешены, правая чашка то за два взвешивания на чашечных весах можно получить только 9 результатов.

Теперь покажем, что в первом взвешивании должно участвовать не менее 10 монет . Действительно, в противном случае в первом взвешивании участвует не более 8 монет быть чётным, так как взвешивание происходит на чашечных весах, а на чашки весов надо класть равные

Значит, если в результате первого взвешивания чашки весов уравновесятся, то фальшивая монета — одна из не менее, чем 5 монет, не участвовавших в первом взвешивании, она может быть как легче, так и тяжелее настоящих, и, следовательно, у нас возможно не менее 10 вариантов и её

А так как число результатов, которые можно получить за два взвешивания, меньше числа вариантов, то определение фальшивой монеты и её относительного веса невозможно.

В первом взвешивании участвует не менее 10 монет — не менее 5 на каждой чаше весов. Если в результате первого взвешивания одна чашка чем 5 оказалась легче, а другая не менее, чем 5 — тяжелее, то у нас возможно не менее 10 вариантов и ее Вновь число результатов за 2 взвешивания будет меньше числа вариантов.

Таким образом, предположив существование способа с помощью чашечных весов определить фальшивую монету и одновременно её относительный вес, мы пришли к заключению, что способ не существует, то есть — к противоречию с предположением.

Пусть

В описании способа определения фальшивой монеты будем использовать следующие обозначения:

1.

Монеты будем обозначать а —

2.

Выражения вида для взвешивания, в котором, в данном случае, пара монет и помещены на левую чашку весов, а пара других монет и (тоже из монет и гирьки) — на правую.

3.

У взвешивания может быть три исхода: < левая чашка = чашки и > правая чашка

4.

означает «для такого выражения возможны следующие случаи» (и далее — случаи для =, > и <).

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

(сначала мы кладем на левую чашу монеты с 1 по 4, а на вторую — с 5 по 8, остальные подобные выражения читаются аналогично)
(получили равенство, тогда фальшивая среди , а все — настоящие):

• (то есть фальшивая (12)):
  

  : фальшивая монета (12) и тяжелее;

  : фальшивая монета (12) и легче;

• (то есть фальшивая среди (9) и легче или среди (10) и (11) и тяжелее):
  

  (возможно только если (9) фальшивая и легче): фальшивая монета (9) и легче;

  (возможно только если (11) фальшивая и тяжелее): фальшивая монета (11) и тяжелее;

  (возможно только если (10) фальшивая и тяжелее): фальшивая монета (10) и тяжелее;

• (то есть фальшивая среди (9) и тяжелее или среди (10) и (11) и легче):
  

  • (возможно только если (9) фальшивая и тяжелее): фальшивая монета (9) и тяжелее;
  • (возможно только если (10) фальшивая и легче): фальшивая монета (10) и легче;
  • (возможно только если (11) фальшивая и легче): фальшивая монета (11) и легче;

(то есть фальшивая среди и легче, или среди и тяжелее, а все — настоящие):

• (то есть фальшивая среди (4) и легче, или (7) и (8) и тяжелее, а все остальные монеты — настоящие):
  

  (возможно только если фальшивая (4) и легче): фальшивая монета (4) и легче;

  (возможна только если фальшивая (8) и тяжелее): фальшивая монета (8) и тяжелее;

  (возможна только если фальшивая (7) и тяжелее): фальшивая монета (7) и тяжелее;

• (возможно только если фальшивая среди (1) и (2) и легче):
  

  (возможна только если фальшивая (1) и легче): фальшивая монета (1) и легче;

  (возможна только если фальшивая (2) и легче): фальшивая монета (2) и легче;

• (возможно только если фальшивая среди (5) и (6) и тяжелее):
  

  (возможна только если фальшивая (6) и тяжелее): фальшивая монета (6) и тяжелее;

  (возможна только если фальшивая (5) и тяжелее): фальшивая монета (5) и тяжелее;

(то есть фальшивая среди и тяжелее, или среди и легче, а все — настоящие):

• (то есть фальшивая среди (4) и тяжелее, или (7) и (8) и легче, а все остальные монеты — настоящие):
  

  (возможно только если фальшивая (4) и тяжелее): фальшивая монета (4) и тяжелее;

  (возможна только если фальшивая (7) и легче): фальшивая монета (7) и легче;

  (возможна только если фальшивая (8) и легче): фальшивая монета (8) и легче;

• (возможно только если фальшивая среди (3) и тяжелее или (5) и (6) и легче):
  

  (возможно только если фальшивая (3) и тяжелее): фальшивая монета (3) и тяжелее;

  (возможна только если фальшивая (5) и легче): фальшивая монета (5) и легче;

  (возможна только если фальшивая (6) и легче): фальшивая монета (6) и легче;

• (возможно только если фальшивая среди (1) и (2) и тяжелее):
  

  (возможна только если фальшивая (2) и тяжелее): фальшивая монета (2) и тяжелее;

  (возможна только если фальшивая (1) и тяжелее): фальшивая монета (1) и тяжелее.

Итак, искомое

Посмотрим, что происходит с конфигурациями, в зависимости от того, как расположены первая и последняя монеты

• Если первая лежит буквой кверху, то последние монет преобразуются по аналогичным правилам так, словно первой монеты нет (пока все не превратятся в ). После преобразований последних монет последняя монета переворачивается.
• Если последняя монета лежит буквой кверху, то она никогда не будет перевернута, а первые монет преобразуются так, будто последней монеты нет.
• Если конфигурация начинается монетой, повернутой кверху буквой и заканчивается монетой, повернутой кверху буквой то средние монеты преобразуются по правилам так, будто других монет нет, пока все не повернутся буквой После этого сначала по порядку переворачиваются монеты а затем по порядку переворачиваются монеты

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

Определим где — среднее число ходов преобразования конфигурации длиной которые начинаются на если не является и оканчиваются на если не является Тогда при имеем

• 
• 
• исходя из замечаний для и
• 

Таким образом, выполняются равенства

Тогда получаем

и аналогичным образом

Теперь получаем реккурентное выражение для

Поскольку, мы знаем, что и то индукцией по получается, что

Обозначим через карту значения

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

Покажем, что по этим данным игрок может восстановить значения всех карт. Он может рассуждать так. Из того, что карты бьют друг друга по циклу, следует, что одна из них имеет значение а следующая по циклу — значение Но, кроме карт этого цикла, карту бьёт карта а карта бьёт карту Значит, не может иметь значение или то есть значения и имеют карты и соответственно.

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

Пусть первым ходом Женя подарит Сереже конфет. Тогда он должен ей подарить конфет, Женя — конфет, Сережа — конфету. Теперь Женя подарить конфеты не может, значит, она дарит ему одну конфету. У Сережи своих конфет не осталось, поэтому игра заканчивается. В итоге у Жени оказалось конфета, а у Сережи — значит, Женя добилась, чего хотела.

Рассмотрим две самых левых клетки. Если червячки в этих клетках поменялись местами, то отрежем эти клетки и рассмотрим новую полоску. Так будем отрезать по две клетки, пока не придем к ситуации, когда червячки из двух левых клеток не поменялись. Это точно случится, иначе в конце останется одна клетка, из которой червячку будет некуда переползать. Пусть осталась полоска длины Самого левого червячка обозначим через следующих — через и

Случай 1. Предположим, что переполз на соседнюю клетку, то есть на вторую. Тогда на первую мог переползти только иначе бы мы и также отрезали. Если переполз на третью клетку, то они с образуют искомую пару. Если переполз на четвертую клетку, то они с образуют искомую пару, значит, этот случай рассмотрен.

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

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

Если в некоторый момент среди чисел на карточках ровно нечётных, то среди произведений троек чисел ровно нечётных; поэтому число на очередной добавляемой карточке будет нечётным ровно тогда, когда нечётно (и тогда в эту минуту увеличится на ).

Заметим, что число нечётно, а число — чётно. Значит, в первую минуту добавится нечётное число, а дальше будут добавляться только чётные. Итак, после первой минуты среди чисел на карточках всегда будет ровно нечётных.

Рассмотрим числа на карточках после минут. Пусть — сумма всех произведений троек этих чисел, а — сумма всех произведений пар этих чисел. Число отличается от прибавлением всех произведений троек чисел, среди которых есть только что добавленное, то есть прибавлением итак, Заметим при этом, что при Значит, при число нечётно, и степень двойки, на которую делится равно степени двойки, на которую делится

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

Пронумеруем двери буквами . Проверим первым ходом три двери На очередном шаге будем смещать три проверяемые двери на две позиции по часовой стрелке. Заметим, что перескочить открытую дверь мы не сможем. С другой стороны, проверяемые двери сдвигаются на две позиции, а открытая — как максимум на одну, значит, рано или поздно преподаватель «догонит» открытую дверь и сможет выйти.

Пример. Пронумеруем коробочки числами от до Первыми семью вопросами узнаем про коробочки Если была найдена тройка коробочек, в которой лежит монетка, то оставим из этой тройки только две, добавив третью, заведомо пустую коробку (например, из другой тройки). Если при такой проверке Гриша получит тройку без монетки, то монетка была в третьей коробоке из тройки. Если монетка по-прежнему присутствует, то из пары коробочек оставим одну, дополнив двумя пустыми коробочками. Монетка будет определена. Если же монетки не оказалось ни в одной из коробок с номерами то на восьмой раз Гриша указывает коробочки Тогда монетка будет или в паре или в паре Последним, девятым ходом, Гриша указывает и находит монетку.

Оценка. Меньше, чем за ходов Гриша не найдет монетку. Если за ходов он укажет суммарно меньше, чем на коробочки, то не сможет узнать, в какой из оставшихся монетка, если она там окажется. Если он укажет на то каждый раз — на три новых коробочки. Если монетка будет в последней тройке, то Гриша ее не найдет.

Выберем аккумуляторов и разобьем их на пар. Последний аккумулятор пока отложим. Первыми шестью операциями проверим эти пар. Либо хотя бы в одной из пар нам попадутся два рабочих аккумулятора и задача решена, либо в каждой паре будет хотя бы один разряженный. Поскольку разряженных тоже шесть, это означает, что в каждой из пар ровно один разряженный (и ровно один заряженный). Тогда отложенный -й аккумулятор заведомо рабочий. Выберем любой аккумулятор из первой пары и проверим его вместе с -м. Если первый был рабочий, лампочка загорится и задача решена. Если лампочка не загорелась, значит рабочий — второй из его пары и мы возьмем его вместе с -м.

(a) Достаточно привести алгоритм получения нуля, поскольку меньше получить невозможно. Итак, сначала поделим числа кроме единицы на пары написав в них разности, получим набор из единиц, включая первоначальную. Далее разбиваем числа на пары и в каждой паре получаем в качестве разности затем с нулями можно делать что угодно.

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

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

Запишем числа, которые будут получаться в течение некоторого времени:

Число 20 повторилось, значит, процесс зациклится. Через 3 минуты после начала на доске будет записано 20, и через каждые 5 минут оно снова будет появляться. Тогда через минут на доске запишут число 20. Можно продолжить цепочку:

Всего в строке и столбце, проходящих через данную клетку 19 клеток, поэтому если мы проделаем операции со всеми парами строк и столбцов таблицы (всего операций), то каждый знак в таблице поменяется 19 раз, став из минуса плюсом.

100 операций достаточно.

_________________________________________________________________________________________________________________________________________________________________________________

Операцию замены знаков во всех клетках некоторого столбца и некоторой строки будем называть операцией относительно клетки-пересечения этих строки и столбца. Клетки, относительно которых мы делали операции, назовём красными, остальные синими. Строки и столбцы, содержащие чётное число красных клеток назовём чётными, а содержащие нечётное число красных клеток — нечётными.

_________________________________________________________________________________________________________________________________________________________________________________

Допустим, можно поменять все знаки в таблице меньше чем за 100 операций, тогда рассмотрим некоторую синюю клетку в строке и столбце . Чтобы знак в поменялся, нужно, чтобы, чтобы и вместе содержали нечётное количество красных клеток, можно считать строку чётной, а столбец — нечётным.

Заметим, что на пересечении строки и столбца одинаковой чётности должна стоять красная клетка, а на пересечении строки и столбца разной чётности — синяя, иначе знак в этой клетке после всех операций не изменится. Следовательно, количество красных клеток в каждой чётной строке равно числу чётных столбцов, а количество синих — числу нечётных столбцов таблицы. Есть хотя бы одна чётная строка , значит, всего в таблице чётное число нечётных столбцов. Но количество красных клеток в каждой нечётной строке (нечётное!) равно числу нечётных столбцов, то есть чётному числу — противоречие с тем, что есть хотя бы один нечётный столбец. Следовательно, нельзя обойтись меньше, чем 100 операциями.

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

Поделим вершины на три группы: исходные, выбранные и хорошие (вершины будут перемещаться из группы в группу, но никакая вершина на может находиться в двух группах одновременно). Изначально все вершины находятся в группе исходных. Выберем среди них такие, в которые не входит ни одна синяя стрелка и отправим их в группу выбранных. Тогда, в силу транзитивности синих стрелок, в каждую исходную вершину ведет хотя бы одна синяя стрелка из выбранных вершин. Если так случилось, что между выбранными вершинами нет красных стрелок, то, приняв за множество выбранных вершин, мы решим задачу. Если же красные стрелки есть, то найдем все выбранные вершины, в которые ведет хотя бы одна красная стрелка из других выбранных, и отправим их в группу хороших. После этого, могло оказаться, что в некоторые исходные вершины не идет синей стрелки из выбранных. В этом случае добавим в множество выбранных те вершины из исходных, в которые синие стрелки приходят только из хороших вершин. После этого снова отправим в группу хороших те из выбранных вершин, в которые ведет хотя бы одна красная стрелка из других выбранных. В силу транзитивности теперь уже красных стрелок, в любую хорошую вершину все еще ведет хотя бы одна красная стрелка из выбранных. Будем продолжать такие перемещения (из исходных в выбранные, из выбранных в хорошие). Заметим, что если в некоторый момент мы не смогли уменьшить множество исходных вершин, то задача решена, а так как изначально там конечное число вершин, этот момент обязательно наступит.

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

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

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

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

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

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

Шаг  Половинным делением (начиная с за вопросов можно выяснить максимальную входящую степень буквы Пусть это Обозначим

Шаг  Задаём последовательно вопросы При этом: а) если мы получили ответ да, то останавливаемся и меняем на найденную строку. Мы увеличили на символов за вопросов. Снова запускаем шаг с новым б) Все ответов нет. Поскольку не входит в слово, это значит, что — конец слова при некотором Спрашиваем про пока не получили ответ нет. Мы потратили вопросов, увеличили длину известного подслова на при этом это подслово — конец загаданного. Итого, если длина полученного слова равна то мы потратили вопросов.

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