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

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

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

где и — количество конфет у -го и -го школьников до передачи.

Введём функцию энергии системы:

При передаче конфет от школьника к изменение энергии составит:

Из условия следует:

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

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

1.

От школьника к конфет

2.

От школьника к конфет

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

Рассмотрим граф, в котором вершинам соответствуют люди, а ребра между вершинами проведены, если соответствующие дети — участники одного марафона. С переходом человека между марафонами все ребра внутри прошлого марафона удаляются, и появляются ребра внутри нового марафона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим сумму обратных величин к числам на доске и исследуем, как она изменяется при указанных операциях. Заменяя пару чисел и на корни и трехчлена мы заменяем в этой сумме слагаемое на

Так как и —- числа из интервала имеем и откуда

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

Решение 2. Как и в первом решении, отметим, что все числа на доске всегда принадлежат интервалу Кроме того, заметим, что корни трехчлена где лежат между числами и на числовой оси. Действительно, из равенства и ранее доказанной положительности корней следует, что и А из равенства и ранее доказанных неравенств и следует, что и . Таким образом, если у трехчлена есть два корня, то и корни лежат в интервале Следовательно, минимум из чисел на доске не уменьшается, значит, все числа будут не меньше некоторого положительного числа (равного минимуму из исходных чисел).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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