сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

1.3 До­ка­жи­те, что a левая круг­лая скоб­ка 2, 4 пра­вая круг­лая скоб­ка мень­ше ко­рень из: на­ча­ло ар­гу­мен­та: 3 конец ар­гу­мен­та .


Сюжет 1

На n кар­точ­ках на­пи­са­ли по k чисел, сумма на каж­дой кар­точ­ке равна m. Ока­за­лось, что любой набор из k не­от­ри­ца­тель­ных чисел с сум­мой 1 можно по­лу­чить, умень­шив не­ко­то­рые числа на одной из кар­то­чек (на­бо­ры не­упо­ря­до­чен­ные). Пусть a(n, k)  — наи­мень­шее m, при ко­то­ром это воз­мож­но.

Спрятать решение

Ре­ше­ние.

Рас­смот­рим, на­при­мер, сле­ду­ю­щую пару на­бо­ров:

 левая круг­лая скоб­ка дробь: чис­ли­тель: 21, зна­ме­на­тель: 34 конец дроби , дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби , дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби , дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби пра­вая круг­лая скоб­ка

и
 левая круг­лая скоб­ка 1, дробь: чис­ли­тель: 13, зна­ме­на­тель: 34 конец дроби , дробь: чис­ли­тель: 13, зна­ме­на­тель: 68 конец дроби , дробь: чис­ли­тель: 13, зна­ме­на­тель: 102 конец дроби пра­вая круг­лая скоб­ка .

Сумма в каж­дом равна  дробь: чис­ли­тель: 347, зна­ме­на­тель: 204 конец дроби , это даже мень­ше, чем 1,71, а  ко­рень из: на­ча­ло ар­гу­мен­та: 3 конец ар­гу­мен­та =1,73 \ldots

Про­ве­рим, что эта пара на­бо­ров ма­жо­ри­ру­ет все нуж­ные четвёрки. Ясно (*), что в упо­ря­до­чен­ной трой­ке с сум­мой x сред­нее число  — не боль­ше, чем  дробь: чис­ли­тель: x, зна­ме­на­тель: 2 конец дроби , а малое  — не боль­ше, чем  дробь: чис­ли­тель: x, зна­ме­на­тель: 3 конец дроби ; ана­ло­гич­ное верно для четвёрок. Дей­стви­тель­но, если мак­си­маль­ное число в четвёрке боль­ше  дробь: чис­ли­тель: 21, зна­ме­на­тель: 34 конец дроби , то вто­рое по ве­ли­чи­не  — не боль­ше, чем  дробь: чис­ли­тель: 13, зна­ме­на­тель: 34 конец дроби , тре­тье не боль­ше  дробь: чис­ли­тель: 13, зна­ме­на­тель: 68 конец дроби а самое ма­лень­кое не боль­ше  дробь: чис­ли­тель: 13, зна­ме­на­тель: 102 конец дроби , зна­чит, такая чет­вер­ка ма­жо­ри­ру­ет­ся вто­рым на­бо­ром. Ана­ло­гич­но, если мак­си­маль­ное число не боль­ше, чем  дробь: чис­ли­тель: 21, зна­ме­на­тель: 34 конец дроби , то оно ма­жо­ри­ру­ет­ся пер­вым на­бо­ром.

Как прий­ти к этому ре­ше­нию?

Рас­смот­рим си­ту­а­цию, в ко­то­рой в пер­вой чет­вер­ке мак­си­маль­ное число равно 1, а во вто­рой a мень­ше 1. За­ме­тим, что для лю­бо­го \varepsilon боль­ше 0 мы долж­ны уметь на­кры­вать чет­вер­ку  левая круг­лая скоб­ка a плюс \varepsilon; 1 минус левая круг­лая скоб­ка a плюс \varepsilon пра­вая круг­лая скоб­ка ; 0; 0 пра­вая круг­лая скоб­ка и вто­рая наша чет­вер­ка сде­лать этого не смо­жет. Зна­чит, вто­рое слева число в пер­вой чет­вер­ке не мень­ше 1 минус a . Те­перь, рас­смот­рев для всех \varepsilon боль­ше 0 чет­вер­ки вида

 левая круг­лая скоб­ка a плюс \varepsilon; дробь: чис­ли­тель: 1 минус левая круг­лая скоб­ка a плюс \varepsilon пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби ; дробь: чис­ли­тель: 1 минус левая круг­лая скоб­ка a плюс \varepsilon пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби ; 0 пра­вая круг­лая скоб­ка ,

