Олимпиада имени Леонарда Эйлера2009-2010 учебный год, III тур дистанционного этапа

На доске нарисовали 8 непересекающихся кругов и от каждого провели по стрелке к тем из остальных семи, которые не больше него. Всего получилось 33 стрелки. Докажите, что среди нарисованных на доске кругов есть три равных.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Занумеруем круги в порядке возрастания радиусов (порядок между кругами равных радиусов устанавливаем произвольно). Тогда из каждого круга заведомо проведены стрелки ко всем кругам с меньшими номерами: из восьмого — 7 стрелок, из седьмого — 6 и т.д.. Всего таких стрелок $7+6+5+4+3+2+1 = 28$. Покрасим их в красный цвет, а оставшиеся 5 стрелок — в синий.
Заметим, что радиусы двух кругов равны тогда и только тогда, когда эти круги связаны двумя противоположно направленными стрелками. Поскольку любые два круга связаны ровно одной красной стрелкой, это означает, что равны в точности те круги, которые связаны синей стрелкой. Допустим, среди кругов нет трёх равных. Тогда каждый круг связан синей стрелкой (входящей или исходящей) не более чем с одним другим кругом. Но тогда синих стрелок не более, чем $8:2 = 4$. Противоречие.