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

Оценка.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Оценка.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим наклеивание -го куска . Пусть до этого между двумя клетками был путь с не более сменами цвета. Если он не заходил в , то он таким и остался. Иначе заменим его кусок от первой его клетки в до последней такой клетки на путь по между этими клетками. Тогда количество смен цвета в новом пути увеличилось не более чем на 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 человек, противоречие. Значит, люди этой группы — преступники.

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

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

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

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

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

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

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