Двойной подсчёт

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

Сравним это число с

После сокращения факториалов получаем

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

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

Назовём антитреугольником тройку вершин, которые не образуют треугольник. Оценим число антитреугольников. Всего антирёбер

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

Пусть — степень -ой вершины в дополнительном графе. Каждый путь длины 2 содержит ровно одну центральную вершину, так что

По неравенству о средних оценим

Тогда всего антитреугольников не более, чем

Подставляя в оценку из условия вместо получаем:

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Каждый появляется каждый раз, когда является концом ребра из , то есть раз; всего пар , значит вычитается раз. По неравенству Коши–Буняковского:

Наконец, сумма Следовательно,

Каждая пара элементов встречается только в одном из подмножеств. Всего в элементном множестве пар элементов. Каждое трёхэлементное множество содержит пары элементов. Значит,

что и требовалось.

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

или же

Левая часть возрастает на натуральных и при неравенство не выполняется. Следовательно,

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

Тогда троек, не подходящих по условию, вдвое меньше: 780. А подходящих троек

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

а полных подграфов на пяти вершинах не более

что и требовалось доказать.

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

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

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

Отсюда и что и требовалось доказать.

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

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

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

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

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

Пусть клетка с координатами имеет вес тогда в процессе сумма весов клеток для каждой фишки не изменяется, ведь

Предположим, что мы добились того, что в этих трёх клетках нет фишек. Изначально сумма весов была равна 2. По итогу она меньше, чем сумма весов всех клеток, кроме этих трёх. Если считать по столбцам, то эта сумма равна:

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

Но тогда получаем противоречие, ведь сумма весов не могла стать меньше 2. А значит, требуемое доказано.

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

Пусть Тогда рассмотрим ситуацию, где все печеньки находятся у Никиты. Его вес равен 1. Тогда сумма весов печенек меньше и если бы в процессе печенька появилась у Вити, то сумма весов стала бы не меньше Отсюда получаем противоречие. Значит, не подходит.

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

что меньше изначальной суммы весов у этих людей, откуда и получаем противоречие.

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

У каждого -тетрамино есть линия сетки, которая разрезает ее на два домино. Сопоставим каждой фигуре одну такую линию. В квадрате имеется внутренних вертикальных и внутренних горизонтальных линий, всего Тогда по принципу Дирихле найдётся линия, которая пересекает не менее

фигур, то есть она разрезает как минимум шесть -тетрамино на две фигурки из двух клеток.

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

(a) Можно считать, что каждый ряд нажат не более раз. Значит, можно считать, что и для всех Вернём таблицу к нулям так: нажмём -ю строку ещё раз, а -й столбец ещё раз. Тогда в каждой клетке окажется нуль. При этом каждая строка и каждый столбец нажимаются не более раз, всего не более нажатий.

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

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

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

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

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