ГДЗ по алгебре 9 класс Шыныбеков раздел 5 - 5.107

Представим 9 человек в виде вершин графа. Если два человека знакомы между собой, соединим их ребром; если не знакомы — ребро между ними проводить не будем. Требуется доказать, что в графе найдутся либо 3 попарно соединённые вершины (3 знакомых друг с другом), либо 4 попарно не соединённые вершины (4 человека, не знакомых друг с другом). **Вспомогательное утверждение:** среди любых 6 человек найдутся либо 3 попарно знакомых, либо 3 попарно незнакомых. *Доказательство:* выберем одного человека $A$. Из оставшихся 5 человек по принципу Дирихле найдётся либо не менее 3 знакомых с $A$, либо не менее 3 незнакомых с ним. 1. Если с $A$ знакомы хотя бы 3 человека, то: - если любые двое из них знакомы между собой, они вместе с $A$ образуют тройку попарно знакомых; - если никто из них друг с другом не знаком, то они сами образуют тройку попарно незнакомых. 2. Если с $A$ не знакомы хотя бы 3 человека, аналогично: - если любые двое из них не знакомы между собой, они вместе с $A$ образуют тройку попарно незнакомых; - если все они знакомы между собой, то они образуют тройку попарно знакомых. Утверждение доказано. --- **Основное доказательство:** Предположим противное: среди данных 9 людей нет ни 3 попарно знакомых, ни 4 попарно незнакомых. Обозначим через $d(v)$ степень вершины $v$ (количество знакомых человека $v$). Поскольку всего людей 9, для любого человека количество незнакомых с ним людей равно $8 - d(v)$. 1. Предположим, что у некоторого человека $A$ степень $d(A) \ge 4$ (то есть у него не менее 4 знакомых). - Если среди этих знакомых найдутся хотя бы двое, которые знакомы друг с другом, то они вместе с $A$ образуют группу из 3 попарно знакомых. - Если среди этих знакомых никто друг с другом не знаком, то любые 4 из них являются 4 попарно незнакомыми людьми. В обоих случаях условие задачи выполняется, что противоречит предположению. Следовательно, ни у одного человека не может быть 4 или более знакомых: для всех вершин выполняется условие $d(v) \le 3$. 2. Предположим, что у некоторого человека $A$ степень $d(A) \le 2$ (то есть у него не более 2 знакомых). Тогда число незнакомых с ним людей равно: $$8 - d(A) \ge 8 - 2 = 6$$ Рассмотрим этих 6 (или более) человек, не знакомых с $A$. По вспомогательному утверждению, среди них найдутся: - либо 3 попарно знакомых (условие задачи выполнено); - либо 3 попарно незнакомых, но тогда эти 3 человека вместе с $A$ (который не знаком ни с кем из них) образуют 4 попарно незнакомых людей. В обоих случаях получаем противоречие. Следовательно, ни у одного человека не может быть 2 или менее знакомых: для всех вершин выполняется условие $d(v) \ge 3$. 3. Из пунктов 1 и 2 следует, что для каждого из 9 человек одновременно должно выполняться: $$d(v) \le 3 \quad \text{и} \quad d(v) \ge 3 \implies d(v) = 3$$ То есть каждый человек должен иметь ровно 3 знакомых. Посчитаем сумму степеней всех 9 вершин: $$\sum d(v) = 9 \cdot 3 = 27$$ По лемме о рукопожатиях сумма степеней всех вершин любого графа равна удвоенному количеству рёбер, то есть всегда является чётным числом. Однако 27 — число нечётное. Следовательно, такой граф существовать не может. Полученное противоречие означает, что исходное предположение неверно. Таким образом, среди любых 9 людей обязательно найдутся 3 человека, знакомых друг с другом, или 4 человека, не знакомых друг с другом. Утверждение доказано.