Предмет: Математика, автор: as28102011

В комнате 6 человек. Докажите, что среди них есть либо трое попарно знакомых (т.е. каждый знаком с каждым), либо трое попарно незнакомых (каждый не знаком с каждым).​

Ответы

Автор ответа: yourbloodhismine
0

Відповідь:

Покрокове пояснення:

Для доказательства данного утверждения воспользуемся теорией графов.

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

Он может быть знаком либо с 0, либо с 1, либо с 2, либо с 3, либо с 4, либо с 5 остальными людьми в комнате (всего 6 возможных вариантов). Пусть без ограничения общности он знаком с 0, 1 и 2.

Тогда между 0, 1 и 2 должны существовать либо связи (попарные знакомства), либо отсутствие связей (попарные незнакомства). Рассмотрим возможные варианты:

Если между 0, 1 и 2 существует хотя бы одна связь (попарное знакомство), без ограничения общности рассмотрим связь между 0 и 1.

Если между 0 и 1 также существует связь (они знакомы), то трое попарно знакомых людей найдены (0, 1 и A), и утверждение доказано.

Если между 0 и 1 нет связи (они незнакомы), то трое попарно незнакомых людей найдены (0, 1 и A), и утверждение доказано.

Если между 0, 1 и 2 отсутствуют все связи (попарные незнакомства), тогда трое попарно незнакомых людей найдены (0, 1 и 2), и утверждение доказано.

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

Похожие вопросы
Предмет: Алгебра, автор: aleksandrakorsun933
Предмет: Українська мова, автор: Аноним
Предмет: Математика, автор: stasudalov98