две простые задачки (математическое)

[avva]

Две простые задачки, которые можно решить в уме. Из книги Винклера, которую я купил на днях и наслаждаюсь. Первую я знал, она древняя и знаменитая, но вторая для меня новая, и я некоторое время помучился, пока не дошло.

1. Вдоль кругового маршрута в пустыне расположены заправочные станции. Бензина, который на них всех в сумме есть, как раз ровно хватает, чтобы объехать весь маршрут и вернуться в исходную точку. Бак у машины достаточно просторный, чтобы вместить бензин на весь маршрут, если нужно. Доказать, что есть такая станция, что машина с пустым баком может начать с нее и проехать весь маршрут.

2. Алиса и Боб играют в следующую игру. На столе выложены в ряд 50 монет, причем каждая из монет может быть любого достоинства. Алиса берет монету с одного из концов ряда, потом Боб берет опять с одного из концов, потом опять Алиса и так далее, пока монеты не закончились. Доказать, что Алиса всегда сможет набрать сумму, равную или больше той, что будет у Боба.

Update: учтите, что в комментариях есть уже верные ответы!

Comments

[plakhov.livejournal.com]

Или я чего не понял, или все равно не работает: например, на круге где угодно может находиться заправка с нулевым количеством бензина. В том числе, ничто не мешает ей оказаться той самой "заправкой, которая будет расположена на маршруте после точки, когда теоретического бензина в баке не окажется" (что бы мы под этим ни подразумевали).

[navi03.livejournal.com]

Да, вы правы, нужно сделать оговорку "если это заправка с нулевым количеством бензина, то нужно выбрать следующую за ней, а эту проигнорировать".

[plakhov.livejournal.com]

Все равно. Пусть в ней будет не 0, а ε (маленькое, близкое к нулю, но ненулевое) количество бензина. Например, такое, которого хватит, чтобы проехать сантиметр. По-моему, такое решение до правильного не доводится.

[navi03.livejournal.com]

Если там даже е количество бензина, всё работает. Эта заправка просто не окажется первой после периода с нулевым (или отрицательным количеством бензина), она не будет первой, с которой мы будем начинать маршрут.

[plakhov.livejournal.com]

Значит, я, видимо, не понимаю, как устроено ваше решение. Я понял его так: сначала начинаем откуда угодно и едем "понарошку". В какой-то момент у нас понарошку "заканчивается бензин", тогда мы движемся далее до следующей станции А и оттуда уже начинаем движение "по-настоящему". Но такой алгоритм не работает: как ничто не помешает станции А содержать нулевое количество бензина, так ничто и не помешает ей содержать эпсилон.

[navi03.livejournal.com]

Сделала уже оговорку, нет у нас станций без бензина, а если есть, то мы их игнорируем. :-)

[plakhov.livejournal.com]

Да неважно здесь, ноль или не ноль. Идея с (почти) пустой станцией просто помогает понять, что это решение не работает. Если нужен конкретный пример без нулей и эпсилонов - вот он.

Пусть у нас круг длиной 12 км и всего три станции, А с бензином на километр на отметке "12 часов" (я здесь и далее разметил круг как обычные часы со стрелками), Б с бензином на километр на отметке "три часа", и В с бензином на 11 километров на отметке "9 часов". Мы начинаем с А. На отметке "1 час" у нас заканчивается бензин, следующая по кругу станция Б, и, согласно вашему алгоритму, она должна являться решением. Но она им не является.

[navi03.livejournal.com]

Там выше было сказано, что если таких точек, где бензина в баке нет, несколько, то мы берём самую "низкую" из них.
Вот мы едем понарошку. Начинаем с А, у нас 1 км есть бензин, в час у нас 0 бензина, в 2 часа -1, в точке Б у нас -2, доливаем 1 получаем -1. Едем дальше. В 4 часа у нас уже - 2, в 5 часов -3, в 6 часов -4... в точке В -7. Доливаем 11, получаем -7+11=4.

Итак мы имеем: в промежутке то А до Б самая низкая точка -2, в промежутке от Б до В - самая низкая точка у нас - 7. Это и есть самый низки промежуток. Следующая за этим промежутком станция В. С неё мы и начнём.

Только у вас вышло 13 литров на 12 км. Но это не существенно конечно.
Если предположить, что где-то на этом маршруте есть станция с нулевым количеством бензина, это ни на что не влияет.

[plakhov.livejournal.com]

Спасибо, наконец понял, что вы имели в виду. Да, так получится.

[navi03.livejournal.com]

:-)

[plakhov.livejournal.com]

И, кстати, это решение лучше моего, т.к. тривиально обобщается на непрерывный случай _Winnie

[navi03.livejournal.com]

Приятно. :-)))

[navi03.livejournal.com]

Вы забываете о том, что на окружности длиной 100 бензина ровно на 100. И если есть станция без бензина, то она не имеет значения, поскольку всё равно все остальные станции имеют в сумме бензина ровно 100.

[plakhov.livejournal.com]

Ответил выше.