Комбинаторика на Всесибе: игры, графы, конструктивы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Докажите, что в любой компании из 
человек либо найдётся человек, знающий четырёх других, либо найдутся четверо, попарно не
знакомых. Знакомства обоюдны — если А знает Б, то и Б знает А.
Источники:
Подсказка 1!
1) Хм, какие-то попарные знакомства, это же граф! Давайте посмотрим на условие с таким взглядом. Нам нужно найти вершину степени хотя бы 4...
Подсказка 2!
2) Давайте попробуем идти от противного! То есть мы хотим попробовать из того, что степени всех вершин меньше трех, получить, что тогда есть независимое множество!
Подсказка 3!
3) Может рассмотрим первого человека и посмотрим, сколько тогда с ним незнакомых, поищем независимое множество там..
Будем говорить в терминах графа — либо найдётся вершина степени хотя бы 
, либо независимое множество размера 
. Пусть степень
каждой вершины не больше 
. Выберем человека 
, он не знаком хотя бы с 
другими, поэтому достаточно найти независимое
множество размера 
на них. Теперь выберем произвольную вершину 
из этих 
. Она соединена не более, чем с тремя из них,
потому достаточно показать, что среди оставшихся 
найдутся две, между которыми нет ребра, что очевидно, поскольку
любая из них имеет степень меньше 
, то есть в качестве 
берём любую из пяти, а в качестве 
ту, с которой 
не
знаком.
что и требовалось доказать
Ошибка.
Попробуйте повторить позже
Докажите, что среди пяти произвольных различных вершин правильного (все стороны и все углы которого равны) 
-и угольника всегда
найдутся три, являющихся вершинами равнобедренного треугольника.
Подсказка 1!
1) Нам нужно найти равнобедренный треугольник в правильном многоугольнике. А равнобедренный треугольник означает, что мы хотим найти два равных отрезка с общей вершиной. Вершин пять. А сколько у нас всего отрезков будет?
Подсказка 2!
2) Да, 10! Теперь осталось посмотреть, сколько среди них может быть отрезков разной длины! Смотрите, если бы отрезков одной длины было хотя бы 3, мы бы смогли что-то сказать? А если только по два отрезка равной длины для всех длин?
Подсказка 3!
3) Это уже сложнее. Всего в 15-угольнике у нас 7 вариантов для длины отрезка. Сколько в таком случае у нас разных длин, если каждой длины по два отрезка?
Подсказка 4!
4) Верно, 3! А теперь давайте посмотрим на эти отрезки немного иначе. Если у нас нет треугольника, то будет 4 вершины, которые составляют эти две пары равных отрезков, образуют четырехугольник с равными сторонами или диагоналями. Осталось рассмотреть возможность существования в нашей фигуре подобного четырехугольника.
Каждой паре выбранных точек соответствует длина отрезка, их соединяющего, которая может принимать 
различных значений (длины
диагоналей или стороны). Всего пар 
. Если равны длины каких-то трёх отрезков, то по принципу Дирихле у каких-то двух есть
общая точка, они и образуют равнобедренный треугольник.
Далее рассмотрим более сложный случай, то есть есть не более двух отрезков для каждой длины. Отсюда следует, что пар с равной
длиной будет хотя бы 
. Если в какой-то паре отрезки совпали по одной из вершин, то мы нашли нужный треугольник, потому считаем,
что в каждой паре отрезков все четыре вершины различны, то есть образуют четырёхугольник, в котором равны либо две стороны, либо
диагонали.
Заметим, что обе пары сторон равны быть не могут, поскольку тогда мы бы получили прямоугольник, а в 
-угольнике не может быть
диагонали-диаметра. Отсюда следует, что в четырёхугольнике не более двух пар равных отрезков, одной из которых будут диагонали.
Однако пары равных отрезков три, потому есть два различных четырёхугольника, которые пересекаются по трём точкам (всего точек
).
Заметим, что каждый четырёхугольник является равнобедренной трапецией, в которой диагональ является наибольшим отрезком. При выборе любых трёх точек диагональ будет одним (наибольшим) из отрезков полученного треугольника, потому диагонали трапеций равны. Но тогда они образуют три равных отрезка из первого пункта, поскольку обе диагонали различных четырёхугольников не могут совпадать.
