Комбинаторика на ОММО: графы, турниры, логика, Дирихле

Первое решение. Сведём задачу на язык графов. Вершины — команды. Ребро проводим между вершинами, если соответствующие команды сыграли между собой. Рассмотрим произвольные две вершины которые не соединены ребром (если таких нет, то рёбер в графе Рассмотрим произвольную вершину из оставшихся. Если в графе отстутствуют рёбра и то тройка не удовлетворяет условиям задачи. То есть хотя бы одно ребро из проведено. Итого, от каждой из оставшихся вершин к паре ведёт хотя бы одно ребро. То есть всего хотя бы рёбер. Теперь рассмотрим граф на оставшихся вершинах. В нём также выделим несмежные вершины (если такой не нашлось, то рёбер хотя бы ). Аналогичными рассуждениями получаем, что от каждой из оставшихся вершин (не ) к паре ведёт хотя бы рёбер. Будем делать такие «спуски», пока не закончатся вершины или пока не встретим полный подграф. Разберём оба случая.

1.

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

Теперь учтём остальные посчитанные рёбра. Их хотя бы

по формуле арифметической прогрессии. Итого, хотя бы

рёбер в графе. Так как — парабола с ветвями вверх и где — абсцисса вершины параболы, то при рёбер в графе хотя бы

2.

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

Таким образом, в графе в любом случае хотя бы рёбер. То есть у нас есть оценка, осталось построить пример на рёбер.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

База индукции: Оценка очевидна.

Шаг индукции: Пусть доказано для , докажем для .

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

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

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