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

[avva]

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

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

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

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

Comments

[goliafffff.livejournal.com]

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

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

[avva.livejournal.com]

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

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

[goliafffff.livejournal.com]

Ко второй задаче. До решения с чётными и нечётными так и не додумался, но кажется придумал алгоритм, при котором Алиса набирает большее количество денег.

Допустим у нас ряд из 50 монет.

Берём монету х_1 с любого из концов и далее рассматриваем ряд из 49 монет (без выбранной нами монеты). Вычитаем номинал выбранной нами монеты из номиналов монет, находящихся на правом и левом концах нового ряда: (x_л - x_1) и (x_п - х_1). Далее из этих двух разностей выбираем максимальную и обозначаем её х_1_diff.

Повторяем проведённую операцию. Снова берём ряд из 50 монет, выбираем монету х_2 с другого конца, рассматриваем ряд без этой монеты (49 монет) и вычитаем номинал выбранной монеты из начала и конца нового ряда: (x_л - x_2) и (x_п - х_2). Далее из этих двух разностей выбираем максимальную и обозначаем её х_2_diff.

После этого выбираем минимум между х_1_diff и х_2_diff. Если меньше х_2_diff, то выбираем монету х_2, если х_1_diff, то x_1.

Алгоритм позволят Алисе выбрать монету таким образом, чтобы после этого Боб мог взять монету, чей номинал наименее всего превосходит номинал монеты Алисы. Ну и естественно за счёт права первенства Алиса никогда не проиграет Бобу.

Вот так вот всё запутано и перепутано, но вроде как работает. :)

[avva.livejournal.com]

Я думал примерно в том же направлении, пока не догадался до решения с четными. Но тут есть проблема, или даже две проблемы.

Во-первых, все, чего вы добились - это что Алиса минимизировала свою потерю после ответного хода Боба. Мы не можем теперь сказать "после ответного хода Боба мы пользуемся индукционным предположением для 48 монет", потому что это всего лишь сохранит то невыгодное положение, в котором Алиса оказалась. Нам нужно что-то более сильное. Если скажем Алиса выбрала монету, а Боб выбрал монету на 10 больше, то теперь нам нужно, чтобы из оставшихся 48 монет Алиса могла обеспечить себе преимущество как минимум в 10, а не всего лишь преимущество как минимум в 0. А как это доказать, не очень ясно.

Во-вторых, этот алгоритм просто не работает :) Скажем, посмотрите на ряд монет

400 500 12 3

Если Алиса выберет 3, то Боб сможет добиться разницы в 397. Если Алиса выберет 400, то Боб сможет добиться всего лишь разницы в 100. По вашему алгоритму Алисе надо выбрать 400, но это неправильный выбор :)

[goliafffff.livejournal.com]

Да, мой алгоритм действительно сбоит при таком раскладе. Подозреваю, что для правильной оценки нужно каким-то образом ввести в расмотрение сумму накопленных денег у Алисы (а возможно и у Боба тоже).