Применение классических комбинаторных методов к разным задачам

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

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

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

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

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

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

Рассмотрим школьников на чётных позициях. Заметим, что среди них нет двух подряд девочек, откуда получаем, что на чётных позициях не более половины девочек. Аналогично на нечётных позициях не более половины девочек, а значит девочек не более 30.

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

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

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

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

Пойдем с конца. Так как последним действием Якс вычитал то ли 3, то ли 4, и получил 2018, то перед этим у него могло быть число или Предпоследним действием Якс прибавлял то ли 3 , то ли Значит, если после этого у него получилось 2021, то могло быть либо , либо если у него получилось 2022, то могло быть либо , либо Итак, после первого действия у Якса получилось либо 2017, либо 2018, либо 2019. И это число было получено в результате умножения количества звезд то ли на 3 , то ли на 4. Но на 4 вообще ни одно из этих чисел не делится, а на 3 – только 2019. Значит, Якс все-таки умножал на 3 и получил 2019. Поэтому звезд на небе .

Количество приличных буквенных слов равно Для данного количество слов из букв, в которых первые букв образуют неприличное слово, равно

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

Таким образом, количество слов, в суффиксе или префиксе которых стоит неприличное слово, не больше (в предъявленном подсчете участвуют все такие слова, но некоторые могли быть подсчитаны более одного раза), чем

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

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

Если граф — это цикл, содержащий 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, значит количества оборотов и равны при Отсюда имеем …, Тогда сумма

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

Первое решение. Назовём дискриминантом пары чисел величину

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

Далее, верны следующие соотношения:

и

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

______________________________________________________________________________________________________________________________________________________

Второе решение. Если на доске написана пара то с помощью первой операции можно добавить пары

Обе этим пары можно записать как

где в первом случае а во втором — С помощью второй операции можно добавить только пару

______________________________________________________________________________________________________________________________________________________

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

Для пары утверждение задачи верно. Далее, рассмотрим два типа операций:

Тогда для новой пары верно

Здесь также получаем нужное неравенство:

______________________________________________________________________________________________________________________________________________________

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

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

Способ 1

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

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

Способ 2

Пусть — наименьшее простое число в этом ряду большее По китайской теореме об остатках существует такое число (), что

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

Способ 3

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

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

Если то на делится каждое -ое число в ряду (*) и или Следовательно,

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

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

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

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

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

Можно считать, что исходные положительные числа расположены в порядке возрастания: Рассмотрим

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

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

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

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

Расположим длины частей, на которые разбили отрезок длины в порядке невозрастания где — длины.

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

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

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

Откуда Но сумма всех отрезков это Значит, При этом потому что это длина кусочка от отрезка длины И тогда можно взять тройку отрезков для которой выполнены неравенства

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

Пример. Отметим в третьей, шестой, девятой, , 48 строках все клетки в столбцах, номера которых не дают остаток 1 при делении на 3. Тогда в каждой из этих 16 строк отмечено по 33 клетки — всего клеток.

Оценка. Докажем методом математической индукции, что на доске меньше клеток отметить нельзя. База для очевидна.

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