Текстовые задачи на конструктивы в комбе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предъявим конкретное взвешивание: на первую чашу весов кладём пять самых лёгких гирь, на вторую три самые тяжёлые. Действительно, если утверждение “любые пять камней вместе тяжелее любых трех” верно, то весы очевидно покажут перевес на первой чаше. Если же утверждение неверно, то есть можно выбрать пятёрку камней и тройку камней, что суммарный вес пятёрки не больше веса тройки. А поскольку суммарный вес любых пяти камней как минимум вес пяти самых лёгких, а суммарный вес любых трёх камней не больше веса трёх самых лёгких, весы гарантированно покажут не перевес первой чаши. Соответственно мы различим исходы и сделаем верный вывод.

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

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

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

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

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

База для : Квадрат без угловой клетки является уголком из трёх клеток, поэтому база очевидна.

Переход:

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

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

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

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

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

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

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

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

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

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

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

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

За три взвешивания— возможно.

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

Пронумеруем монеты от до Первое взвешивание: монеты на первой чаше, а на второй.

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

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

Каждую гирю мы можем либо взять, либо нет.

Используя гирь, мы можем различить максимум весов, что меньше чем

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

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

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

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

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