58. National mathematical olympiad Final round

Първо ще докажем, че за даден връх на изпъкналия 2009-ъгълник и всяка триангулация, с прилагане на разрешената операция можем да получим триангулацията, получена от прекарването на всички диагонали през този връх. За произволен връх $A$, движейки се обратно на часовниковата стрелка, да означим с $B_1,B_2,\dots ,B_k$ последователните върхове, за които $A{B}_i$ е страна на дадения многоъгълник или диагонал в дадената триангулация. Ако отсечката $B_i{B}_{i+1}$ не е страна, тя е диагонал и след извършване на разрешената операция, ще получим нова триангулация от която излизащите от $A$ диагонали са с един повече. Продължавайки по този начин ще получим триангулация с диагонали само от върха $A$.

Ще докажем по индукция по $n\ge 4$, че твърдението е вярно за произволен изпъкнал $n$-ъгълник. При $n=4,5$ твърдението се проверява директно. Да допуснем, че твърдението е вярно за някое $k\ge 5$ и да разгледаме триангулация на изпъкнал $(k+1)$-ъгълник. Без ограничение приемаме, че избрания диагонал е $A_1{A}_i$. Съгласно доказаното, от дадената триангулация можем да получим триангулацията, получена с прекарването на всички диагонали през $A_1$. Ако при това $A_1{A}_i$ е станал зелен, задачата е решена. Нека зелен е станал диагонала $A_1{A}_j$, като без ограничение считаме, че $j<i$. От индукционото допускане следва, че в многоъгълника $A_1{A}_2...A_i$ можем да получим триангулация, в която диагоналът $A_1{A}_{i-1}$ е зелен. Тъй като $k\ge 5$ и всяка триангулация на $(k+1)$-ъгълник съдържа $k-2$ диагонала, то в триангулацията освен диагоналите $A_1{A}_{i-1}$ и $A_1{A}_i$ има поне още един диагонал. Този диагонал разделя $(k+1)$-ъгълника на два изпъкнали многоъгълника, всеки с по-малко от $k+1$ върха, като диагоналите $A_1{A}_{i-1}$ и $A_1{A}_i$ са в един от двата многоъгълника. Остава да приложим индукционното допускане за този многоъгълник.