Упр.1032 ГДЗ Мерзляк Полонский 6 класс (Математика)

Задача

Рассмотрим одного из людей в этой компании. Пусть это будет мистер X, у него есть пять потенциальных знакомых: A,B,C,D и E.
С кем-то он может быть знаком, а с кем-то нет. Может быть знаком и со всеми пятью людьми в компании, а может и наоборот. Все возможные случаи запишем в таблицу.
Получается, что мы всегда можем найти в компании из шести человек трёх знакомых с мистером X или трёх незнакомых с ним людей (что получается и по принципу Дирихле). Рассмотрим каждый из этих случаев.
Знакомство будем рисовать красной линией, а незнакомство – синей.
1) Пусть мистер X знаком хотя бы с тремя людьми из компании. Это могут быть любые из пяти оставшихся человек, например.
Если окажется, что A и C знакомы, или A и E знакомы, или C и E знакомы.
в любом случае мы получим трёх попарно знакомых людей в компании.
Если же окажется, что ни одна из пар A и C, A и E, C и E не знакомы друг с другом:
сразу сможем найти трёх попарно незнакомых друг с другом людей в этой компании.
Таким образом, если случайно выбранный человек имеет хотя бы трёх знакомых в компании, то всегда можно найти трёх попарно знакомых или трёх попарно незнакомых людей в компании из шести человек.
2) Если же мистер X не имеет хотя бы трёх знакомых в этой компании, то мы сможем найти хотя бы трёх незнакомых ему людей.
Если окажется, что A и C незнакомы, или A и E незнакомы, или C и E незнакомы.
получим трёх попарно незнакомых людей в компании.
Если же окажется, что каждая из пар A и C, A и E, C и E знакомы друг с другом.
сразу сможем найти трёх попарно знакомых друг с другом людей в этой компании.
Таким образом, если случайно выбранный человек имеет хотя бы трёх незнакомых в компании, то всегда можно найти трёх попарно незнакомых или трёх попарно знакомых людей в компании из шести человек.
Таким образом, доказано, что в любой компании из шести человек всегда можно найти трёх попарно знакомых или трёх попарно незнакомых человек.
Данная задача является теоремой Рамсея, и была доказана ещё в 1930 году.

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

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

Действительно, если бы у X было только 0, 1 или 2 знакомых, то незнакомых было бы 5, 4 или 3 соответственно. Если же знакомых 3, 4 или 5, то уже есть нужное число знакомых.

Рассмотрим два случая.

1) У X есть хотя бы три знакомых. Возьмём любых троих из них, например A, C и E.

Если хотя бы одна из пар A и C, A и E, C и E знакома, то вместе с X получаем троих попарно знакомых людей.

Если же ни одна из этих пар не знакома, то A, C и E попарно незнакомы.

2) У X есть хотя бы три незнакомых. Возьмём любых троих из них, например A, C и E.

Если хотя бы одна из пар A и C, A и E, C и E незнакома, то получаем троих попарно незнакомых людей.

Если же все эти пары знакомы, то A, C и E попарно знакомы.

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