Обиколка на писта.

[ABK]

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

[ptj]

За да има задачата решение е необходимо резервоара да побира всичкото количество бензин, което е коректно да беше пояснено в условието.

[ptj]

Индукция:

1.) Нека съществува начин за преминаване на писта с дължина [tex]S_n[/tex] с помощта на [tex]n[/tex] туби бензин.

2.)Ще покажем, че съществува начин за преминаване на писта с дължина [tex]S_{(n+1)}=S_n+l[/tex], където [tex]l[/tex] e разстоянието съответстващо на новата [tex](n+1)[/tex]-ва туба.
Да отбележим с [tex]B[/tex], точката където се намира [tex](n+1)[/tex]-вата туба, а съответно с [tex]A[/tex]и [tex]C[/tex] точките по пистата намиращи се на разстояние [tex]l[/tex] от [tex]B[/tex].
Съгласно 1.) или маршрута [tex]AC[/tex]или маршрута [tex]CA[/tex] (без преминаване и за 2-та през[tex]B[/tex]) могат да се преминат с [tex]n[/tex] туби бензин.
Тогава очевидно и единия от маршрутите [tex]ACB[/tex] или [tex]CAB[/tex] се изминава с [tex]n[/tex] туби бензин, а наличието на [tex]n+1[/tex]-вата туба ще е достатъчно за преминаване на целия маршрут [tex]ACBA[/tex] или на целия маршрут [tex]CABC[/tex], т.е. на писта с дължина [tex]S_(n+1)[/tex].
3.) n=1 задачата очевидно има решение.

От 1.), 2.) и 3.) съгласно принципа на пълната математическа индукция, следва че зaдачата има решение за произволно [tex]n[/tex].

[pal702004]

Може да се направи обиколката и при фиксирано направление (напр. по часовниковата стрелка).
От решението на ptj също така не ставя ясно при добавяне на нова точка (удължаване на пистата с l) колко бензин има в нея (може да има и 0 бензин).
Ако отбележим с [tex]a_k[/tex] разстоянието от точката до съседната точка (по часовниковата стрелка), а с [tex]b_k[/tex] - бензина, тоест, разстоянието, което може да измине с бензина в т. [tex]k[/tex]. то може a[tex]_k \ne b_k \;\forall k[/tex]. И номера с просто добавяне на нова точка не виждам как ще мине.
Номера тука може да мине с "премахване" на точка - метода на спускането. Тъй като съществува [tex]k:\;b_k \ge a_k[/tex], то модела се запазва с премахването на точка [tex]k[/tex] и "преразпределяне"
(Ако в т. k има повече бензин, отколкото е необходимо да стигне до следващата точка, това е равносилно на увеличаване количеството бензин в следващата точка с разликата и изравнявамето им в т. к)

[tex]b_{k+1}:=b_{k+1}+b_k-a_k,\quad a_{k-1}:=a_{k-1}+a_k,\quad b_{k-1}:=b_{k-1}+a_k[/tex]

с намаляне броят на точките и запазване на началните условия [tex]\sum a_i=\sum b_i[/tex]

[pal702004]

Задачата може да се формализира по следният начин (ако работим с разликите [tex]c_k=b_k-a_k[/tex]

За всяка редица[tex]\{c\}: \sum c_i=0[/tex] съществува елемент [tex]k[/tex]:

[tex]c_k \ge 0[/tex]
[tex]c_k+c_{k+1}\ge 0[/tex]
[tex]\cdots[/tex]
[tex]c_k+\cdots+c_n+c_1+\cdots c_{k-1} \ge 0[/tex]

Идея: Ако [tex]c_k \ge 0[/tex] и [tex]c_k+c_{k+1} \ge 0[/tex], то двата елемента могат да се обединят

[drago]

Да допуснем противното, т.е. тръгвайки от всяка туба е невъзможно да се обиколи пистата. Да означим с [tex]A_1[/tex] тубата, тръгвайки от която ще изминем най-голямо разстояние(примерно по часов. стрел.) . Нека останалите (в същата посока) са [tex]A_1,A_2,\ldots,A_n[/tex]. Значи като тръгнем от [tex]A_1[/tex] стигаме до някъде преди [tex]A_{j_1}[/tex]; след това като тръгнем от [tex]A_{j_1}[/tex] стигаме някъде преди [tex]A_{j_2}[/tex] и т.н. Не е възможно, продължавайки така, да спрем някъде м/у [tex]A_n[/tex] и [tex]A_1[/tex], тъй като тогава с общия бензин не би могло да обиколим пистата. Значи тръгвайки от някое [tex]A_{j_k}[/tex] ще прехвърлим [tex]A_1[/tex] и след това ще изминем поне целия път, който изминаваме тръгвайки от [tex]A_1[/tex]. Значи от начална точка [tex]A_{j_k}[/tex] ще изминем строго повече разстояние, отколкото тръгвайки от [tex]A_1[/tex], което е противоречие с избора на [tex]A_1[/tex].
Това в условието, че бензина във всяка туба е различно количество, е излишно.

[pal702004]

Да, доказателството на Драго е коректно.
Но не е трудно да се докаже и във по-формализираната версия: Ако в кръг са разположени [tex]n[/tex] числа (положителни, отрицателни, нули) с общ сбор 0, то съществува точка, тръгвайки от която в дадено направление сбора на първите [tex]k[/tex] числа е неотрицателен [tex]k \in [1;n][/tex]
С екстра алгоритъм за намирането и.

[ABK]

Благодаря. Това е задача от сръбско контролно за Младежката балканска олимпиада.

[drago]

@pal702004: Да, така е, вариация на същата идея. Допускаме противното и нека за всяко [tex]j[/tex] нека [tex]k_j[/tex] е първото [tex]n, n>j[/tex] със свойството [tex]c_j+c_{j+1}+\ldots+ c_{k_j} <0[/tex]. Тук за удобство предполагаме [tex]c_{n+i}=c_i[/tex]. Вземаме онова j , за което [tex]k_j-j\,, j=1,2,\ldots,n[/tex] е най-голямо. Тръгваме от това [tex]j[/tex] и последователно както по-горе обикаляме и ще получим противоречие с това, че [tex]k_j[/tex] е първото с описаното по-горе свойство. Що се отнася до алгоритъм, при крайни конфигурации, след като знаем съществуването на нещо, просто правим проверката на всички варианти и все някъде ще ударим 6-ца от тотото
Тази задача още вчера ми напомни на нещо, което съм виждал, но не можах да го намеря. Всъщност, се оказва, че такава задача, или поне със същата идея е давана на Putnam 1995, A4:
http://www.artofproblemsolving.com/Foru ... 0&t=595985

Задачата е същата..., като тръгнем в обратната посока ще обърнем знака на неравенствата.