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

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

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

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

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

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

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

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

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

Способ 1. Первые дней дворник сгребает снег из второго столбца в первый, следующие дней дворник сгребает снег из третьего столбца во второй, затем дней из четвёртого в третий, и т. д. Через дней в десятом столбце не будет снега. Посчитаем, сколько снега стало в столбце через дней. Вечером -го дня в столбце номер не было снега, а в столбце в каждой клетке было по снега. На следующий вечер в столбце станет по снега в каждой клетке. Затем ещё десять дней количество снега в каждой клетке -го столбца будет увеличиваться на а затем дней — на Итого, через дней в каждой клетке столбца будет по

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

_________________________________________________________________________________________________________________________________________________________________________________

Способ 2. Пусть дворник сгребёт снег из -го столбца в -ый, из -го во -й, …, из -го в -ый. Тогда вечером девятого дня в первых девяти столбцах будет по дм снега в каждой клетке, а в десятом столбце снега не будем. Затем дворник проделывает аналогичный процесс в обратном порядке: из -го в -ый, из -го в -ый, …, из -го в первой. Тогда вечером -го дня в клетках последних девяти столбцов будет по снега, а в первом столбце не будет снега. Аналогично повторим такие сдвиги (каждый длится дней) ещё раз (всего сдвигов), и через дней получим в клетках девяти столбцов по снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более снега в каждой клетке.

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

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

• если то надо перевернуть карточки 53, 59, 61;
• если то надо перевернуть карточки 31, 37, 41;
• если то надо перевернуть карточки 23, 29, 31;
• если то надо перевернуть карточки 17 и 19, но между ними лишь число 18, что меньше, чем 16!;
• если то надо перевернуть карточки 11 и 13, но между ними лишь число 12, что меньше, чем 10!.

Далее, при и нужно перевернуть карточки 7 и 11. Заметим, что и поэтому при условие выполняется (произведение равно 720), а при не выполняется

Если то одна из перевернутых карточек — 7. Пусть число на второй карточке равно Заметим, что если то каждое из произведений вновь равно 720. Это второй подходящий вариант, но ответ тот же. Если то «внутреннее» произведение меньше 720, а «внешнее» не меньше 720. То же верно в случае, когда

Если то надо перевернуть карточки 5 и 7, но между ними число 6, а «внешнее» произведение не меньше 4!.

Если то перевернуты карточки 3 и 5, но

Если то одним из перевёрнутых чисел будет 5. Второе перевёрнутое число может быть только 1 или 2, иначе «внешнее» произведение делится на 3, а «внутреннее» — нет, но и тем более

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пронумеруем пробирки числами от до и бочки числами от до Назовем операцией последовательное наливание в пробирки номер номер ..., номер (именно в таком порядке) реактива из -ой бочки. Операцией назовем последовательное наливание реактива из -ой бочки в пробирки с номерами

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

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

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

Далее считаем, что и Обозначим все простые, меньшие кроме и через Рассмотрим

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

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

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

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

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

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

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

Сопоставим строке …, чисел от 1 до 100 последовательность из 99 знаков < и > в соответствии с тем, как упорядочены соседние числа. То есть если то -й знак в этой последовательности равен <, в противном случае он равен >.

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

Сопоставим каждой перестановке знаков расстановку чисел по следующему правилу (далее такие расстановки будем называть выделенными). При …, если (т.е. -й знак <) поставим на место наибольшее из не выбранных ранее чисел, если же — наименьшее из не выбранных ранее чисел.

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

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

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

Предположим, что первые знаков данной строки

и выделенной строки

совпадают. Если то и сами строки совпадают. Пусть Без ограничения общности будем считать, что

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

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

Приведем один из возможных алгоритмов, позволяющий Совунье обжарить котлеты всего за 6 минут. Пронумеруем котлеты числами 1, 2 и 3. Сначала кладем на сковородку котлеты 1 и 2 на две минуты. Через две минуты переворачиваем первую котлетку, вторую убираем со сковороды на тарелку, но добавляем третью котлету, и жарим первую и третью котлеты две минуты. Спустя 4 минуты после начала процесса первая котлета готова, и мы ее снимаем со сковороды и кладем на тарелку. Третью котлету переворачиваем, а вторую возвращаем на сковородку, кладя необжаренной стороной вниз. В итоге еще через 2 минуты мы получим 3 целиком готовые котлеты.