Графы и турниры → .04 Считаем рёбра

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

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

Действительно, все рёбра, выходящие из вершин с номерами от до делятся на два типа:

идущие в вершины с номерами от до — таких не болыше

идущие в вершины с номерами от до — таких не больше но каждое мы можем посчитать по два раза.

В задаче нас спрашивают, существует ли граф со степенями вершин Предположим, что он существует, и воспользуемся доказанным утверждением для первых пяти вершин:

противоречие.

Пронумеруем олигархов и их города числами от до соответственно.

Пример.

Пусть дорога между городами и принадлежит олигарху под номером тогда и только тогда, когда Тогда количество дорог равно

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

Оценка 1.

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

Рассмотрим произвольную тройку олигархов и Докажем, что эта тройка сопоставлена не более чем одной дороге.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Оценка 2.

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

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

База очевидна.

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

ребер.

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

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

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

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

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

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

Тогда

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

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

С другой стороны, по условию есть ученики, поздоровавшиеся ровно с

школьниками, и они не находятся среди Поэтому учеников в школе не меньше, чем

Таким образом, справедливы неравенства

Складывая их, мы получим

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Первое решение на самом деле дает оценку на человека, второе — даже на человек.

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

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

Первоначально имеем граф с 125 вершинами, причем степень каждой вершины равна 10. Поэтому число всех ребер графа равно Предположим, что утверждение задачи неверно, то удалось найти вершин (студентов), никакие две из которых не соединены ребром (студенты не знакомы), и при удалении которых вместе с ребрами, из них выходящими (студенты ушли), остается подграф с вершинами, каждая из которых имеет одну и ту же степень . В этом новом графе число ребер равно , и оно на меньше числа ребер исходного графа (т.к. с каждой удаленной вершиной «исчезают» 10 ребер, выходящих из этой вершины, и все «исчезающие» ребра различны). Таким образом,

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

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

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

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

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

Введём граф, вершинами которого являются ученики, а рёбра соединяют учеников из разных школ. Покрасим ребро в синий, если двое знакомы, и в красный — если не знакомы. Назовём синей или красной галочкой тройку учащихся из разных школ, где один из них соединён рёбрами одинакового цвета с двумя другими.

Посчитаем общее число таких галочек. Каждые трое учеников из разных школ образуют хотя бы одну галочку: между ними три рёбра, и по принципу Дирихле найдутся два одного цвета, которые и задают нужную конструкцию. Таких троек всего

Рассмотрим, на какие пары учеников из разных школ опираются галочки — то есть те двое, которые не являются главным учеником. Таких пар

так как выбираем по паре из каждой пары школ.

По принципу Дирихле найдётся хотя бы одна пара, на которую приходится не менее

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

Рассмотрим ребро соединяющее вершины с числами и Обозначим через количество вершин в компоненте связности, содержащей при удалении ребра Тогда:

где — количество вершин в компоненте, содержащей Для любого ребра верны неравенства:

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

Заметим, что:

Применим неравенство Коши для ребра

Суммируя по всем рёбрам дерева, получим:

Заметим, что для каждого коэффициент при суммировании равен

Таким образом, требуемое неравенство доказано.

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

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

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

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