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

Действительно, если радиус вписанной окружности равен 1, то сторона правильного шестиугольника равна . А длина ломаной по намеченному пути равна

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

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

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

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

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

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

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

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

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

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

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

Пронумеруем все единицы, начиная с самой левой, натуральными числами от до Единице с номером поставим число где — количество нулей, которые находятся правее нее. Рассмотрим величину

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

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

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

Пронумеруем все клетки, начиная с крайней левой, в которой находится камень, натуральными числами от до Пусть в клетки с номером в начале лежит камней. Рассмотрим величину

Докажем, что значение является инвариантом. Действительно, пусть за ход два камня из клетки с номером переложили в клетку с номером Пусть — значение после хода, тогда

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

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

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

1) Рядом с 2 стоит 3. Тогда рядом с 3 может стоять только 1. Ее сосед — это только 4 и рядом с 4 может встать только 6.

2) Рядом с 2 стоит 4. Тогда рядом с 4 может стоять или .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим противное — пусть существует алгоритм, позволяющий найти фальшивую монету из монет за ходов.

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

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

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

Которые соответствуют случаю, когда все взвешиваний были сделаны правильно. Ясно, что такой лист только один;

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

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

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

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

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

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

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

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

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

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

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

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