ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116409
Темы:    [ Четность и нечетность ]
[ Теория графов (прочее) ]
[ Процессы и операции ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

Автор: Фольклор

Среди участников олимпиады каждый знаком не менее чем с тремя другими. Докажите, что можно выбрать группу из чётного числа участников (больше двух человек) и посадить их за круглый стол так, чтобы каждый был знаком с обоими соседями.


Решение

Будем выстраивать участников в ряд так, чтобы знакомые стояли рядом. Когда-нибудь этот процесс закончится. Это значит, что все трое знакомых последнего в ряду (обозначим его А) уже выстроены. Обозначим через B и C тех из них, которые не стоят рядом с А. Если между А и B (А и C) стоит чётное число человек, то они вместе с А и B (А и C) образуют искомую группу. Если же оба эти числа чётны, то между B и C стоит нечётное число человек, и они вместе с А, B и C образуют искомую группу.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2009/2010
Номер 31
вариант
Вариант весенний тур, базовый вариант, 8-9 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .