Упр.77 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Задача

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 77. Задача Рамсея. Докажите, что в любой компании из 6 человек найдутся либо трое попарно незнакомых друг с другом, либо трое попарно знакомых.

Подробный ответ

Рассмотрим любого человека в компании из 6 человек. Соединим его с каждым из остальных пяти: если два человека знакомы, будем считать соответствующее ребро «красным», если не знакомы — «синим».

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

Пусть у него есть трое знакомых: $$A,\;B,\;C.$$

Если среди них есть хотя бы одна пара знакомых, например $$A$$ и $$B,$$ то вместе с выбранным человеком получаем троих попарно знакомых: $$\text{человек},\;A,\;B.$$

Если же никакие двое из $$A,\;B,\;C$$ не знакомы, то они попарно незнакомы, и мы получаем троих попарно незнакомых.

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

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