Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Вырежем из нашего куба куб и разобьём его на 64 куба .

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

В исходном кубе после этого остались кубики на трёх гранях, имеющих общую вершину. Рассмотрим 64 клетки на одной из этих граней, которые не лежат ни на какой из двух других. Они разбиваются на 16 квадратов , в каждом из которых не более трёх закрашенных ячеек. Итого на трёх гранях получаем не более .

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

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

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

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

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

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

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

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

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

Докажем теперь, что меньше 120 закрашенных клеток не может быть.

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

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

Сравним числа и

Пусть то есть В каждом столбце присутствуют хотя бы 6 синих клеток. Из взятого в качестве предположения неравенства следует, что в каком-то столбце количество красных клеток хотя бы от количества синих, то есть хотя бы 5, поэтому общее количество закрашенных клеток в данном столбце хотя бы 11, откуда и, следовательно, Если и оценка доказана. Предположим, тогда то есть не превосходит 10.

Но раз а в каком-то из наших не более чем 10 столбцов присутствуют хотя бы 6 красных клеток. Так как в нём должно быть ещё и 6 синих, мы получаем, что общее количество закрашенных клеток в этом столбце хотя бы 12, то есть, и Тогда, чтобы было меньше 120, необходимо Продолжим эти рассуждения.

Поскольку значит Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 7 красных клеток, откуда

Поскольку в каком-то столбце присутствуют хотя бы то есть хотя бы 8 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 9 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 11 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 15 красных клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.

Аналогично разбираем случай, когда то есть В каждой строке присутствуют хотя бы 5 красных клеток. Из взятого в качестве предположения неравенства следует, что в какой-то строке есть хотя бы 6 синих клеток, то есть общее количество закрашенных клеток в данной строке хотя бы 11, откуда и, следовательно, Если и оценка доказана. Предположим, тогда то есть не превосходит 10.

Но раз а в какой-то из наших не более чем 10 строк присутствуют хотя бы 7 синих клеток. Так как в ней должно быть ещё и 5 красных, мы получаем, что общее количество закрашенных клеток в этой строке хотя бы 12, то есть, и Тогда, чтобы было меньше 120, необходимо Продолжим эти рассуждения.

Поскольку в какой-то строке присутствуют хотя бы то есть хотя бы 8 синих клеток, откуда

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

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

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

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

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

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

Во-первых, поскольку количество вершин чётно, "длинных"диагоналей (соединяющий противоположные вершины многоугольника) пересекаются в центре многоугольника. Эта точка посчитана

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

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

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

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

точек меньше.

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

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

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

Нам нужно максимизировать это выражение, т.е. минимизировать сумму квадратов восьми чисел, сумма которых составляет 23. Как известно, сумма квадратов чисел уменьшается при сближении этих чисел к их среднему арифметическом, поэтому для целых чисел минимум достигается, когда семь из восьми чисел равны 3, а оставшееся равно 2.

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

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

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

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

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

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

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

С другой стороны, если Гензель будет каждый раз выбирать клетку, которая приносит максимальное количество очков, Гретель своим следующим ходом сможет набрать максимум на очка больше, так как добавлением одной фишки Гензель повышает “ценность” каждой из оставшихся клеток не более, чем на

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

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

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

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

Для каждой ячейки посчитаем сумму чисел ней и в её соседях и сложим все эти суммы. Полученное число будет не менее

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

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

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

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

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

В каждом столбце стоит одно чётное и одно нечётное число. Где стоит чётное число, а где нечётное, выбирается двумя способами, итого способов для всей таблицы. Далее, существует способов расставить чётные числа по выбранных для них местам и столько же способов расставить нечётные. Итого способов.

Построим контрпример. Разобьём города на групп по городов. Назовём эти группы

Внутри каждой группы соединим города рейсами компании номер

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

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

Это построение схематически изображено на рисунке. Разные компании обозначены разными цветами.