две простые задачки (математическое)
Sep. 13th, 2013 02:53 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaДве простые задачки, которые можно решить в уме. Из книги Винклера, которую я купил на днях и наслаждаюсь. Первую я знал, она древняя и знаменитая, но вторая для меня новая, и я некоторое время помучился, пока не дошло.
1. Вдоль кругового маршрута в пустыне расположены заправочные станции. Бензина, который на них всех в сумме есть, как раз ровно хватает, чтобы объехать весь маршрут и вернуться в исходную точку. Бак у машины достаточно просторный, чтобы вместить бензин на весь маршрут, если нужно. Доказать, что есть такая станция, что машина с пустым баком может начать с нее и проехать весь маршрут.
2. Алиса и Боб играют в следующую игру. На столе выложены в ряд 50 монет, причем каждая из монет может быть любого достоинства. Алиса берет монету с одного из концов ряда, потом Боб берет опять с одного из концов, потом опять Алиса и так далее, пока монеты не закончились. Доказать, что Алиса всегда сможет набрать сумму, равную или больше той, что будет у Боба.
Update: учтите, что в комментариях есть уже верные ответы!
1. Вдоль кругового маршрута в пустыне расположены заправочные станции. Бензина, который на них всех в сумме есть, как раз ровно хватает, чтобы объехать весь маршрут и вернуться в исходную точку. Бак у машины достаточно просторный, чтобы вместить бензин на весь маршрут, если нужно. Доказать, что есть такая станция, что машина с пустым баком может начать с нее и проехать весь маршрут.
2. Алиса и Боб играют в следующую игру. На столе выложены в ряд 50 монет, причем каждая из монет может быть любого достоинства. Алиса берет монету с одного из концов ряда, потом Боб берет опять с одного из концов, потом опять Алиса и так далее, пока монеты не закончились. Доказать, что Алиса всегда сможет набрать сумму, равную или больше той, что будет у Боба.
Update: учтите, что в комментариях есть уже верные ответы!
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-09-14 12:48 pm (UTC)1. Дано N заправок. Если N=1 решение тривиально. Если N>1 надо искать рекурсию, вернуться к той же проблеме с N-1 заправками. Ок, заправляемся где достаточно бензина, доезжаем до следующей, и ...
2. ... тут включается воображение. Во стою я на заправке, чуть чуть бензина у меня еще есть, но хватит ли до следующей я не знаю. И в какую сторону ехать? Рекурсия не работает потому что проблема усложнилась. Теперь точка отправления фиксирована...
Компьютерные игры разрушили мой мозг