Комбинаторика на устном туре Турнира Городов

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

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

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

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

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

Противоречие.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Оценка.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример, подтверждающий точность полученной оценки

хороших клеток уже возможно.

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

Оценка.

Можно считать, что первый наклеенный кусок — весь квадрат, от этого ничего не испортится. Считаем его нулевым. Докажем индукцией по утверждение:

_________________________________________________________________________________________________________________________________________________________________________________

После еще кусков между любыми двумя клетками есть путь с не более чем сменами цвета.

_________________________________________________________________________________________________________________________________________________________________________________

База при верна.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

В конце между противоположными углами любой путь имеет хотя бы 88 смен цвета. Значит, поверх нулевого куска наклеено еще хотя бы 44.

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

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

Положим и пусть и — количества синих и красных клеток. Оценим сверху количество общих сторон красных клеток с синими.

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

(1)

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

(2)

Из (1) и (2) следует, что

Поскольку получаем отсюда

Поскольку а целое, получаем нужный результат.

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

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

Воспользуемся методом математической индукции. Понятно, что для такая инструкция есть. Это база индукции. Теперь покажем, как из инструкции для сделать инструкцию для и для этого будет достаточно. Обозначим или Инструкция для будет выглядеть так:

I группа: сначала все пары вида в любом порядке

Если нечетно, сюда приходится добавить все пары вида при (назовём эти команды дополнительными).

II группа: инструкция для первых коробочек из индукционного предположения

III группа: все пары различных чисел вида в любом порядке

При длина этой инструкции не превышает

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

Есть четыре варианта того, как могут располагаться шарики основного цвета.

1) Они идут подряд, и все они среди левых коробок — ничего делать не надо;

2) Они идут подряд, и все они среди правых коробок — используем все пары вида ;

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

4) Шарики основного цвета — самые первые и самые последние. Перенеся последние влево (при нечётном используя дополнительные операции), получаем требуемое.

(Про это всё проще думать, если мыслить расположение коробочек не в ряд, а по окружности.)

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

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

Пример. Для прямоугольника получаем

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

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

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

Так как правильные слова покрывают весь кроссворд, сумма количеств клеток в них не меньше Каждое слово содержит не больше клеток, поэтому количество правильных слов не меньше Отсюда

Назовем слова, которые можно получить, достижимыми. Всего существует различных слов длины поэтому достаточно доказать, что количество достижимых слов длины равно Докажем это утверждение по индукции.

База индукции. Для и это легко проверяется: А АА, А АБ.

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

1.

из слова длины применив операцию а): W АW

2.

из слова длины применив операцию б): W WБ

3.

из слова длины применив операцию в): W БWА

Слов 1-го и 2-го типа по а слов 3-го типа При этом слова 3-го типа не могут совпадать со словами 1-го и 2-го типа. А вот множества слов 1-го и 2-го типа пересекаются. Их общие слова имеют вид АБ. Докажем, что слова (которые находятся между буквами А и Б) — это все достижимые слова длины Понятно, что если — достижимое слово, то за две операции из него можно получить АБ. С другой стороны, если слово Б достижимое, то посмотрим, как оно было получено. Если проделать все те же операции, но пропустить приписывание последней буквы Б, то будет получено слово значит, оно достижимое.

Таким образом, общих слов 1-го и 2-го типа столько же, сколько достижимых слов длины то есть Следовательно, количество слов длины равно что и требовалось доказать.

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

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

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

Пусть мы опросили людей. Опросим еще случайных людей из оставшихся. Разобьем 46 опрошенных людей на 4 группы по 11,11,11,13 человек. Пусть групшы, где 11 человек, будут отвечать на вопросы так, будто свидетели они и 4 неопрошенных человека, а группа из 13 человек будет отвечать на вопросы так, будто свидетели они и 2 любых неопрошенных. Так как мы не можем понять, какая из версий настоящая, то и преступника мы найти не сможем, ведь любой человек в какой-то из версий свидетель.

_________________________________________________________________________________________________________________________________________________________________________________

Выберем 47 человек и каждого спросим «Кто из жителей преступники?». Пусть каждый назвал 35 человек и никто не назвал себя, иначе преступник определяется очевидно. Разобьем всех людей на групшы так, что внутри одной группы ответы одинаковые.

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

Действительно, если в каждой группе хотя бы 12 человек, то если этих групп хотя бы 4 , то всего людей хотя бы , а если групп не более, чем 3 , то всего людей не более, чем — противоречие.

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

Первое решение.

Рассмотрим клетчатый квадрат размером и удалим из него внутренний центральный квадрат оставив только рамку толщиной 1. В рамке будет как раз 40 клеток. Докажем, что на плоскости нет клетчатого прямоугольника, содержащего ровно 20 из этих 40 клеток.

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

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

Второе решение.

Рассмотрим клетчатый прямоугольник и удалим из него клетки и Останется ровно 40 клеток. Предположим, что нашёлся клетчатый прямоугольник, в котором ровно 20 отмеченных клеток. Он может затрагивать одну, две или три горизонтали с номерами

Если он затрагивает одну горизонталь, то в нём не более 14 отмеченных клеток.

Если он задевает 2 горизонтали (одна из них — вторая), то он задевает вертикаль с номером 7 (иначе в нём не более 14 клеток). Тогда эта вертикаль вносит в прямоугольник нечётное число отмеченных клеток, а остальные — чётное. Поэтому общее число отмеченных клеток в прямоугольнике нечётно.

Если он задевает все три горизонтали, то число отмеченных клеток в нём либо кратно 3 (если он не задевает 7-й вертикали), либо имеет остаток 1 при делении на 3 (иначе).

В каждом из случаев получаем противоречие.

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

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

Утверждение 1. Покажем, что при таком определении производной для последовательности выполняется: производная суммы — это сумма производных.

Пусть дана последовательность, являющаяся суммой нескольких других последовательностей:

где — какие-то произвольных последовательностей. Тогда производная этой суммы:

В силу произвольности наше утверждение доказано.

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

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

Запишем по определению производной:

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

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

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

Кроме того, мы представили в виде суммы двух произведений хороших последовательностей. Далее по индукции, используя утверждения 1 и 2, получаем, что и все производные состоят из положительных чисел.

Первое решение.

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

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

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

Второе решение.

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

Рассмотрим две расстановки, отличающиеся ровно в одном месте. Запустим в них по роботу параллельно; тогда получающиеся расстановки всегда будут отличаться ровно в одном месте. В частности, итоговые цвета будут различны.

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

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

то после одного использования цвет сдвинется в противоположную сторону.

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

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

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

Осталось привести пример при Пусть участники пронумерованы от до и пары в кубке таковы (первым указан проигравший, вторым победитель): тогда при игре навылет пары могли быть такими (победитель снова указан вторым):

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

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

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

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