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


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

Сюжет 1

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

1.4 Огра­ни­че­на ли по­сле­до­ва­тель­ность a левая круг­лая скоб­ка 2, k пра­вая круг­лая скоб­ка минус a левая круг­лая скоб­ка 1, k пра­вая круг­лая скоб­ка ?

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

Ре­ше­ние.

Вы­чис­лим a левая круг­лая скоб­ка 1, k пра­вая круг­лая скоб­ка . Как уже от­ме­ча­лось, для вся­ко­го l мень­ше или равно k долж­на быть кар­точ­ка, в ко­то­рой l-ое по ве­ли­чи­не число не мень­ше, чем  дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби . Если кар­точ­ка всего одна, то сумма на этой кар­точ­ке, таким об­ра­зом, не мень­ше

1 плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби плюс \ldots плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: k конец дроби .

С дру­гой сто­ро­ны, кар­точ­ка

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

оче­вид­но, под­хо­дит, т. к. в на­бо­ре с еди­нич­ной сум­мой l-ое по ве­ли­чи­не число не боль­ше  дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби , так что

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

Те­перь рас­смот­рим про­из­воль­ную пару на­ту­раль­ных чисел l мень­ше k, со­от­но­ше­ние

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

Те­перь рас­смот­рим про­из­воль­ную пару на­ту­раль­ных чисел l мень­ше k, со­от­но­ше­ние между ко­то­ры­ми мы уточ­ним позд­нее, и предъ­явим два на­бо­ра, вдвоём ма­жо­ри­ру­ю­щих все на­бо­ры с еди­нич­ной сум­мой: а имен­но

 левая круг­лая скоб­ка \underbrace дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби , дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби , \ldots, дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби _l \text раз , дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 1 конец дроби , дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 2 конец дроби , дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 3 конец дроби , \ldots, дробь: чис­ли­тель: 1, зна­ме­на­тель: k конец дроби пра­вая круг­лая скоб­ка

и

 левая круг­лая скоб­ка 1, дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби , дробь: чис­ли­тель: 1, зна­ме­на­тель: 3 конец дроби , \ldots, дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби , дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l в квад­ра­те конец дроби , дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l левая круг­лая скоб­ка l плюс 1 пра­вая круг­лая скоб­ка конец дроби , дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l левая круг­лая скоб­ка l плюс 2 пра­вая круг­лая скоб­ка конец дроби , \ldots, дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l левая круг­лая скоб­ка k минус 1 пра­вая круг­лая скоб­ка конец дроби пра­вая круг­лая скоб­ка .

Дей­стви­тель­но, рас­смот­рим любой упо­ря­до­чен­ный по убы­ва­нию набор  левая круг­лая скоб­ка a_1 боль­ше или равно a_2 боль­ше или равно \ldots боль­ше или равно a_k пра­вая круг­лая скоб­ка с еди­нич­ной сум­мой. Ясно, что a_i мень­ше или равно дробь: чис­ли­тель: 1, зна­ме­на­тель: i конец дроби при любом i и по­это­му пер­вая кар­точ­ка ма­жо­ри­ру­ет любой набор с еди­нич­ной сум­мой, в ко­то­ром все числа не пре­вос­хо­дят  дробь: чис­ли­тель: 1 , зна­ме­на­тель: l конец дроби .

Пусть, на­про­тив, a_1 боль­ше дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби . Тогда для лю­бо­го i имеем

 a_2 плюс a_3 плюс \ldots плюс a_l плюс i мень­ше 1 минус дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби \Rightarrow a_l плюс i мень­ше или равно дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l левая круг­лая скоб­ка l плюс i минус 1 пра­вая круг­лая скоб­ка конец дроби .

По­это­му любой набор с a_1 боль­ше дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби ма­жо­ри­ру­ет­ся вто­рой из наших кар­то­чек.

Оста­лось убе­дить­ся, что раз­ность между a левая круг­лая скоб­ка 1, k пра­вая круг­лая скоб­ка и мак­си­му­мом из сумм в этих двух на­бо­рах может быть сде­ла­на (при под­хо­дя­щем вы­бо­ре l и k) сколь угод­но боль­шой. Дей­стви­тель­но, сумма на пер­вой кар­точ­ке от­ли­ча­ет­ся от a левая круг­лая скоб­ка 1, k пра­вая круг­лая скоб­ка на

 1 плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби плюс \ldots плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: l минус 1 конец дроби минус дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l конец дроби боль­ше дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби плюс \ldots плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: l минус 1 конец дроби

и эта ве­ли­чи­на при до­ста­точ­но боль­ших l может быть сде­ла­на, как из­вест­но, сколь угод­но боль­шой. Те­перь за­фик­си­ру­ем про­из­воль­ное l и по­смот­рим на вто­рую кар­точ­ку: сумма чисел на ней мень­ше, чем

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

на

 дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 1 конец дроби плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 2 конец дроби плюс умно­жить на s плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: k конец дроби минус дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l конец дроби левая круг­лая скоб­ка дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 1 конец дроби плюс \ldots плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: k минус 1 конец дроби пра­вая круг­лая скоб­ка = дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби левая круг­лая скоб­ка дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 1 конец дроби плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 2 конец дроби плюс умно­жить на s плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: k минус 1 конец дроби пра­вая круг­лая скоб­ка плюс
 плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: k конец дроби минус дробь: чис­ли­тель: l минус 1, зна­ме­на­тель: l в квад­ра­те конец дроби боль­ше дробь: чис­ли­тель: 1, зна­ме­на­тель: l конец дроби левая круг­лая скоб­ка дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 1 конец дроби плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: l плюс 2 конец дроби плюс \ldots плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: k минус 1 конец дроби пра­вая круг­лая скоб­ка минус 1 .

По­сколь­ку вы­ра­же­ние в скоб­ках при фик­си­ро­ван­ном l и не­огра­ни­чен­ном k может быть сде­ла­но сколь угод­но боль­шим, то можно вы­брать k так, что эта раз­ность будет боль­ше раз­но­сти между a левая круг­лая скоб­ка 1, k пра­вая круг­лая скоб­ка и пер­вой сум­мой, ко­то­рая одним лишь вы­бо­ром l может быть сде­ла­на сколь угод­но боль­шой для про­из­воль­но­го k боль­ше l. Утвер­жде­ние до­ка­за­но.

 

Ответ: нет.

1