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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

В качестве вершин графа для удобства отметим центры клеток. Нарисуем их зеленым цветом. Ребра графа проведем синим цветом.

Теперь нарисуем вершины по кругу, оставив одну вершину, ни с чем не соединенную, в центре, и соединим вершины ребрами. Обратите внимание на порядок вершин.

Вот одна из возможных картинок. Мы уменьшаем верхнюю грань и “схлопываем” ее с нижней.

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

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

По условию, изначально кони стоят в углах, то есть в вершинах и Пусть не умаляя общности белые кони стоят в вершинах и а черные — в и

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

Рассмотрим ориентированный граф, вершинам которого соответствуют депутаты, а рёбра идут от критикующего депутата к критикуемому.

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

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

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

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

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

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

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

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

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

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

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

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

откуда

Посчитаем рёбра в графе детей двумя способами – тогда их , где в классе мальчиков и девочек, однако тогда существует такое , что и , значит, число учеников в классе кратно 8. Между 30 и 35 такое число одно — 32.

Нарисуем ориентированный граф, где стрелка идет от человека к человеку , если ударил . Пусть всего человек. Тогда так как из каждого человека выходит по 4 стрелки, то всего стрелок . С другой стороны, так как в каждого человека входит 3 стрелки, то всего стрелок Противоречие.

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

Пусть – число семиклассников, – число восьмиклассников; тогда Второе уравнение мы получим, если подсчитаем двумя способами общее количество рукопожатий. С одной стороны, число рукопожатий равно , поскольку от каждого семиклассника «исходит» 8 рукопожатий. С другой стороны, число рукопожатий равно , так как от каждого восьмиклассника «исходит» 7 рукопожатий. Следовательно, Решая полученную систему уравнений, находим: .

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

Если граф — это цикл, содержащий 101 вершину, то на любых 100 вершинах ровно 99 рёбер, так что такая компания удовлетворяет условиям задачи. Осталось показать, что не существует такой компании из 102 человек (тогда и компании из более чем 102 человек тоже быть не может). Ниже мы приведём несколько различных способов сделать это; в каждом способе мы предполагаем, от противного, что такая компания нашлась.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Докажем, что компании из человек быть не может. Назовём вершину чётной, если её степень чётна, и нечётной иначе.

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

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

что нечётно. Противоречие.

Удобно рассуждать на соответствующем графе. Шпионы – вершины графа, пары шпионов – ребра графа. Всего ребер Донос шпиона А на шпиона В – это, скажем, раскрашивание ребра (А,В). Количество всех раскрашиваний равно, по условию . Количество раскрашиваний превышает количество ребер на Это означает, что найдутся не менее 10 дважды раскрашенных ребра (ребро А,В) либо не раскрашено, либо раскрашено один раз, либо раскрашено дважды – как (А,В) и как (В,А). А это как раз то, что требовалось доказать.