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


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

Рас­смат­ри­ва­ют­ся все­воз­мож­ные на­бо­ры дей­стви­тель­ных чисел x1, ..., x2021, не пре­вос­хо­дя­щих по мо­ду­лю 1, с сум­мой 0. Для ка­ко­го наи­мень­ше­го C можно любой такой набор рас­ста­вить по кругу так, что сумма любых не­сколь­ких сто­я­щих под­ряд чисел будет по мо­ду­лю не боль­ше C?

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

Ре­ше­ние.

До­ка­жем что C боль­ше или равно 2 минус дробь: чис­ли­тель: 2, зна­ме­на­тель: 1011 конец дроби . Рас­смот­рим набор из 1010 чисел −1, и 1011 чисел  дробь: чис­ли­тель: 1010, зна­ме­на­тель: 1011 конец дроби . Ясно что при любой рас­ста­нов­ке по кругу два по­ло­жи­тель­ных ока­жут­ся рядом, зна­чит, най­дет­ся дуга с сум­мой  дробь: чис­ли­тель: 2020, зна­ме­на­тель: 1011 конец дроби .

По­ка­жем, что при любом ко­ли­че­стве чисел n верна оцен­ка

C левая круг­лая скоб­ка n пра­вая круг­лая скоб­ка мень­ше или равно 2 минус дробь: чис­ли­тель: 2, зна­ме­на­тель: левая квад­рат­ная скоб­ка дробь: чис­ли­тель: левая круг­лая скоб­ка n плюс 2 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби пра­вая квад­рат­ная скоб­ка конец дроби .

До­ка­зы­вать это будем, как ни стран­но, ин­дук­ци­ей по n. База при n=1,2,3 про­ве­ря­ет­ся не­по­сред­ствен­но. Так же за­ме­тим, что для рас­ста­нов­ки чисел по кругу усло­вие, что сумма на любой дуге по мо­ду­лю не боль­ше C, эк­ви­ва­лент­но усло­вию, что для про­из­воль­ной по­зи­ции на круге мно­же­ство сумм по всем дугам, име­ю­щим левый конец в этой по­зи­ции, уме­ща­ет­ся на от­рез­ке длины C. Этой пе­ре­фор­му­ли­ров­кой мы и будем поль­зо­вать­ся в даль­ней­шем.

