Применение классических комбинаторных методов к разным задачам → .03 Двойной подсчёт

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

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

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

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

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

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

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

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

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

Предположим противное. Пусть наборы

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

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

Сопоставляя это с неравенством заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности верных неравенств вида а в каждой тройке ровно два верных неравенства.

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

Каждый участник выбывает, потерпев ровно два поражения. В ситуации, когда остались двое “финалистов”, общее количество поражений равно .

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

Учитывая, что и — чётные числа, уравнения и не имеют решений.

Приходим к уравнению , откуда , а общее количество участников равно

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

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

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

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

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

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

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

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

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

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

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

Разобьем доску на квадратики . Покрасим их в шахматном порядке. Затем, сдвинем раскраску на 1 по диагонали. Легко проверить, что полученная раскраска подходит.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

Пример. Фишку 50 последовательно 99 раз меняем со следующей против часовой стрелки. Получаем требуемое расположение.

Есть несколько способов доказать оценку, ниже мы приведём два из них.

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

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

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

Тем самым, мы получаем, что фишки 1 и 100 совершают одинаковый сдвиг по и против часовой стрелки, поэтому они остаются на своих позициях. Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второй способ. Будем считать сдвиги фишек относительно их начальной позиции, причём сдвиг по часовой стрелке будет считаться с плюсом, против часовой — с минусом. Тогда при обмене двух фишек к сдвигу одной из них прибавляется +1, а другой — Значит, в результате проведённых операций общая сумма сдвигов будет равна 0.

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

Поскольку он должен равняться 0, имеем

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

— чётна, а значит не равна Противоречие.

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

Сложив почленно все эти неравенства, получим

что после сокращения на равносильно условию Так как — число целое, то Ситуация с возможна, например, если все ученики решили по задаче.