Задача за наградата на СМБ

[mousehack]

Върху окръжност са избрани [tex] n[/tex] точки,като никои три хорди с краища тези точки не се пресичат в една точка.Да се докаже,че съществува [tex] n[/tex], за което могат да се прекарат [tex]\frac{n^2-3n+4 }{2 } [/tex] хорди с краища дадените точки,които разделят вътрешността на окръжността на [tex] 1998 [/tex] части.

[Реклама]

[mousehack]

не ви ли харесва задачата?

[krainik]

Доста известна е и решението- също. Все пак е добро упражнение за човек, които не я е виждал

[mousehack]

Гледам доста време мина пък никои не е написал решение.Та за това ето го моето:
Първо да докажем следната Лема:Броят на частите,на които се диле вътрешността на окръжност при прекарването на всички [tex]\left(\begin{array}{rr}n\\2\\\end{array}\right)[/tex] хорди с краища дадените [tex]n[/tex] точки,при условие,че никои три хорди не се пресичат в една точка,е [tex]\left(\begin{array}{rr}n\\4\\\end{array}\right)+\left(\begin{array}{rr}n\\2\\\end{array}\right)+1.[/tex]Доказателството ще проведем по индукция.За [tex]n=2[/tex] се проверява директно,че горната формула е вярна.Да допуснем,че тя е вярна за някое [tex]n[/tex] и да я докажем за [tex]n+1.[/tex]За целта да преброим колко нови части се появяват при добавяне на една точка.Лесно се съобразява,че ако една хорда се пресича с [tex]t[/tex] други хорди,то тя "добавя" [tex]t+1[/tex] нови части.Тогава общият брой на новите части ("добавени" от [tex]n+1[/tex]-та точка) е [tex]\sum_{k=0}^{n-1 }(k(n-k-1)+1). [/tex]Използвайки,че [tex]1+2+3...+n-1=\frac{(n-1)n}{2 } [/tex] и [tex] 1^2+2^2+3^2+...+(n-1)^2=\frac{(n-1)n(2n-1)}{6 } [/tex],лесно се проверява,че горната сума е равна точно на [tex]\left(\begin{array}{rr}n+1\\4\\\end{array}\right)+ \left(\begin{array}{rr}n+1\\2\\\end{array}\right)+1-(\left(\begin{array}{rr}n\\4\\\end{array}\right)+\left(\begin{array}{rr}n\\2\\\end{array}\right)+1)[/tex],което доказва Лемата.
Да допуснем,че [tex]n\le 16.[/tex]Тогава дори да прекараве всички хорди,частите,на които се дели вътрешността на окръжността,са по-малко от [tex]\left(\begin{array}{rr}16\\4\\\end{array}\right)+\left(\begin{array}{rr}16\\2\\\end{array}\right)+1=1941<1998.[/tex]Следователно [tex]n>16.[/tex]Да допуснем,че [tex]n\ge 18.[/tex]Понеже броят на всички хорди е [tex]\left(\begin{array}{rr}n\\2\\\end{array}\right)[/tex],то броят на "изтритите" хорди е [tex]\left(\begin{array}{rr}n\\2\\\end{array}\right)-\frac{n^2-3n+4}{2 }=n-2.[/tex]Всяка от "изтритите" хорди намалява броя на частите най-много [tex] (\frac{n-2}{2 })^2+1. [/tex]Тогава,броят на частите е поне [tex]\left(\begin{array}{rr}n\\4\\\end{array}\right)+\left(\begin{array}{rr}n\\2\\\end{array}\right)+1-(n-2)( (\frac{n-2}{2 })^2+1).[/tex]Ще покажем,че тази разлика е по-голяма от 2000 при [tex]n\ge 18=[/tex]Наистина,тъй като [tex]\left(\begin{array}{rr}n\\2\\\end{array}\right)+1>n-2[/tex] за всяко [tex]n[/tex],достатъчно е да докажем,че [tex]\left(\begin{array}{rr}n\\4\\\end{array}\right)-(n-2)(\frac{n-2}{2 })^2 >2000.[/tex]Като използваме,че [tex]\frac{n-2}{4 }\ge 4 [/tex] (понеже [tex]n\ge 18[/tex],получаваме,че е достатъчно да покажем,че [tex] \frac{n(n-1)(n-3)}{6 } -(n-2)^2>500.[/tex]Последното е еквивалентно с [tex]n^2(n-9)+15n-24>3000.[/tex]Следователно [tex]n<18.[/tex]Ще установим,че при [tex]n=17 [/tex] с [tex]\frac{n^2-3n+4}{2 }=21 [/tex] хорди е възможно вътрешността на окръжността да се раздели на 1998 части.Да прекараме всички хорди с краища в 16 точки (120 на брой).Съгласно доказаното по-горе,нътрешността на окръжността се дели на [tex]\left(\begin{array}{rr}16\\4\\\end{array}\right)+\left(\begin{array}{rr}16\\2\\\end{array}\right)+1=1941[/tex] части.Да прекараме хорда,свързваща 17-та точка с една от останалите,така,че от двете страни на хордата да останат съответно 8 и 7 от останалите 15 точки.Тогава тази хорда ще пресича 8.7=56 от останалите и следователно ще "добавим" оше 57 части.Общият брой е 1941+57.1998