Лемма. Опре­де­лим опе­ра­цию пре­об­ра­зо­ва­ния на­бо­ра: за­ме­ним в на­бо­ре два числа раз­ных зна­ков a и −b (пусть a, b боль­ше или равно 0 пра­вая круг­лая скоб­ка на одно число a − b. Тогда если по­лу­чен­ный набор до­пус­ка­ет рас­ста­нов­ку для не­ко­то­ро­го числа C и вы­пол­ня­ет­ся a плюс b мень­ше или равно C, то ис­ход­ный до­пус­кал рас­ста­нов­ку для C.

До­ка­за­тель­ство. Рас­ста­вим по кругу пре­об­ра­зо­ван­ный набор, и вос­поль­зу­ем­ся пе­ре­фор­му­ли­ро­ван­ным усло­ви­ем, на­чи­ная от по­зи­ции, на ко­то­рой стоит до­бав­лен­ное число a − b. Тогда по пе­ре­фор­му­ли­ро­ван­но­му усло­вию все суммы дуг, на­чи­на­ю­щих­ся в этой по­зи­ции (вклю­чая сумму, рав­ную нулю) по­кры­ва­ют­ся от­рез­ком длины C. Тогда в этот от­ре­зок по­па­ло и одно из чисел a и −b, по­сколь­ку они не могут ле­жать с раз­ных сто­рон от от­рез­ка  — рас­сто­я­нии между ними равно a + b, то есть не пре­вос­хо­дит длин­ны от­рез­ка. Если по­па­ло число a  — за­ме­ним a − b на числа a, −b (в таком по­ряд­ке), у по­лу­чен­ной рас­ста­нов­ки те же суммы, что у ис­ход­ной, и еще сумма a, ле­жа­щая где нужно. Ана­ло­гич­но за­ме­ним a минус b на числа −b, a если по­па­ло −b.

Те­перь до­ка­жем ин­дук­ци­он­ный пе­ре­ход. Рас­смот­рим набор из n чисел не боль­ших 1 по мо­ду­лю с сум­мой 0. Рас­смот­рим наи­мень­шие по мо­ду­лю по­ло­жи­тель­ное и от­ри­ца­тель­ное число. Если их сумма мо­ду­лей не боль­ше

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

то можно вос­поль­зо­вать­ся Лем­мой. Пусть их сумма боль­ше.

Тогда это воз­мож­но при чет­ном n толь­ко если по­ло­жи­тель­ных и от­ри­ца­тель­ных по­ров­ну. Тогда разо­бьем их на пары, как при до­ка­за­тель­стве Леммы. Тогда сумма чисел в каж­дой паре (то есть «новое» число) по мо­ду­лю не пре­вос­хо­дит

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

Наша за­да­ча рас­по­ло­жить их по кругу так, чтобы для не­ко­то­рой по­зи­ции A сумма по любой дуге с левым кон­цом в A ле­жа­ла бы на от­рез­ке

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

это оче­вид­но можно сде­лать. Те­перь вспом­ним, что каж­дое новое число это на самом деле два ста­рых, и рас­по­ло­жим эти ста­рые в по­ряд­ке по­ло­жи­тель­ное от­ри­ца­тель­ное. До­ба­ви­лись суммы, по­лу­ча­ю­щи­е­ся из ста­рых до­бав­ле­ни­ем од­но­го из пер­вых чисел пары, то есть не более чем еди­ни­цы. По­сколь­ку все ста­рые суммы ле­жа­ли на от­рез­ке длины

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

те­перь все суммы лежат на от­рез­ке длины

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

что и тре­бо­ва­лось. Пусть n=2 k минус 1, тогда сумма мо­ду­лей наи­мень­ших по мо­ду­лю по­ло­жи­тель­но­го и от­ри­ца­тель­но­го чисел может быть слиш­ком боль­шой толь­ко если ко­ли­че­ство по­ло­жи­тель­ных и от­ри­ца­тель­ных чисел от­ли­ча­ет­ся на еди­ни­цу. Без огра­ни­че­ния общ­но­сти пусть по­ло­жи­тель­ных k. Каж­дое по­ло­жи­тель­ное число, кроме са­мо­го ма­лень­ко­го, объ­еди­ним в пару с от­ри­ца­тель­ным. По­лу­чи­ли набор из k чисел (остав­ше­е­ся по­ло­жи­тель­ное и k − 1 сумм в парах, суммы в парах по мо­ду­лю не боль­ше  дробь: чис­ли­тель: 2, зна­ме­на­тель: k минус 1 конец дроби пра­вая круг­лая скоб­ка , остав­ше­е­ся по­ло­жи­тель­ное обо­зна­чим x, есте­ствен­но

 дробь: чис­ли­тель: k минус 2, зна­ме­на­тель: k конец дроби боль­ше или равно X боль­ше или равно дробь: чис­ли­тель: k минус 1, зна­ме­на­тель: k конец дроби .

Мы хотим эти числа рас­ста­вить по кругу с на­ча­лом от­сче­та так, чтобы по­след­ним сто­я­ло x, а все суммы кроме суммы k − 1 пары ле­жа­ли на от­рез­ке  левая квад­рат­ная скоб­ка минус дробь: чис­ли­тель: k минус 2, зна­ме­на­тель: k минус 1 конец дроби X, 0 пра­вая квад­рат­ная скоб­ка . Для этого сна­ча­ла вы­бе­рем пару, ко­то­рая вста­нет k минус 1−й по но­ме­ру: до­ста­точ­но взять ее мень­ше либо рав­ной чем  минус дробь: чис­ли­тель: 1, зна­ме­на­тель: k минус 1 конец дроби X, а такая най­дет­ся из сред­не­го зна­че­ния. Затем все осталь­ные пары рас­ста­вить как угод­но, чтобы их сумма не вы­хо­ди­ла из ко­ри­до­ра  — это воз­мож­но, по­то­му что мо­дуль чисел ма­лень­кий.

Те­перь пе­рей­дем от рас­ста­нов­ки пар к рас­ста­нов­ки ис­ход­ных чисел, по­ста­вив числа в каж­дой паре в по­ряд­ке от­ри­ца­тель­ное-по­ло­жи­тель­ное. По­сколь­ку до этого все суммы ле­жа­ли на от­рез­ке  левая квад­рат­ная скоб­ка минус дробь: чис­ли­тель: k минус 2, зна­ме­на­тель: k минус 1 конец дроби X, 0 пра­вая квад­рат­ная скоб­ка , зна­чит, и на от­рез­ке  левая квад­рат­ная скоб­ка минус дробь: чис­ли­тель: k минус 2, зна­ме­на­тель: k конец дроби , 0 пра­вая квад­рат­ная скоб­ка , те­перь они лежат на от­рез­ке  левая квад­рат­ная скоб­ка минус 1 минус дробь: чис­ли­тель: k минус 2, зна­ме­на­тель: k конец дроби , 0 пра­вая квад­рат­ная скоб­ка   — по­бе­да.

 

Ответ: 2 минус дробь: чис­ли­тель: 2, зна­ме­на­тель: 1011 конец дроби .

Спрятать критерии
Критерии проверки:

A B на­прав­ле­нии при­ме­ра (т. е. до­ка­за­тель­ства, что C боль­ше или равно дробь: чис­ли­тель: 2020, зна­ме­на­тель: 1011 конец дроби пра­вая круг­лая скоб­ка . При­мер, по­ка­зы­ва­ю­щий что для мень­ше­го C не ра­бо­та­ет — ±3 бал­лов.

Любые мень­шие зна­че­ния C: 0 бал­лов.

B Про­дви­же­ния в на­прав­ле­нии оцен­ки.

B0 Любая оцен­ка не силь­нее чем |a| плюс |b| где a — мак­си­маль­ное из по­ло­жи­тель­ных чисел, а b — ми­ни­маль­ное (т. е. мак­си­маль­ное по мо­ду­лю) из от­ри­ца­тель­ных: 0 бал­лов.

Любой ал­го­ритм рас­ста­нов­ки, обес­пе­чи­ва­ю­щий лишь что, что сумма на дугах с одним фик­си­ро­ван­ным кон­цом не боль­ше C: 0 бал­лов.