Областная олимпиада по математике, 2016 год, 9 класс

На окружности отмечены ${2n+1}$ различных точек, причем $n$ из них окрашены в синий цвет, $n$ точек — в красный, а одна — в черный. Докажите, что можно провести $n$ попарно непересекающихся отрезков с концами в этих точках так, чтобы ни одна точка не являлась концом более чем одного отрезка и чтобы никакой отрезок не соединял синюю и красную точки.

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

Предположим, что где-то на окружности найдется пара рядом расположенных синих точек и пара рядом расположенных красных точек. Соединив пару синих отрезком и пару красных отрезком, мы уменьшим $n$ на два, и дальше можно положиться на индукцию (придется также проверить базу для $n=0$ и $n=1$).

Пусть это не так и, без ограничения общности, после каждой красной точки стоит точка другого цвета. Если при этом где-то найдется пара рядом стоящих синих точек, то, соединив их одним отрезком, а две стоящие от них по обе стороны красные точки другим отрезком, мы опять уменьшим $n$ на два и задействуем индукцию.

Если же такой пары синих точек нет, то, соединив черную точку с соседней красной, и далее две соседние с ними по обе стороны синие точки, а затем две новые соседние красные, и, продолжая соединять точки попарно, мы получим в итоге $n$ искомых отрезков и одну лишнюю красную точку.

Допустим, n-четное число. Становится очевидно, что и синих, и красных точек четное количество и можно будет провести ровно по n/2 отрезков с концами СС (синий и синий) и КК (красный и красный). Суммируя количество отрезков мы получим минимум n (можно и больше)

Если же n-нечетное число, то очевидно, что можно провести минимум n-1/2 отрезков СС и КК, то есть в сумме n-1 отрезок. Важно то, что мы соединяем точки так, чтобы либо одна синяя, либо одна красная оставалась в одной полуплоскости с черной точкой, а мы можем это сделать из-за того, что кол-во точек нечетно, а для самих отрезков нужно четное кол-во точек. В конце концов, мы получим либо один отрезок ЧК, либо ЧС. Получается, мы сможем провести n отрезков