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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

Из первого условия следует, что ровно у точек оба соседа белые, а из второго — что ровно у точек оба соседа черные. Это означает, что у оставшихся точек соседи разного цвета.

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

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

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

Остальные выражаются аналогично. Тогда часов.

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

Ясно, что у каждого есть одинаковое количество друзей, обозначим его через Рассмотрим ребёнка и его друзей.

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

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

Этим решениям соответствуют и Примеры строятся в соответствии с решением: групп по ребят. Внутри групп ребята дружат, а ребята из разных групп враждуют.

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

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

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

Сумма чисел в вершинах каждого треугольника равняется Поэтому сумма чисел во всех углах стопки должна делиться на Но если в каждом углу стопки сумма чисел равна то сумма всех чисел равна — не делится на

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

Заметим, что минимум этого выражения достигается при или поскольку нечётно, а — целое. Тогда просуммируем по ученикам эту величину. Получим

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

Тогда То есть ЧТД.

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

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

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

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

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

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

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

Обозначим Предположим, что каждые две фракции имеют не более трёх общих членов.

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

Очевидно, что списков, которые составил не меньше, чем списков, которые составил то есть

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

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