по­лу­чим, что тре­тье число в пер­вой чет­вер­ке не мень­ше, чем  дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 2 конец дроби , а рас­смот­рев для \varepsilon боль­ше 0 чет­вер­ки вида

 левая круг­лая скоб­ка a плюс \varepsilon; дробь: чис­ли­тель: 1 минус левая круг­лая скоб­ка a плюс \varepsilon пра­вая круг­лая скоб­ка , зна­ме­на­тель: 3 конец дроби ; дробь: чис­ли­тель: 1 минус левая круг­лая скоб­ка a плюс \varepsilon пра­вая круг­лая скоб­ка , зна­ме­на­тель: 3 конец дроби ; дробь: чис­ли­тель: 1 минус левая круг­лая скоб­ка a плюс \varepsilon пра­вая круг­лая скоб­ка , зна­ме­на­тель: 3 конец дроби пра­вая круг­лая скоб­ка ,

что чет­вер­тое число пер­вой чет­вер­ки  — это хотя бы  дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 3 конец дроби . Зна­чит, сумма в пер­вой чет­вер­ке хотя бы

 1 плюс левая круг­лая скоб­ка 1 минус a пра­вая круг­лая скоб­ка плюс дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 2 конец дроби плюс дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 3 конец дроби = дробь: чис­ли­тель: 17 минус 11 a, зна­ме­на­тель: 6 конец дроби .

Далее раз­бе­рем слу­чай, в ко­то­ром чет­вер­ки

 левая круг­лая скоб­ка дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби ; 0; 0 пра­вая круг­лая скоб­ка

и
 левая круг­лая скоб­ка дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби ; 0 пра­вая круг­лая скоб­ка

на­кры­ва­ют­ся вто­рой сум­мой. Тогда чет­вер­ка  левая круг­лая скоб­ка дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби пра­вая круг­лая скоб­ка также на­кры­ва­ет­ся вто­рой сум­мой (если мы, ко­неч­но, не хотим сумму в пер­вой чет­вер­ке, боль­шую 1,75). В такой си­ту­а­ции вто­рое число во вто­рой чет­вер­ке хотя бы  дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби , тре­тье  — хотя бы  дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби , чет­вер­тое  — хотя бы  дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби . Зна­чит, сумма во вто­рой чет­вер­ке хотя бы  дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби тре­тье  — хотя бы  дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби , чет­вер­тое  — хотя бы  дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби умно­жить на Зна­чит, сумма во вто­рой чет­вер­ке хотя бы

a плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби = дробь: чис­ли­тель: 12 a плюс 13, зна­ме­на­тель: 12 конец дроби .

Те­перь за­ме­тим, что все пары вида

 левая круг­лая скоб­ка 1; 1 минус a; дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 2 конец дроби ; дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 3 конец дроби пра­вая круг­лая скоб­ка

и
 левая круг­лая скоб­ка a; дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби ; дробь: чис­ли­тель: 1, зна­ме­на­тель: 4 конец дроби пра­вая круг­лая скоб­ка ,

под­хо­дят. Дей­стви­тель­но (*), если наи­боль­шее число по­па­да­ет в по­лу­ин­тер­вал  левая круг­лая скоб­ка a; 1 пра­вая квад­рат­ная скоб­ка , то тогда сле­ду­ю­щее по раз­ме­ру не боль­ше, чем 1 минус a, тре­тье  — не боль­ше, чем  дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 2 конец дроби , а чет­вер­тое  — не боль­ше, чем  дробь: чис­ли­тель: 1 минус a, зна­ме­на­тель: 3 конец дроби . Ана­ло­гич­но раз­би­ра­ет­ся слу­чай, когда наи­боль­шее число в чет­вер­ке по­па­да­ет в ин­тер­вал  левая квад­рат­ная скоб­ка дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби ; a пра­вая квад­рат­ная скоб­ка . Зна­чит, любой под­хо­дя­щий ва­ри­ант может быть све­ден к парам та­ко­го вида без уве­ли­че­ния суммы. Если

 дробь: чис­ли­тель: 17 минус 11 a, зна­ме­на­тель: 6 конец дроби не равно q дробь: чис­ли­тель: 12 a плюс 13, зна­ме­на­тель: 12 конец дроби ,

то, оче­вид­но, можно из­ме­нить a так, чтобы эти вы­ра­же­ния стали равны и ближе друг к другу, мак­си­маль­ное из них, со­от­вет­ствен­но, умень­шит­ся. Если же

 дробь: чис­ли­тель: 17 минус 11 a, зна­ме­на­тель: 6 конец дроби = дробь: чис­ли­тель: 12 a плюс 13, зна­ме­на­тель: 12 конец дроби ,

то 34 минус 22 a=12 a плюс 13, а зна­чит a= дробь: чис­ли­тель: 21, зна­ме­на­тель: 34 конец дроби . Сумма в чет­вер­ках в этом слу­чае равна

 дробь: чис­ли­тель: 21, зна­ме­на­тель: 34 конец дроби плюс дробь: чис­ли­тель: 13, зна­ме­на­тель: 12 конец дроби = дробь: чис­ли­тель: 347, зна­ме­на­тель: 204 конец дроби мень­ше ко­рень из: на­ча­ло ар­гу­мен­та: 3 конец ар­гу­мен­та .

1