Страница 56 номер 77, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Задача Рамсея. Докажите, что в любой компании из 6 человек найдутся либо трое попарно незнакомых друг с другом, либо трое попарно знакомых.
Шестеро человек — вершины, ребро соединяет знакомых.
Возьмём любого из шестерых и обозначим его \(A\); остальных пятеро. Будь знакомых с \(A\) не больше двух и незнакомых не больше двух, всего их было бы не больше \(2 + 2 = 4\), а их пятеро. Значит, среди пятерых найдутся либо трое знакомых с \(A\), либо трое незнакомых с \(A\).
Первый случай: \(B\), \(C\), \(D\) знакомы с \(A\). Если какие-нибудь двое из них знакомы между собой, они вместе с \(A\) дают трёх попарно знакомых; если никакие двое не знакомы, то \(B\), \(C\), \(D\) — трое попарно незнакомых.
Второй случай: \(B\), \(C\), \(D\) не знакомы с \(A\). Если какие-нибудь двое из них не знакомы между собой, они вместе с \(A\) дают трёх попарно незнакомых; если все трое попарно знакомы, то \(B\), \(C\), \(D\) — трое попарно знакомых.
В каждом случае нужная тройка нашлась.
Ответ: утверждение доказано: у любого человека из шестерых среди пяти остальных найдутся либо трое знакомых с ним, либо трое незнакомых с ним, и внутри такой тройки либо есть пара, дополняющая его до нужной тройки, либо сама тройка оказывается попарно знакомой (попарно незнакомой).
Задача Рамсея. Докажите, что в любой компании из 6 человек найдутся либо трое попарно незнакомых друг с другом, либо трое попарно знакомых.
Сопоставим каждому из шести человек вершину графа и соединим ребром тех двоих, которые знакомы. Требуется доказать, что найдутся либо три вершины, попарно соединённые рёбрами (трое попарно знакомых), либо три вершины, попарно не соединённые (трое попарно незнакомых).
Возьмём любого из шестерых и обозначим его \(A\). Остальных пятеро, и каждый из них либо знаком с \(A\), либо не знаком. Если бы знакомых с \(A\) было не больше двух и незнакомых тоже не больше двух, всего их было бы не больше \(2 + 2 = 4\), а их пятеро. Значит, среди пятерых найдутся либо трое знакомых с \(A\), либо трое незнакомых с \(A\). Разберём оба случая.
Первый случай: трое — назовём их \(B\), \(C\), \(D\) — знакомы с \(A\). Если какие-нибудь двое из них знакомы между собой, то эти двое вместе с \(A\) и дают трёх попарно знакомых. Если же никакие двое из \(B\), \(C\), \(D\) не знакомы друг с другом, то \(B\), \(C\), \(D\) — трое попарно незнакомых.
Второй случай: трое — \(B\), \(C\), \(D\) — не знакомы с \(A\). Если какие-нибудь двое из них не знакомы между собой, то эти двое вместе с \(A\) дают трёх попарно незнакомых. Если же все трое попарно знакомы, то \(B\), \(C\), \(D\) — трое попарно знакомых.
В каждом из двух случаев нужная тройка нашлась, значит, утверждение верно для любой компании из 6 человек.
Ответ: утверждение доказано: у любого человека из шестерых среди пяти остальных найдутся либо трое знакомых с ним, либо трое незнакомых с ним, и внутри такой тройки либо есть пара, дополняющая его до нужной тройки, либо сама тройка оказывается попарно знакомой (попарно незнакомой).
