Графы и турниры

Рассмотрим каждую пару мальчик-девочка. Всего таких пар Заметим, что если девочка стоит левее мальчика, то мальчик посчитает девочку, а девочка этого мальчика не посчитает. Наоборот, если мальчик стоит левее девочки, то девочка этого мальчика посчитает, а мальчик эту девочку не посчитает. В итоге в каждой паре ровно один ребенок считает другого. Значит, сумма всех чисел будет равна общему количеству пар, то есть

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

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

Решение 1. Нарисуем таблицу с столбцами и строками. Когда ребенок съедает конфету, будем в очередную клетку соответствующего столбика, писать, сколько денег он заплатил в кассу.

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

______________________________________________________________________________________________________________________________________________________

Решение 2. Рассмотрим одну пару детей. Заметим, что в каждой такой паре ровно раз один ребенок платит за другого: один раз, когда съедается первая конфета, один раз, когда съедается вторая конфета, и т. д., последний раз, когда съедается последняя восьмая конфета. Значит, за каждую пару касса получает 8 рублей. Всего пар детей значит, заработок кассы равен рублям.

Пронумеруем людей числами от до . Заметим, что при могут созвониться сначала и , потом и , потом и , и в конце и . Тогда все будут знать все новости. Пусть мы умеем организовывать созвон для человека. Научимся организовывать для . Сначала пусть созвонятся и . Теперь знает две новости. Далее организуем созвон для человека. А потом могут созвониться опять и . Легко видеть, что все будут знать все новости, а количество звонков стало равно .

Обозначим количество мальчиков через , а девочек — через . Тогда количество рёбер со стороны мальчиков равно , а со стороны девочек оно равно . Так как это на самом деле все рёбра в графе, мы получаем . Из этого равенства следует, что делится на 4. Пусть , тогда из равенства выше получаем, что , а общее количество детей равно — число, делящееся на 7.

Раскрасим строки доски в 2 цвета: строки с нечётными номерами в первый, а с чётными — во второй. Тогда слон каждый раз будет менять цвет, на котором стоит. Чёрных клеток второго цвета 16, поэтому всего слон сможет посетить не более клеток.

Приведём пример, в котором посетим 33 клетки. Начнём с пойдём по двум нижним строкам: далее пойдём в Заметим, что мы оказались в угловой клетке пустой доски причём нам нужно обойти 25 клеток. Используем аналогичный обход двух строк, окажемся в клетке и так далее. В итоге мы посетим 33 клетки и закончим в

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

(a) Проведём индукцию по База для верна. Пусть в любом связном графе с вершиной хотя бы ребра. Покажем, что в связном графе с вершинами хотя бы ребро. Пусть степени всех вершин хотя бы 2. Тогда суммарная степень хотя бы а значит, рёбер хотя бы Пусть нашлась вершина степень которой не более 1. Если ее степень равна 0, то в графе всего 1 вершина, поскольку граф связен, и утверждение задачи верно. Пусть теперь степень равна 1. Тогда удалим эту вершину вместе с исходящим из неё ребром. Предположим, что нарушилась связность. Тогда есть какие-то 2 вершины и путь между которыми обязательно проходил через Но степень равна 1, значит, на пути мы зашли в и вышли по тому же ребру. Тогда рассмотрим такой же путь, но без захода в Так можно удалить все посещения на пути, значит, связность не нарушилась. Тогда можно применить предположение индукции. В графе с удаленной вершиной не менее ребер, следовательно, в исходном графе не менее ребер.

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

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

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

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

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

Возьмём вершину степени 10 и поместим на первый уровень. На второй уровень поместим всех соседей . На третий уровень поместим всех соседей соседей , ещё не появившихся на картинке, и так далее. У нас образуется 10 “веточек”, началами которых будут соседи . Посмотрим, чем заканчивается каждая веточка, то есть на самые низкие вершины веточки. Из них и выходит по одному ребру: только наверх, рёбра не могут идти на тот же уровень или вниз. При этом в каждой веточке есть хотя бы одна самая низкая вершина, что нам и даёт искомые 10 вершин.

Рассмотрим граф с вершинами в узлах сетки и ребрами — отрезочками между узлами. Заметим, что в графе есть 8 вершин нечетной степени (по 2 на каждой стороне). Заметим, что как минимум в 6 из них наш маршрут не начинается и не заканчивается. А значит, мы входили в эти вершины столько же раз, сколько и выходили из них. То есть для каждой такой вершины одно из ее ребер было пройдено дважды. Отметим для каждой из наших вершин такое ребро. Заметим, что одно и то же ребро может быть отмечено не более 2 раз (по одному раз для каждого конца). Поэтому мы прошли дважды хотя бы по 3 ребрам. Поэтому длина нашего пути не меньше, чем метров.

Теперь приведем пример. Начнем из второго сверху перекрестка на самой правой улице. Сначала обойдем всю границу. Мы вернулись в начальный перекресток. Теперь идем так: влево, вверх, влево, вниз, влево, вниз, вправо, вниз, вправо, вверх, вверх, влево, вниз, вправо, вправо. В итоге как раз получится 2700 метров.

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

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

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

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

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

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

Построим граф: вершины — города, ребра — дороги. Городов в стране четное количество, по лемме о рукопожатиях, пронумеруем города от до . Проведём дополнительных ребер: между и , и , …, и (ребра могли получится кратными). Полученный граф является эйлеровым. Давайте начнем путь по циклу из вершины по добавленному ребру, и поочередно отдавать дороги компаниям. В конце процесса у всех кроме, возможно, вершины ровно по 2 дороги каждой компании. У есть настоящие ребра обеих компаний, так как мы в какой-то момент зашли и вышли из нее. Затем уберём добавленные ребра, для любой вершины будет выполнятся условие, так как мы убрали всего одного ребро, исходящее из нее.

Рассмотрим граф, вершинами которого являются пары цифр (упорядоченные). Количество таких пар (каждое из 2 чисел можно выбрать 10 способами). Будем проводить стрелочку из вершины в вершину , если второе число равно первому числу . Заметим, что из каждой вершины выходит 10 ребер и входит 10 ребер. Если мы сотрем ориентацию на ребрах, то легко видеть, что полученный граф будет связным. Тогда также как и во второй задаче найдем ориентированный цикл, содержащий все ребра. Заметим, что каждой последовательности из 3 чисел соответствует ровно 1 ребро (между первыми двумя числами и последними двумя числами). Выпишем сначала произвольную пару чисел, а затем будем дописывать следующую согласно нашему циклу (то есть, если мы выписали числа из вершины , а следующей в нашем цикле является вершина , то допишем на доску последнюю цифру и так далее). Поскольку мы прошли по всем ребрам ровно 1 раз, у нас встретятся все комбинации из 3 чисел, причем ровно по 1 разу, что и требовалось.