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

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

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

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