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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

откуда и следует искомое.

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

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

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

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

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

С одной стороны, так как на предметы записались 60, 50 и 40 человек, то и сданных тетрадок по арифмантике будет 60, по УЗМС — 50, а по прорицаниям — 40. В сумме получается сданных тетрадок.

С другой стороны, студенты, записавшиеся на один курс, сдадут по одной тетрадке, и так как таких студентов то и сданных ими тетрадок будет Студенты, записавшиеся на два курса, сдадут по две тетрадки, и так как таких студентов тоже то они сдадут всего тетрадок. Наконец, студентов, записавшихся на все три предмета, сдадут тетрадок. Поэтому всего сданных тетрадок будет

Приравняем посчитанные двумя способами тетрадки.

Итак, значит, в одном списке 25 человек. Именно это число нам и нужно было посчитать в задаче.

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

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

Ничья взаимна (если A сыграл вничью с B, то B сыграл вничью с A). Пусть за ничью каждый получает по очку. Тогда суммируя эти очки по всем играм вничью, получим четное число (за каждую игру отдаем 2 очка), а по игрокам — нечетное (). Получили противоречие.

Сумма всех чисел таблицы по столбцам равна , значит, строк там .