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

[avva]

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

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

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

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

Comments

[vromanov.livejournal.com]

В первой задаче еще должно быть условие что бак у машины безконечного объема.

[hshhhhh.livejournal.com]

> Доказать, что Алиса всегда сможет набрать сумму, равную или больше той, что будет у Боба.

Но ведь можно доказывать что Боб всегда сможет набрать сумму равную или больше той что будет у Алисы? А как так если ни у кого не может быть меньше половины?

[biglebowsky.livejournal.com]

У Алисы первый ход.

[biglebowsky.livejournal.com]

+1

[avva.livejournal.com]

Да, добавил.

[michael.ul.myopenid.com (from livejournal.com)]

По первой задаче.
1) Обозначим количество топлива на заправках - a_i, а количество топлива, нужное для проезда к следующей заправке - b_i. Докажем, что на окружности при выбранном зафиксированном направлении движения всегда существует заправка, от которой можно доехать до следующей. Доказательство от противного. Допустим, такой заправки не существует. Это означает, что a_i

[Error: Irreparable invalid markup ('<b_i [...] заправками>') in entry. Owner must fix manually. Raw contents below.]

По первой задаче.
1) Обозначим количество топлива на заправках - a_i, а количество топлива, нужное для проезда к следующей заправке - b_i. Докажем, что на окружности при выбранном зафиксированном направлении движения всегда существует заправка, от которой можно доехать до следующей. Доказательство от противного. Допустим, такой заправки не существует. Это означает, что a_i<b_i для любого i. Но тогда и сумма a_i меньше чем сумма b_i, а по условию они равны. Следовательно, на кольце всегда существует такая заправка, от которой можно доехать до соседа.
2) Для любого кольца с n заправками можно построить эквивалентное с n-1 заправкой. Согласно пункту 1, найдём заправку k, от которой можно доехать до заправки k+1. Удалим промежуток между заправками и k+1 заправку, поменяв на k-ой заправке количество топлива на a'_k=a_k-b_k+a_{k+1}>0. Получившееся кольцо эквивалентно исходному, просто с заправки k+1 стартовать нельзя.
3) Повторим процедуру, пока не стянем кольцо в единственную точку. Это и будет стартовая точка маршрута.

http://www.google.com, чтобы автор поста сам решил когда это публиковать

[goliafffff.livejournal.com]

Вопросы по первой задаче: "Фиксировано ли расстояние между станциями?", "Возможны ли станции на которых бензина нет?", "Существует ли ограничение на минимальное количество бензина в станции, таким образом, чтобы можно было доехать до ближайшей станции?"

Вопросы по второй задаче: "Монеты могут быть любого достоинства. Значит ли это, что достоинство каждой монеты принадлежит множеству натуральных чисел и, по сути дела, может быть сколь угодно большим?" и "Стремятся ли Алиса и Боб набрать как можно больше монет, или они берут их случайно?"

[katyat.livejournal.com]

Пардон, коммент был преждевременный, решила вторую.

[avva.livejournal.com]

Первая задача: 1) не фиксировано. 2) Возможно, хотя тогда можно просто притвориться, что их нет, все равно с них начинать бесперспективно. 3) нет ограничения.

Вторая задача: 1) достоинство каждой монеты может быть сколь угодно большим, да. 2) Алиса стремится набрать не меньше денег (не монет, а денег, монет у них будет поровну), чем Боб. Нам нужно помочь ей в этом. Она не ставит цели обязательно набрать максимум, и она не может рассчитывать на то, что Боб ставит такую цель.

[michael.ul.myopenid.com (from livejournal.com)]

Вторая задача вообще простая. Нумеруем монетки и делим их на два множества, с чётными номерами и нечётными. Понятно, что сумма денег в них будет либо равна, либо в одном будет больше. Алиса первым ходом выбирает множество, из которого она будет брать монетки и всё.

http://www.google.com

