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

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

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

Всего у каждого из семи подписанных на канал учеников может быть не более трёх хороших друзей. Следовательно, изначально количество хороших пар не превышает 21. Рассмотрим момент, когда на канал подписались все ученики, кроме одного. Тогда в момент, когда подпишется последний ученик, количество хороших пар уменьшится уже на 3, следовательно, подписок может быть не более чем 19. Так как в классе всего 28 человек, то весь класс не может быть подписан на канал.

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

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

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

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

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

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

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

Приведем стратегию за мудрецов. Пусть мудрецы говорят “пас” до того момента, пока очередь не дойдет до первого мудреца, цвета шляп всех мудрецов перед которым имеют один и тот же цвет. Этот мудрец назовет цвет противоположный тому, шляпы которого надеты на всех предстоящий мудрецах. Каждый следующий вновь скажет “пас”.

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

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

Поскольку все раздачи шляп равновероятны, мудрецы проигрывают с вероятностью

а значит, вероятность выиграть больше

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

База. Все клеток в одной строке. Если они стоят подряд, то есть в точности квадратов. А если не подряд, то ещё меньше.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Запишем в клетки доски положительные целые числа так: число записано в каждой клетке й диагонали, параллельной главной диагонали, идущей слева сверху вправо вниз (ниже приведен пример для доски

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Первое решение.

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

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

Будем теперь класть на весы по одному куски массами именно в этом порядке. Начальная масса кучки на весах будет равна а конечная — так как

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

Второе решение.

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

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

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

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

Приведем пример размещения ягод. В чашки с нечетными номерами положим по вишен, а в чашки с четными номерами по вишен. Всего получится вишен. Далее съедим по две вишни из чашек с номерами и Останется вишни.

Первое решение. Назовём числа 0, 1, …, 49 маленькими, а остальные числа, которые могут появиться на табло, т.е. числа 50, 51, …, 99 — большими. Заметим, что после нажатия из маленького числа обязательно получается большое, а из большого числа — маленькое. Значит, после нечётного количества операций на табло будет гореть большое число.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Выстроим все целые числа от 0 до 99 в цепочку

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Первое решение

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

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

База индукции:

Числа от 1 до 4 можно выписать по кругу четырьмя различными способами:

Хорошими в них будут единственные пары:

При этом База индукции выполнена.

Шаг индукции.

Пусть утверждение индукции выполнено для всех количеств чисел от 4 до докажем для Рассмотрим все натуральные числа от 1 до выписанные в произвольном порядке. Заметим, что ни одна хорошая пара чисел не содержит число 1, и пара чисел, записанных слева и справа от 1, образуют хорошую пару. Назовем такую пару маленькой.

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

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

В итоге ответ — 97 хороших пар чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение

Рассмотрим произвольную запись по кругу в некотором порядке всех натуральных чисел от 1 до 100. Будем считать их расположенными в вершинах правильного 100-угольника, обозначим его Сначала докажем, что хорды, соответствующие двум разным хорошим парам чисел, не могут пересекаться по внутренним точкам.

Рассмотрим две хороших пары чисел в которых все 4 числа различны. Можно считать, что Если хорды, соответствующие этим парам, пересекаются по внутренней точке, то числа и лежат по разные стороны от хорды и оба больше что противоречит «хорошести» пары

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Подграф с новыми числами на рёбрах удовлетворяет условию с той же константой

Доказательство леммы. Заметим, что для каждого -рёбра есть одно и то же количество -шестёрок, в которые входят оба его конца. И наоборот, для любой -шестёрки среди 15 рёбер между её вершинами есть одно и то же количество -рёбер. То же верно для -рёбер и для -рёбер. Значит, сумма чисел на рёбрах в -шестёрке в новой расстановке есть среднее сумм по всем -шестёркам в старой расстановке, то есть среднее нескольких чисел, не больших – значит, Аналогичное утверждение верно для сумм в -шестёрках. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Далее изучаем новую расстановку. Рассмотрим случаи.

Случай Иными словами, есть ровно одна -шестёрка, на которой пятнадцать -рёбер, и шесть -шестёрок, на каждой из которых десять -рёбер и пять -рёбер. Имеем систему неравенств:

Умножим первое на сложим со вторым, умноженным на 3, получим откуда

Случай Теперь у нас две -вершины и пять -вершин, то есть на -шестёрке есть десять -рёбер и пять -рёбер, а на -шестёрке – шесть -рёбер, восемь -рёбер и одно -ребро. Имеем

Исключая получаем

значит,

Случай Аналогично предыдущему, имеем

Избавляясь на этот раз от получаем откуда

Случаи сводятся к рассмотренным умножением всех чисел на что ведёт к замене Итак, оценка доказана.

Пример. Любое число вершин от двух до 999995 объявим вершинами типа остальные – вершинами типа На всех рёбрах между двумя вершинами типа напишем число на всех остальных – число 1. Тогда, если в шестёрке вершин хотя бы пять -вершин, то сумма в ней не больше а иначе – не меньше

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

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

Доказательство проведём индукцией по

База: Если у каждой последовательности есть хотя бы один сосед, то

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

Для любой последовательности

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

Таким образом, в своём подмножестве или последовательность имеет не менее соседей.

По предположению индукции: и Следовательно:

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