Затворени интервали

[aifC]

Нека [tex]\Delta_{1}, \Delta_{2}......\Delta_{k}[/tex] са затворени интервали садържащи се в затворения интервал [tex][0,1][/tex], които покриват целия интервал [tex][0,1][/tex]. Предполага се, че тази система от интервали е минимално покритие, т.е. , че никоя нейна подсистема не покрива целия интервал [tex][0,1][/tex]. Докажете че сумата на дължините на интервалите [tex]\Delta_{j}[/tex] е по-малка от [tex]2[/tex].

[Genie_Almo]

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

Ако [tex]k=1[/tex], тогава [tex]\triangle_{1 }[/tex] съвпада с [0,1] и съответно дължината му е 1. Ако [tex]k=2[/tex], тогава всеки от интервалите [tex]\triangle_{1 }[/tex] и [tex]\triangle_{2 }[/tex] има дължина най-много 1, но не могат да бъдат едновременно 1, с оглед да се спази условието за минималност на покритието. Следователно общата дължина на двата интервала също е по-малка от 2.

Да разгледаме случая [tex]k\ge 3[/tex]. Въвеждаме нотацията {[tex]\triangle_{i } (m_{i },l_{i}), i=1,2,..k[/tex]}, която описва интервала [tex]\triangle_{i }[/tex] с начало [tex]m_{i }[/tex] и край [tex]l_{i}[/tex]. Нека приемем [tex]m_{i }[/tex] и [tex]l_{i}[/tex] като числа от интервала [0,1], съответни на отдалечеността спрямо нулата. Без ограничение можем да сортираме индексите на интервалите във възходящ ред според тяхното начало спрямо нулата, т.е. без ограничение приемаме че:

[tex]m_{1 }\le m_{2}\le m_{3}\le ...\le m_{k}[/tex]

Нека разгледаме произволни два поредни интервала и [tex]\triangle_{i }[/tex] и [tex]\triangle_{i+1 }[/tex] . Те не могат да имат общо начало, защото това ще означава, че или двата интервала съвпадат или единият се съдържа в другия. И при двата случая се нарушава условието за минималност. По-същите съображения и краищата на интервалите не могат съвпадат. Също така не е възможно [tex]l_{i+1 }\le l_{i}[/tex], защото това води до [tex]\triangle_{i+1 }\in \triangle_{i }[/tex]. Прилагайки горното върху всяка двойка от типа [tex]\triangle_{i }[/tex],[tex]\triangle_{i+1 }[/tex] установяваме, че:

(1) \begin{array}{|l} m_{1}< m_{2}<...<m_{k} \\ l_{1}< l_{2}<...<l_{k}\end{array}

Да съобразим, че за да няма непокрити участъци в интервала [0,1] са задължителни условията [tex]m_{1}=0, l_{k}=1[/tex] . Да направим още едно важно наблюдение над двата поредни интервала. Ако допуснем, че [tex]l_{i }<m_{i+1}[/tex], тогава интервалът [tex](l_{i },m_{i+1})[/tex], определен от тези две числа ще остане непокрит - съгласно (1) не може да има друг от останалите k-2 интервала, който да покрие тази празнина. Това означава, че за всеки два поредни интервала [tex]\triangle_{i } (m_{i },l_{i})[/tex] и [tex]\triangle_{i+1 } (m_{i+1 },l_{i+1})[/tex] е в сила неравенството [tex]m_{i }<m_{i+1}\le l_{i }<l_{i+1}[/tex] (2).