[captain-tylor.livejournal.com]

Кажется, года три назад вы про первую задачу уже писали.

[avva.livejournal.com]

Это возможно. Она очень известная.

[http://users.livejournal.com/_winnie/]

Красивая задача про монеты, спасибо.
Спойлер: http://pastebin.com/bJV5LtkX

[dimrub.livejournal.com]

Я первую не слышал раньше, но кажется решил. Выберем случайным образом бензоколонку a0, и начнем ехать. Допустим, мы доехали до некоей точки, от которой до следующей бензоколонки (назовем ее a1) r0 километров. На бензоколонках в интервале [a1, a0) достаточно бензина, чтобы проехать расстояние [a1, a0] + r0. Теперь начнем с a1. Если нам удалось доехать до a0, то мы в шоколаде, поскольку у нас еще в запасе достаточно бензина, чтобы проехать r0. Если же нет, то мы находимся на расстоянии r1 до a2, и на отрезке [a2, a0) достаточно бензина, чтобы проехать [a2, a0] + r0 + r1. Так мы продолжаем, пока не доедем до бензоколонки, непосредственно предшествующей a0 (an). На ней достаточно бензина, чтобы проехать отрезок [an, a0] плюс все остатки, а значит, если мы с нее начнем, то мы проделаем весь круг.

[navi03.livejournal.com]

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

[plakhov.livejournal.com]

Первая не понял, почему такая уж знаменитая: решается по индукции (шаг: если от А можно доехать до Б, то можно заменить их на А+Б, находящуюся в А).
Вторая очень клевая! Спойлер: Алиса всегда может взять или все монеты с четными номерами, или все с нечетными, и Боб ей в этом никак помешать не может

[http://users.livejournal.com/_winnie/]

И первая задача. Чувствую, что можно менее косноязычно и просто, но пока не понимаю как:
http://pastebin.com/48WaGS9N

Интресно, можно ли обощить до какой-нибудь полезной теоремы с интегралом по окружности.

[huzhepidarasa.livejournal.com]

Найдем какую-нибудь бензоколонку А, от которой можно доехать до следующей бензоколонки Б, и перенесем весь бензин из Б в А. Если в получившемся состоянии возможен круговой маршрут, то он возможен и в исходном состоянии. Будем повторять, пока не останется одна бензоколонка.

Всем удачной записи и подписи.

[http://users.livejournal.com/_winnie/]

Придумал обобщение первой задачи: если у периодической функции с периодом T интеграл на [0,Т] больше Т, то можно выбрать x так, что интеграл на [x,x+t] больше t

[http://users.livejournal.com/_winnie/]

Я считаю, необходимо зафиксировать черновик.

[nokachi.livejournal.com]

она даже у нас в классе по алгоритмам в Стэнфорде была

[spamsink.livejournal.com]

Нет. Предположим, на круге длиной 100 есть 10 заправок емкости 9 на расстоянии 1 друг от друга, и заправка емкостью 10 диаметрально противоположно от средней из тех 9.

[navi03.livejournal.com]

угу....

[navi03.livejournal.com]

Нужно начать с произвольной бензоколонки и записывать количество бензина в баке, которое собирается на пути. В каком-то месте пути будет точка, когда теоретического бензина в баке не окажется. Мы должны выбрать ту заправку, которая будет расположена на маршруте после этой точки. Это можно проделать в обоих направлениях.
Если взять ваш пример, то я начала со станции 10 и до первой станции 9 мне не хватит бензина, поскольку между ними 45 км. Это и будет место, когда бак пустой. А если я начну с первой станции 9 и буду двигаться по направлению к следующей станции 9, задача будет решена.
То есть в любом случае нужно пройти весь маршрут, прибавляя бензин из баков и отнимая расход, и найти промежуток, на котором бензина не будет. И следующая после этого промежутка станция - это нужное нам начало.

[spamsink.livejournal.com]

Таких точек может быть несколько.