Применение классических комбинаторных методов к разным задачам

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

 – количество способов выбрать подграф  – количество способов выбрать цвет  – количество способов раскрасить оставшиеся ребра.

По принципу Дирихле, существует раскраска графа, в которой число одноцветных подграфов составляет хотя бы

что и требовалось доказать.

Обозначим Предположим, что каждые две фракции имеют не более трёх общих членов.

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

Очевидно, что списков, которые составил не меньше, чем списков, которые составил то есть

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

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

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

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

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

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

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

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

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

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

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

Тогда получим:

— число тыкв в конце у каждого человека за столом (в порядке раздачи тыкв)

— число тыкв после раздачи тыкв -ым

— число тыкв после раздачи -его

— число тыкв после раздачи тыкв -ым

— число тыкв после раздачи тыкв -ым

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

Рассмотрим ситуацию с конца, пронумеруем расы жителей. Пусть оставшийся житель принадлежал к расе раса — раса, которую убивает раса а раса — оставшаяся.

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

Тогда к расе принадлежало нечетное число жителей (выживший и все, погибшие от рук расы ), к расе принадлежало нечетное число жителей (все жертвы расы ), а к расе принадлежало четное число жителей (все павшие в бою с расой ).

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

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

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

откуда и следует искомое.

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

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

Очевидно, что количество вирусов в -ую секунду — Докажем тогда по индукции, что число бактерий в -ую секунду —

База индукции. — что верно.

Предположение индукции. Пусть для всех верно, что — число бактерий в -ую секунду.

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

Итого, утверждение доказано. В -ую секунду у нас бактерий. А значит, через ровно через секунд все бактерии будут уничтожены.

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

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

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

Рассмотрим сумму произведений соседних чисел. Пусть мы поменяли местами числа и с соседями и и соответственно. Тогда наша сумма изменится на величину

т.к. Значит, при наших операциях эта сумма не меняется.

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

т.к. все числа попарно различны по условию. Значит, мы не можем получить искомую расстановку.

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

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

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

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

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

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

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

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

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

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