Боксёры на спартакиаде (задача по теории графов)

[Xenia1996]

На спартакиаду съехалось чётное число боксёров (но больше двух), каждый из которых сразился хотя бы с половиной из всех съехавшихся.
Всегда ли можно выбрать четверых боксёров и поставить их в круг так, что каждый будет стоять рядом с теми, с кем он сразился?
Изменится ли ответ на задачу, если в круг ставить не 4, а 5 боксёров (а общее число на этот раз тоже чётно, но больше 4)?

[MrDindows]

1) Выберем любых 2 из $2n$, которые не сражались между собой. По условию каждый из них сразился минимум с $n$ других боксёров, а так как без наших двух всего $2n-2$ боксёров, то есть хотя бы 2 других боксёра, с которыми они оба сражались. Эта четвёрка и будет искомой.

[Xenia1996]

MrDindows в сообщении #462519 писал(а):

1) Выберем любых 2, которые не сражались между собой.

А если таких нет?
Очевидно, конечно, но упомянуть следовало.

А что насчёт 5?

[MrDindows]

Думаю)

-- Вс июн 26, 2011 21:47:34 --

Насчёт 5, для любого натурального $n$ есть контрпример.
Разделим точки(боксёров) на две половины. И соеденим каждую точку одной половины со всеми точками другой. Очевидно, что в таком случаем мы не будем иметь ни одного цикла нечётной длины.