Считаем рёбра

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

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

Обозначим количество городов в группах и через и соответственно, Пусть в городов не меньше, чем в то есть В есть город Z, из которого выходит не менее дорог в города из Кроме того, из выходит дорог к городам группы Значит, из выходит не менее дорог. Противоречие.

Случай, когда в больше городов, чем в рассматривается аналогично.

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

Теперь приведём пример на Нужно ставить королей в следующем порядке на клетки с координатами:

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

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

Значит, между этими подграфами не более рёбер. Внутри же каждого из этих подграфов не более рёбер. Значит, всего в графе не более

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

_________________________________________________________________________________________________________________________________________________________________________________

Приведём пример на рёбер. Разбиваем города на групп по городов. Внутри групп между городами авиалиний нет, а между городами из разных групп — есть.

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

по неравенству между средним квадратическим и средним арифметическим

Мы показали, что для произвольного подграфа в примере выполняется условие задачи.

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

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

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

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

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

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

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

Следовательно,

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

Складывая эти неравенства по всем неупорядоченным парам смежных вершин многогранника, получаем

По доказанному выше неравенству отсюда следует требуемая оценка.

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

Рассмотрим граф, в котором вершины — ребра, города — дороги. Выделим в нем максимальную антиклику . Если она размера 7 или более, то нам повезло. Иначе отделим эти вершины, а в оставшемся графе снова выберем максимальную антиклику . Наберем таким образом 8 непересекающихся антиклик. Теперь в одну часть отнесем все вершины этих восьми антиклик (их будет не более ), а во вторую часть — все оставшиеся вершины. Заметим, что любая оставшаяся вершина имеет хотя бы по одной смежной в каждой антиклике, иначе на очередном шаге эту вершину можно было бы присоединить к этой антиклике. Следовательно, из каждой вершины второй части, которых хотя бы 52, выходит не менее 8 ребер в первую часть. Итого, не менее 416 ребер между частями. Противоречие.

Рассмотрим произвольного человека и его друзей. Если среди этих друзей есть друг который знаком с двумя другими друзьями то может пригласить и их двух общих друзей.

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

Первое решение. Докажем сначала следующую лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем по индукции.

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

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

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

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

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

Второе решение. Cначала докажем лемму.

Лемма. Если в графе на вершинах нет треугольников, то в нём не более рёбер. Докажем это.

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

Давайте предположим, что в полученном графе нет треугольников. Тогда по лемме в графе не более рёбер, но их Пришли к противоречию.

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

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

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

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

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

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

Приведём пример на Введём систему координат так, что левая нижняя точка имеет координаты Удалим все рёбра, соединяющие вершины с координатами и — чётное.

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

Разделим ребра на два типа: те, что соединяют две клетки из одной вертикали и те, что соединяют две клетки из одной горизонтали.

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

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