Нека разгледаме сега интервалът [tex]\triangle_{i +2} (m_{i+2 },l_{i+2})[/tex] как би се позиционирал спрямо другите два. Имайки предвид (1) и (2) заключаваме, че числото [tex]l_{i+2}[/tex] е най-голямото от общо шестте разглеждани, т.е. е в сила [tex]m_{i }<m_{i+1}\le l_{i }<l_{i+1}<l_{i+2}[/tex]. Както вече забелязахме по аналогия, ако [tex]l_{i+1 }<m_{i+2}[/tex], то интервалът [tex](l_{i+1 },m_{i+2})[/tex] остава непокрит и няма как да бъде покрит от останалите k-3 интервала. Ако [tex]m_{i+1}<m_{i+2}\le l_{i}[/tex] тогава ще е налице конструкцията [tex]m_{i }<m_{i+1}<m_{i+2}\le l_{i }<l_{i+1}<l_{i+2}[/tex], при която се вижда как интервалът [tex]\triangle_{i+1 }[/tex] е изцяло покрит от интервалите [tex]\triangle_{i }[/tex] и [tex]\triangle_{i+2}[/tex], което нарушава условието за минималност. Следователно единствената възможна конструкция остава [tex]m_{i }<m_{i+1}\le l_{i }<m_{i+2}\le l_{i+1}<l_{i+2}[/tex]. Тъй като предното е в сила за всеки три поредни интервала, това означава, че е в сила следното верижно неравенство:

[tex]m_{1 }<m_{2}\le l_{1 }<m_{3}\le l_{2}<m_{4} \le l_{3}<m_{5}\le ... \le l_{k-3}<m_{k-1}\le l_{k-2}<m_{k}\le l_{k-1}<l_{k}[/tex] (3)

Ако се вгледаме по-детайлно в тази конструкция виждаме, че тя действително се валидира от факта, че за всеки от интервалите делта съществува точно определен участък, който се покрива само от този интервал - и това гарантира условието за минималност на покритието. За [tex]\triangle_{1 }[/tex] това е интервалът [tex][m_{1 },m_{2})[/tex]. По-нататък за всяко [tex]\triangle_{i} , i = 2,3,...,k-1[/tex] - това е интервалът [tex](l_{i-1 },m_{i+1})[/tex]; и накрая за [tex]\triangle_{k }[/tex] - това е [tex](l_{k-1 },l_{k}][/tex].

Сега, ако фиксираме [tex]m_{1 },m_{2},...,m_{k}[/tex] се вижда как дължината на всеки интервал [tex]\triangle_{i} , i = 2,3,...,k-2[/tex] би се увеличил точно с толкова, с колкото придвижим неговия край [tex]l_{i }[/tex] към числото [tex]m_{i+2 }[/tex], при това без да се променя дължината на останалите делти. Само че стойността на [tex]l_{i }[/tex] никога няма да достигне до [tex]m_{i+2 }[/tex].

Следователно за сумата от дължините на интервалите [tex]\triangle_{1},\triangle_{2},...,\triangle_{k}[/tex] можем да запишем следното неравенство:

[tex][\triangle_{1}]+[\triangle_{2}]+...+[\triangle_{k}] = (l_{1}-m_{1}) + (l_{2}-m_{2}) + (l_{3}-m_{3}) +...+ (l_{k-2}-m_{k-2}) + (l_{k-1}-m_{k-1})+ (l_{k}-m_{k}) < (m_{3}-m_{1}) + (m_{4}-m_{2}) + (m_{5}-m_{3}) +...+ (m_{k}-m_{k-2}) + (l_{k-1}-m_{k-1})+ (l_{k}-m_{k}) = -m_{1} + l_{k-1} + l_{k} = 1+l_{k-1}<2[/tex]

За заключителната част на неравенството е използван фактът, че [tex]m_{1}=0, l_{k}=1[/tex] .

[Genie_Almo]

Сега, ако фиксираме [tex]m_{1},m_{2},...,m_{k}[/tex] се вижда как дължината на всеки интервал [tex]\triangle_{i} ,i=2,3,...,k−2[/tex] би се увеличил точно с толкова, с колкото придвижим неговия край [tex]l_{i}[/tex] към числото [tex]m_{i+2}[/tex], при това без да се променя дължината на останалите делти.

Тук си открих малка грешка. Следва да се разбира:

...дължината на всеки интервал [tex]\triangle_{i} ,i=1,2,3,...,k−2[/tex] би се увеличил точно с толкова....

[Genie_Almo]

И още една грешка:

Заключителната част на неравенството ще е:

[tex]-m_{1}-m_{2}+l_{k-1}+l_{k} = 1+l_{k-1}-m_{2}<2[/tex] , което не променя крайния резултат, но поставя под съмнение продуктивността и техническата грамотност на автора на решението, особено в малките часове на денонощието. За което се извинявам!