Республиканская олимпиада по математике, 2019 год, 9 класс

В правильном $n$-угольнике ($n\ge4$) каждая диагональ красится в один из двух цветов. Затем в каждой паре одноцветных пересекающихся диагоналей удаляют одну из этих диагоналей. Какое наибольшее число диагоналей могло остаться при таких операциях? (Диагонали, выходящие из одной вершины, пересекающимися не считаются.) ( Ильясов С. )

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

Покажем что ответ $2(n-3)$ или другими словами можно провести максимум $n-3$ диагонали одного цвета. Докажем это по индукции: база $n=4$ максимум одна непересекающаяся диагональ одного цвета, пусть для $n=1,....,k$ у нас выполняется условие, покажем это при $n=k+1$. Проведём одну диагональ она разделит наш многоугольник на два в которых мы уже знаем количество диагоналей. Значит в многоугольнике мы можем провести не больше $n-3$ одного цвета, соответсвенно не более $2(n-3)$ диагоналей обоих цветов. Пример:Проведём все диагонали первого цвета из одной вершины, все диагонали второго цвета из другой вершины, несложно заметить что диагонали одного цвета не пересекаются

Все диагонали второго цвета должны быть проведены из соседней вершины к первой.

(Первая вершина - это вершина из которой выходят все диагонали первого цвета.)

Решение можете посмотреть на данном сайте в разделе математика:

Республика 2019

Ответ:$2(n-3)$

Возьмем цвета красный и синий

Пусть мы нашли такую раскраску, что там максимум диагоналей. Тогда посмотрим только на синие диагонали(красные диагонали никак не влияют на расстановку синих). Понятно, что их максимум количество, и они не пересекаются между собой. Т.е. просто нужно найти наибольшее количество диагоналей в n-угольнике которые не пересекаются. А таких $n-3$ значит синих диагоналей максимум $n-3$ с красными аналогично, значит ответ $2(n-3)$

Пример показан выше

Лемма: В правильном $n-$угольнике может быть проведено максимум $n-3$ диагоналей так, что бы они не пересекались, отсюда ответ максимум $2n-6$.

Пример: С двух любых СОСЕДНИХ вершин сделайте диагональ на каждую другую вершину, диагонали из первой вершины в синий, из второй в красный.

Доказательство леммы: Докажем по индукции для выпуклого $n \geq 4$ угольника. Для $n=4$ очевидно, переход на $n+1$, если сделать диагональ, фигура разделится на какие-то $k$ угольника и $n-k+3$ угольника, и никакие вершины из этих двух многоугольников не должны быть соединены, а у каждого из них максимальным количеством диагоналей является $k-3$ и $n-k$, в сумме $n-3$, плюс одна диагональ которую мы сделали вначале перехода, в итоге $n-2$, доказано.