Олепиадная задача по графам: трое знакомых или трое незнакомых
Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
Разобрать решение
У данного человека среди остальных пяти есть либо не менее трёх знакомых, либо не менее трёх незнакомых ему. Разберём, например, первый случай. Среди этих трёх людей есть либо двое знакомых – тогда они вместе с выбранным нами исходно человеком образуют нужную тройку, либо они все трое попарно незнакомы.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.