Ограда около гора

[ptj]

В една гора разстоянието между всеки две дървета е не по-голямо от разликата в техните височини. Всички дървета имат височина до 100 метра. Да се докаже, че гората може да се обиколи с ограда с дължина 200 метра (дебелината на дърветата се пренебрегва).

[mkmarinov]

Да не си пропуснал, че височините са целочислени?

[inveidar]

Не. Условието си е напълно коректно!!!

[drago]

Нека дърветата са [tex]A_1,A_2,\cdots, A_n[/tex] и са подредени по нарастващ ред на техните височини [tex]a_1 < a_2 < \cdots < a_n[/tex]. Toгава:

(1) [tex]|A_1A_2|+|A_2A_3|+\cdots+|A_{n-1}A_n| \leq a_n-a_1 \leq 100[/tex]

Сега може да си предствим, че задачата е такава: Начупена линия с дължина по-малка или равна от 100 е хвърлена в равнината, да се докаже, че периметърът на изпъкналата и обвивка е по-малък или равен на 200.

Правим следното: Нека изпъкналата обвивка е [tex]A_{i_1}A_{i_2}\cdots A_{i_k}[/tex]

За всяко[tex]A_{i_j}A_{i_{j+1}}[/tex] означаваме с [tex]A_{i_j}B_{i,1}\cdots B_{i,s(i)}A_{i_{j+1}}[/tex] начупената линия, с която от [tex]A_{i_j}[/tex] може да се отиде до [tex]A_{i_{j+1}}[/tex] , без да напускаме начупената линия [tex]A_1A_2\cdots A_n[/tex] и за която заградената площ [tex]A_{i_j}B_{i,1}\cdots B_{i,s(i)}A_{i_{j+1}}A_{i_j}[/tex] е минимална.

Това означава, че:

(2) във вътрешността на [tex]A_{i_j}B_{i,1}\cdots B_{i,s(i)}A_{i_{j+1}}A_{i_j}[/tex] няма точка от начупената линия [tex]A_1A_2\cdots A_n[/tex].

Тогава:


(3) [tex]|A_{i_j}A_{i_{j+1}}| \leq |A_{i_j}B_{i,1}|+|B_{i,1}B_{i,2}|+ \cdots + |B_{i,s(i)}A_{i_{j+1}}|,\, i=1,2,\cdots,k,\, A_{i_{k+1}}=A_{i_1}[/tex]


забележете, че не може да има отсечка, която принадлежи на повече от 2 начупени линии [tex]A_{i_j}B_{i,1}\cdots B_{i,s(i)}A_{i_{j+1}}[/tex]. Това е така поради (2).

Използвайки това и като сумираме (3) за [tex]i=1,2,\cdots[/tex] ще получим

[tex]\sum_{j=1}^k |A_{i_j}A_{i_{j+1}}| \leq 2 \sum_{i=1}^{n-1} |A_iA_{i+1}| \leq 2.100 =200[/tex]

[inveidar]

Много сложно за такава хубава и достъпна до всеки задачка. Просто тръгваме от най-високото дърво и вървим към следващото по височина и така нататък, докато стигнем до най-ниското. Така получаваме една пътечка с дължина по-малка от 100. Остава да заградим пътечката с ограда. Ако някъде се пресича пътечката, това не е проблем - ще изрежем излишната мрежа!

[drago]

Да, това е така, на практика това е (1) в моя пост.
Интересно беше дали съществува изпъкнала ограда, която да загражда дърветата.
Е, има. Но по-лесно едва ли може да се направи!

[grav]

Интересно беше дали съществува изпъкнала ограда, която да загражда дърветата.

На ниво интуиция това е 'очевидно' от неравенстовто на триъгълника. Разбира се твоето решение прави това строго.

[inveidar]

На ниво интуиция това е 'очевидно' от неравенстовто на триъгълника. Разбира се твоето решение прави това строго.

Наистина от неравенството на триъгълника лесно се получава, че всяка начупена линия има изпъкнала обвивка с не по-голяма дължина.

[ptj]

Авторовото решение е по-простичко (казаното от "inveidar"):

Нека дървета с височина [tex]a_1< a_2 < ... < a_n[/tex] растат в точките [tex]A_1,A_2,...,A_n[/tex].
Тогава по условие [tex]A_1A_2\le |a_1-a_2|=a_1-a_2[/tex] , ... , [tex]A_{n-1}A_n=a_{n-1}-a_n[/tex].
Следователно дължината на начупената линия [tex]A_1,A_2,...,A_n[/tex] e не по-голяма от [tex](a_1-a_2)+(a_2-a_3)+...+(a_{n-1}-a_{n})=a_1-a_n<100[/tex], а оградата с която може да се обиколи тя съответно е не по-дълга от 200м.




П.П. Въпроса за изпъкналата външна ограда се решава посредством неравенство на триъгълника (от настоящата ограда), но нейната дължина ще е не по-голяма от 100 метра.

[inveidar]

А кой е авторът на задачата? Да видим дали няма някой преди него?!

[ptj]

Давана е за пръв път на Московката математическа олимпиада през 1972г. в I-ви кръг за 9-ти клас.

Докато сте топли да ви дам още една от "начупени линии" и конструкции:

При какви стойности на [tex]n[/tex] съществува затворена непрекъсната линия от [tex]n[/tex] отсечки, така че всяка права съдържаща една отсечка съдържа поне още една.

[inveidar]

Печелиш. Аз я открих в една руска книжка от 1974(дадена за печат 1973), но там е с дървета между 50 и 10 метра!

[drago]

...П.П. Въпроса за изпъкналата външна ограда се решава посредством неравенство на триъгълника (от настоящата ограда), но нейната дължина ще е не по-голяма от 100 метра.

Нещо се лъжеш Ptj, Изпъкналата обвивка е не-по голяма от 200 и тази оценка е абсолютно точна, т.е. ако се намали и на епсилон вече няма да е вярно !

...Наистина от неравенството на триъгълника лесно се получава, че всяка начупена линия има изпъкнала обвивка с не по-голяма дължина.

Драги ми inveidar, при всичката ми симпатия към теб за нещата, които правиш, пробвай да го напишеш това, така че да е достатъчно строго. Ако се получи по лесно и по-кратко от моето, ще черпя!

[ptj]

Да, грешката е моя. Изпъкналата ограда е с дължина не по-голяма от 200 метра.

[inveidar]

Наистина от неравенството на триъгълника лесно се получава, че всяка начупена линия има изпъкнала обвивка с не по-голяма дължина.

Добре де, няма да ме черпиш!!! Никак не е лесно да се докаже с неравенството на триъгълника! Объркал съм се.