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

[avva]

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

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

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

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

Comments

[vromanov.livejournal.com]

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

[biglebowsky.livejournal.com]

+1

[hshhhhh.livejournal.com]

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

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

[biglebowsky.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, чтобы автор поста сам решил когда это публиковать

[avva.livejournal.com]

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

[goliafffff.livejournal.com]

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

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

[avva.livejournal.com]

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

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

[katyat.livejournal.com]

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

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

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

http://www.google.com

[avva.livejournal.com]

Ага, все верно.

[captain-tylor.livejournal.com]

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

[avva.livejournal.com]

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

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

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

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

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

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

[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] плюс все остатки, а значит, если мы с нее начнем, то мы проделаем весь круг.

[avva.livejournal.com]

Да, кажется, все верно, работает. Более обычное решение покороче см. в комментариях.

[navi03.livejournal.com]

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

[spamsink.livejournal.com]

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

[plakhov.livejournal.com]

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

[dmpogo.livejournal.com]

не получится так просто, не учитывается невозможность изменения направления движения, а выбрав А,Б, выбирается и направление. И тут то может оказаться что заправка со кучей бензина у вас за спиной

[huzhepidarasa.livejournal.com]

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

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

[avva.livejournal.com]

И вам!

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

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

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

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

[avva.livejournal.com]

:) прекрасно!

[gul-kiev.livejournal.com]

Вторая задача напомнила другую красивую.

Алиса и Боб играют в следующую игру. Они по очереди кладут круглые монеты диаметром 1 на квадратный стол 10x10. Монету можно класть в произвольное место стола, не занятое другими монетами; монета должна быть полностью на поверхности (не свисать) и не пересекаться с другими монетами. Проигрывает тот, кому некуда положить монету. Доказать, что Алиса, которая ходит первой, всегда может выиграть.

[butbka.livejournal.com]

А эта напомнила задачу про выкладывание шахматной доски доминошками

[navi03.livejournal.com]

У меня про Алису есть вот такая книга.
У кого дети постарше очень советую. Мои дети задачи из первых двух глав решили с удовольствием. Дальше идут задачи посложнее, и пока им не по силам. Но зато я играюсь.
Очень хороший лёгкий язык. Автор - умница.
http://www.livelib.ru/book/1000310517

[migmit.livejournal.com]

Ну дык! Смаллиан! Его даже представляли как-то раз: "Имею честь представить вам профессора Смаллиана, который сейчас докажет вам, что либо он не существует, либо вы не существуете, но кто именно не существует, вам не известно".

[migmit.livejournal.com]

Чего-то все какую-то индукцию в первой задаче изобретают, хотя всё тривиально.

Заправим бак на полный маршрут, и поедем с любого места, на каждой заправке выгребая всё горючее (будем считать, что бак достаточно большой и его хватит). Когда вернёмся в исходную точку — бак будет снова заправлен на полный маршрут (сколько потратили, столько из выгребли). Возьмём станцию, на подъезде к которой у нас было наименьшее количество горючего. Если уменьшить начальную заправку бака на это количество, мы всё равно сумеем объехать весь круг (и при этом в конце у нас будет то же количество горючки, что и в начале), но к этой станции причапаем на последних каплях. Теперь остаётся поменять местами две части маршрута — до этой заправки, и после неё, и мы получили искомое решение. На стыке всё сойдётся, так как количество горючего в баке до и после стыка будет одинаковым.

[avva.livejournal.com]

Да, это то же решение по сути, что предложил _winnie выше.

[mathclimber.livejournal.com]

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

И написал пост про три мои любимые задачки: http://mathclimber.livejournal.com/32371.html

[ruslan-lv.livejournal.com]

Задачи забавные, но слишком много недоговорённостей.

[bud dy (from livejournal.com)]

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

[leonid-smetanin.livejournal.com]

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

[avva.livejournal.com]

Каждый ход каждый из них выбирает, с какого конца брать.

[109518.livejournal.com]

Мне кажется задача номер 1 это пример того как воображение мешает в доказательствах. Я её решить не смог. Рассуждал я так:

1. Дано N заправок. Если N=1 решение тривиально. Если N>1 надо искать рекурсию, вернуться к той же проблеме с N-1 заправками. Ок, заправляемся где достаточно бензина, доезжаем до следующей, и ...

2. ... тут включается воображение. Во стою я на заправке, чуть чуть бензина у меня еще есть, но хватит ли до следующей я не знаю. И в какую сторону ехать? Рекурсия не работает потому что проблема усложнилась. Теперь точка отправления фиксирована...

Компьютерные игры разрушили мой мозг

[vromanov.livejournal.com]

У меня по первой задаче вот такая идея. Будем рисовать график запаса горючего от растояния. Это будет пилообразный график. С вертикальными скачками на заправках и постепенным понижением между ними. Т.к. указано, что количество горючего как раз хватает на весь путь, то левая и правая точка будут лежать на одной высоте. Т.е. график можно замкнуть. Проведем горизонтальную линию через точку относящуюся к какой-либо заправке. Пока ломанная выше этой линии - значит бензина хватает, как только становится ниже - бензин кончился.
В результате, выбираем одну (или несколько) точек, которые лежат ниже всего на этой ломанной. С них можно стартовать, и бензин никода не кончится.

[avva.livejournal.com]

Да, все верно.

[rosinkauri.livejournal.com]

Верно ли я понимаю условие 1ой задачи: бензина хватает на весь маршрут и обратно (т. е. на 2 круга)?

[barzel.livejournal.com]

2. Мне кажется, что у Алисы нет выигрышной стратегии.

Допустим она ходит 9. У Боба 4 варианта: 1,5,2,4. Допустим он ходит 1. Тогда у Алисы 2 варианта: 2 или 4. Что бы она не выбрала, Боб всегда может ее блокировать.

ПОсле первого хода Алисы, есть 4 варианта развития. Боб выбирает любой произвольно, тогда у Алисы два варианта. Она выбирает один из них, а Боб другой.