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

[avva]

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

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

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

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

Comments

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

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

[Error: Irreparable invalid markup ('<b_i [...] k,>') 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, чтобы автор поста сам решил когда это публиковать

[avva.livejournal.com]

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