Процессы и алгоритмы

Пусть есть две разные последовательности ходов. Они различаются в каком-то месте: в первой последовательности был сделан ход, перемещающий шарик из коробки в коробку а во второй — из коробки в коробку Докажем, что

1) ход будет обязательно сделан и в первой последовательности ходов;

2) этот ход можно сделать прямо перед ходом сохранив все остальные ходы (и итоговое расположение шариков в коробках).

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

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

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

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

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

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

Если число одного из мудрецов равно то он знает, что число другого мудреца равно либо либо ему остаётся определить только то, какая из этих двух возможностей имеет место. Когда мудрец отвечает на вопрос "Знаешь ли ты моё число?"в первый раз, он может ответить положительно только если его число равно (в этом случае число второго однозначно равно ). Если ответ был отрицательный, то второй мудрец узнает, что число не равно (хотя он это и так знает, если его число больше ). Далее, если при втором задании вопроса отвечает отрицательно, то узнает, что число не равно и (если число равно он наверняка знал бы, что число равно поскольку после первого вопроса он знает, что оно не равно ).

Пусть перед очередным вопросом одного из мудрецов (для определенности, ) обоим мудрецам известно, что число не равно а число не равно Если ответил отрицательно, то его число не равно (иначе он бы знал, что число равно также его число не равно (иначе он бы знал, что число равно поскольку оно не может быть равно ). Итак, в случае отрицательного ответа мы приходим к ситуации, аналогичной только что рассмотренной: перед вопросом B обоим мудрецам известно, что число не равно а число не равно

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

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

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

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

Мы получили три цифры — иначе говоря, трехзначное число. Далее определяем фальшивую монету по следующему рецепту:

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

Сначала заметим, что мы можем сделать циклический сдвиг букв в слове. Действительно, пусть у нас есть слово . Удвоим его и удалим буквы слева. Получили слово .

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

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

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

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

Последнее неравенство неверно по условию. Противоречие.

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

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

Запустим процесс, когда мы из одного самого большого числа вычитаем Останавливаем процесс, когда все числа становятся равными и Рассмотрим, как при такой замене меняется разница между суммой гор и суммой долин. Пусть мы вычитаем из наибольшей горы Есть три случая: либо два соседа становятся горами, либо только один сосед, либо никто. В первом случае сумма гор увеличилась на а сумма долин увеличилась на Во втором случае сумма гор уменьшилась на а сумма долин тоже уменьшилась на В третьем случае сумма гор уменьшилась на а сумма долин тоже уменьшилась на То есть при наших действиях требуемая величина не изменяется. Процесс когда-нибудь закончится, так как каждым ходом сумма всех чисел уменьшается, но отрицательных чисел мы не могли получить. Когда все числа либо либо у нас гор и долин с разницей

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

Решение 2. Переведем задачу на язык графов: пусть дан граф, в котором степень каждой вершины не превосходит требуется распределить вершины по трем группам так, чтобы степень каждой вершины внутри своей группы не превосходила Распределим вершины по трем группам произвольно. Предположим, что все же существует вершина, степень которой внутри ее группы По принципу Дирихле, в одной из двух оставшихся групп эта вершина имеет степень Переместим ее в эту группу. Ясно, что после этого действия количество ребер, проходящих внутри трех групп, уменьшилось хотя бы на Будем повторять это действие до тех пор, пока степень каждой вершины в своей группе не станет Описанный процесс конечен, так как с каждым его шагом уменьшается количество ребер, проведенных внутри трех групп, при этом изначально в графе было проведено конечное количество ребер.

Условимся называть “друзьями” любых двух рыцарей, не являющихся врагами; далее, начнем с того, что рассадим всех рыцарей за круглым столом произвольно. Пусть где-то за столом сидят рядом рыцарь и его враг для определенности будем считать, что сидит справа от Мы утверждаем, что за столом найдется такое место, где рядом сидят рыцари — друг и — друг причем сидит справа от В самом деле, рыцарь имеет не менее друзей; мест справа от них также имеется а врагов у не более — значит, хоть одно из мест справа от друга рыцаря занимает друг рыцаря Пересадим теперь в обратном порядке всех рыцарей, сидящих справа от начиная с рыцаря и вплоть до рыцаря Ясно, что при этом изменятся лишь пары и соседей — они заменятся на пары друзей и Таким образом, число пар сидящих рядом врагов уменьшится минимум на (оно уменьшится даже на если рыцари и — враги). Продолжая пересаживать рыцарей таким же образом и далее, Мерлин может окончательно разъединить за столом все пары сидящих рядом врагов.

Пусть по кругу стоят числа (нумерация циклическая по модулю 100). Всего есть два возможных варианта полученных сумм: и Докажем, что эти суммы равны.

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

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

Троек в круге четное число, так как при выкидывании сохранялась четность количества чисел в круге. Значит, если в круге троек, то первая сумма будет равна а вторая Суммы равны, что и требовалось доказать.

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

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

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

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

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

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

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

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

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

Кружков конечное число, поэтому этот процесс рано или поздно закончится.

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

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

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

Приведем последовательность этажей, начиная с 13-го и заканчивая 8-м, на которые надо ездить. При этом если следующий этаж выше текущего, то нажимать надо первую кнопку, а если выше, то вторую:

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

Приведем один из возможных примеров, как бурундучкам справиться с этой работой. Пронумеруем грузовики числами 1, 2, 3, 4 и 5. Расставим эти грузовики мысленно по кругу так, чтобы после пятого грузовика шел первый. Пусть за первый час бурундучки поменяют по одному колесу на грузовиках с номерами 1, 2, 3 и 4. Затем бурундучки переходят к следующим по часовой стрелке грузовикам и за второй час меняют по одному колесу на грузовиках 2, 3, 4 и 5. В третий час они меняют по одному колесу на грузовиках с номерами 3, 4, 5, 1. В четвертый час — на грузовиках с номерами 4, 5, 1 и 2, и, наконец, за пятый час они меняют колеса на грузовиках с номерами 5, 1, 2 и 3. Заметим, что над каждый грузовиком трудились ровно 4 часа. Значит, все 4 колеса бурундучки успели поменять.

Подожжем первый шнур с двух концов, а второй шнур с одного. Когда первый шнур целиком догорит, пройдет ровно 30 секунд, значит, второму шнуру, если ничего не изменится, также останется гореть 30 секунд. Но в этот момент мы подожжем его со второго конца. Тогда он догорит в два раза быстрее, то есть за 15 секунд. В итоге второй шнур горел всего секунд, именно это время нам и требовалось отмерить.