Математикадан облыстық олимпиада, 2015-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 отрезков