Олимпиадная задача по теории графов для 8–9 класса: участники за круглым столом
Среди участников олимпиады каждый знаком не менее чем с тремя другими. Докажите, что можно выбрать группу из чётного числа участников (больше двух человек) и посадить их за круглый стол так, чтобы каждый был знаком с обоими соседями.
Разобрать решение
Будем выстраивать участников в ряд так, чтобы знакомые стояли рядом. Когда-нибудь этот процесс закончится. Это значит, что все трое знакомых последнего в ряду (обозначим его А) уже выстроены. Обозначим через B и C тех из них, которые не стоят рядом с А. Если между А и B (А и C) стоит чётное число человек, то они вместе с А и B (А и C) образуют искомую группу. Если же оба эти числа чётны, то между B и C стоит нечётное число человек, и они вместе с А, B и C образуют искомую группу.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.