Комбинаторика на Питергоре

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Если салфетку пересекают вертикальные прямые, то самая левая и самая правая из них содержат ровно по одному узлу, накрытому салфеткой.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

(всего прямая). Рассмотрим очередную прямую на ней лежит узлов(на каждом шаге их количество уменьшается на 2). Если она не проведена, то эти узлы покрыты различными прямыми, что невозможно, поскольку нам осталось провести прямых. Значит, она проведена. Аналогично должна быть проведена и прямая Итак мы установили, что заведомо проведено прямых. Но при этом точки и всё ещё остались непокрытыми. Они являются вершинами прямоугольника и поэтому не могут быть покрыты одной прямой.

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

Пример.

Два возможных примера показаны на рисунке.

Оценка.
Решение 1.
Рассмотрим произвольного ребёнка. Если он не видит уха, то он смотрит в чей-то затылок. Тогда стоящий перед ним либо видит чьё-то ухо, либо также смотрит в затылок. Таким образом, мы получаем цепочку из стоящих в ряд детей, в которой самый первый ребёнок видит чьё-то ухо. Заметим, что в этой цепочке не более ребёнка. Поскольку общее количество детей равно то цепочек не меньше чем Значит, их хотя бы Стало быть, как минимум ребёнка видят чьё-то ухо.
Решение 2.
Рассмотрим произвольного ребёнка. Пусть для определённости он смотрит "вправо"(см. рис). Если он не видит уха, то он смотрит в чей-то затылок. Тогда стоящий перед ним также смотрит вправо и т.д., но самый правый ребёнок в этой строке должен смотреть вверх или вниз. Поэтому в этой строке есть хотя бы один ребёнок, который видит чьё-то ухо. Таким образом, если в какой-то строке есть ребёнок, смотрящий “горизонтально”, то в этой строке есть ребёнок, который видит ухо.

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

Рассмотрим теперь случай, когда в какой-то строке нет детей, смотрящих "горизонтально". Следовательно, они все смотрят "вертикально"и поворотом доски на этот случай сводится к уже рассмотренному.

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

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

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

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

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

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

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

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