?
Ни о какой безапелляционности в моих высказываниях не может быть и речи! [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

две простые задачки (математическое) [сент. 13, 2013|02:53 pm]
Anatoly Vorobey
[Tags|]

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

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

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
(Удалённый комментарий)
[User Picture]From: biglebowsky
2013-09-13 12:11 pm
+1
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: biglebowsky
2013-09-13 12:11 pm
У Алисы первый ход.
(Ответить) (Parent) (Thread)
From: michael.ul.myopenid.com
2013-09-13 12:36 pm
По первой задаче.
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, чтобы автор поста сам решил когда это публиковать
(Ответить) (Thread)
[User Picture]From: avva
2013-09-13 05:50 pm
Все верно, только редуцировать можно легче: вместо "удаления промежутка" просто перенести все топливо из заправки к предыдущей, а эту заправку убрать.
(Ответить) (Parent) (Thread)
[User Picture]From: goliafffff
2013-09-13 12:38 pm
Вопросы по первой задаче: "Фиксировано ли расстояние между станциями?", "Возможны ли станции на которых бензина нет?", "Существует ли ограничение на минимальное количество бензина в станции, таким образом, чтобы можно было доехать до ближайшей станции?"

Вопросы по второй задаче: "Монеты могут быть любого достоинства. Значит ли это, что достоинство каждой монеты принадлежит множеству натуральных чисел и, по сути дела, может быть сколь угодно большим?" и "Стремятся ли Алиса и Боб набрать как можно больше монет, или они берут их случайно?"
(Ответить) (Thread)
[User Picture]From: avva
2013-09-13 12:51 pm
Первая задача: 1) не фиксировано. 2) Возможно, хотя тогда можно просто притвориться, что их нет, все равно с них начинать бесперспективно. 3) нет ограничения.

Вторая задача: 1) достоинство каждой монеты может быть сколь угодно большим, да. 2) Алиса стремится набрать не меньше денег (не монет, а денег, монет у них будет поровну), чем Боб. Нам нужно помочь ей в этом. Она не ставит цели обязательно набрать максимум, и она не может рассчитывать на то, что Боб ставит такую цель.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: katyat
2013-09-13 12:38 pm
Пардон, коммент был преждевременный, решила вторую.
(Ответить) (Thread)
From: michael.ul.myopenid.com
2013-09-13 12:55 pm
Вторая задача вообще простая. Нумеруем монетки и делим их на два множества, с чётными номерами и нечётными. Понятно, что сумма денег в них будет либо равна, либо в одном будет больше. Алиса первым ходом выбирает множество, из которого она будет брать монетки и всё.

http://www.google.com
(Ответить) (Thread)
[User Picture]From: avva
2013-09-13 05:50 pm
Ага, все верно.
(Ответить) (Parent) (Thread)
From: captain_tylor
2013-09-13 01:27 pm
Кажется, года три назад вы про первую задачу уже писали.
(Ответить) (Thread)
[User Picture]From: avva
2013-09-13 01:32 pm
Это возможно. Она очень известная.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: _winnie
2013-09-13 01:57 pm
Красивая задача про монеты, спасибо.
Спойлер: http://pastebin.com/bJV5LtkX
(Ответить) (Thread)
[User Picture]From: _winnie
2013-09-13 02:11 pm
И первая задача. Чувствую, что можно менее косноязычно и просто, но пока не понимаю как:
http://pastebin.com/48WaGS9N

Интресно, можно ли обощить до какой-нибудь полезной теоремы с интегралом по окружности.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dimrub
2013-09-13 01:58 pm
Я первую не слышал раньше, но кажется решил. Выберем случайным образом бензоколонку a0, и начнем ехать. Допустим, мы доехали до некоей точки, от которой до следующей бензоколонки (назовем ее a1) r0 километров. На бензоколонках в интервале [a1, a0) достаточно бензина, чтобы проехать расстояние [a1, a0] + r0. Теперь начнем с a1. Если нам удалось доехать до a0, то мы в шоколаде, поскольку у нас еще в запасе достаточно бензина, чтобы проехать r0. Если же нет, то мы находимся на расстоянии r1 до a2, и на отрезке [a2, a0) достаточно бензина, чтобы проехать [a2, a0] + r0 + r1. Так мы продолжаем, пока не доедем до бензоколонки, непосредственно предшествующей a0 (an). На ней достаточно бензина, чтобы проехать отрезок [an, a0] плюс все остатки, а значит, если мы с нее начнем, то мы проделаем весь круг.
(Ответить) (Thread)
[User Picture]From: avva
2013-09-13 05:46 pm
Да, кажется, все верно, работает. Более обычное решение покороче см. в комментариях.
(Ответить) (Parent) (Thread)
[User Picture]From: navi03
2013-09-13 02:01 pm
Нужно начать со станции, где максимальное количество бензина и двигаться в том из двух направлений, в котором следующая станция находится ближе.

Edited at 2013-09-13 14:26 (UTC)
(Ответить) (Thread)
[User Picture]From: spamsink
2013-09-13 03:30 pm
Нет. Предположим, на круге длиной 100 есть 10 заправок емкости 9 на расстоянии 1 друг от друга, и заправка емкостью 10 диаметрально противоположно от средней из тех 9.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: plakhov
2013-09-13 02:10 pm
Первая не понял, почему такая уж знаменитая: решается по индукции (шаг: если от А можно доехать до Б, то можно заменить их на А+Б, находящуюся в А).
Вторая очень клевая! Спойлер: Алиса всегда может взять или все монеты с четными номерами, или все с нечетными, и Боб ей в этом никак помешать не может
(Ответить) (Thread)
From: dmpogo
2013-09-13 04:58 pm
не получится так просто, не учитывается невозможность изменения направления движения, а выбрав А,Б, выбирается и направление. И тут то может оказаться что заправка со кучей бензина у вас за спиной
(Ответить) (Parent) (Thread) (Развернуть)
From: huzhepidarasa
2013-09-13 02:13 pm
Найдем какую-нибудь бензоколонку А, от которой можно доехать до следующей бензоколонки Б, и перенесем весь бензин из Б в А. Если в получившемся состоянии возможен круговой маршрут, то он возможен и в исходном состоянии. Будем повторять, пока не останется одна бензоколонка.

Всем удачной записи и подписи.
(Ответить) (Thread)
[User Picture]From: avva
2013-09-13 05:44 pm
И вам!
(Ответить) (Parent) (Thread)
[User Picture]From: _winnie
2013-09-13 02:37 pm

Придумал обобщение первой задачи: если у периодической функции с периодом T интеграл на [0,Т] больше Т, то можно выбрать x так, что интеграл на [x,x+t] больше t
(Ответить) (Thread)
[User Picture]From: _winnie
2013-09-13 02:45 pm
Я считаю, необходимо зафиксировать черновик.

(Ответить) (Thread)
[User Picture]From: avva
2013-09-13 05:43 pm
:) прекрасно!
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2013-09-13 04:20 pm
Вторая задача напомнила другую красивую.

Алиса и Боб играют в следующую игру. Они по очереди кладут круглые монеты диаметром 1 на квадратный стол 10x10. Монету можно класть в произвольное место стола, не занятое другими монетами; монета должна быть полностью на поверхности (не свисать) и не пересекаться с другими монетами. Проигрывает тот, кому некуда положить монету. Доказать, что Алиса, которая ходит первой, всегда может выиграть.
(Ответить) (Thread)
[User Picture]From: butbka
2013-09-13 04:35 pm
А эта напомнила задачу про выкладывание шахматной доски доминошками
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>