Комбинаторика на Высшей пробе: клетки, комбигео, игры, графы

Рассмотрим октаэдр. Пусть каждый человек соответствует вершине октаэдра.

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

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

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

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

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

Получается, что за команду сказали, что болеют человек, а за команду болеют . Так как болельщики проигравших команд не могут сказать, что болеют за свою команду, потому что это будет правда, то за команду будут болеть человек, а за команду , наоборот, — человек. Из этих соображений можно сказать точно, что , следовательно, за победителей будут болеть большее количество человек. Поэтому «Локомотив» и «Зенит» победили в своих играх, а «Спартак» и «Динамо» проиграли.

Пусть тогда за «Локомотив» по-настоящему болеют человек, за «Зенит» — , за «Спартак» — , за «Динамо» — . Получается, что после опроса за «Локомотив» болеют , за «Зенит» болеют , за «Спартак» болеют , а за «Динамо» — . Итого: болельщиков «Локомотива» , болельщиков «Зенита» , болельщиков «Спартака» , болельщиков «Динамо» .

Приведём выигрышную стратегию для Данила. Число клеток на поверхности чётно (равно Разобьём всю поверхность куба на доминошки; доминошки не пересекаются и покрывают весь куб. Легко видеть, что такие примеры есть. В начале хода Данила пешка стоит в какой-то доминошке. Данил ходит во вторую клетку доминошки. Если Данил до этого действовал в соответствии с этой стратегией, то вторая клетка доминошки не закрашена, и сделать в неё ход можно. Очевидно, что последний ход сделает Данил — хотя бы потому, что он всегда может сделать ход.

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

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

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

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

Предположим, что на поле можно разместить фигуры при , тогда можно разместить и при . Разобьём поле на 16 квадратов , тогда ровно в 12 из них будут стоять по 1 королю («к»), а в 4 других - 12 коней-лошадей («л») и 1 мяч, т.е. 13 фигур, значит, пустых квадратов быть не должно. Соответственно, квадраты будем называть к-квадраты и л-квадраты. Заметим, что если хотя бы в одном из л-квадратов две «л» стоят у общей стороны с другим квадратом, то этот соседний квадрат не будет содержать «к», значит, он должен быть л-квадратом, но тогда в сумме в этих двух квадратах разместится не более 4 фигур, т.к. клетки прямоугольника разбиваются на пары в виде хода «л», а во всех 4 л-квадратах разместится не более фигур, а должно быть 13. Кроме того, не существует л-квадратов с 4 «л» (аналогичные рассуждения). Значит, в каждом л-квадрате будет ровно 3 «л» и никакие 2 «л» не могут стоять парой у общей стороны с другим квадратом, следовательно, такие л-квадраты находятся в углах поля и 3 «л» стоят с краю всего поля, причём в одном из них ещё стоит и мяч.

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

Для уже можно построить пример. Отметим слоном мяч и поставим королей и коней.