Puzzle #94. Грузоперевозки

Разбор

У некоторых людей возникли вопросы, мол, а в чем тут задача. Ведь 36 тонн легко можно перевезти ровно за 9 поездок в грузовике с грузоподъемностью 4 тонны, т.к. 36 / 4 = 9.

Все верно, только в условии было сказано, что мешки весят не более тонны. Т.е. когда все мешки нагружены ровно в 1 тонну - частный случай. В реальности же, они будут разного веса. И даже для случая, когда все мешки весят ровно 600 кг, понадобится не менее 10 поездок, т.к. в грузовик вместится максимум только 6 мешков за раз.

Задача заключается именно в том, чтобы наверняка доказать, что какого бы веса мешки не были, нам понадобится не более 11 поездок.

Итак, 

1. Каждый раз мы нагружаем грузовик до тех пор, пока масса груза не превысит 4 тонны.
2. Затем мы уберем 1 мешок и отложем его в сторону. Масса груза будет не более 4х тонн.
3. Таким образом делаем 8 поездок. После этого у нас будет ровно 8 отложенных мешков.
4. Мы перевезли (8 * ~4 <= ~32 тонны) не более 32 тонн. Осталось не менее 4х тонн, из ктр часть на складе, часть в отложенных мешках.
5. За 9ю поездку отвезем отвезем часть на складе.
6. 10й и 11й поездки хватит на переправку 8 оставшихся мешков.

Пример: 

71 мешок по 501 кг (35571 кг) + 1 мешок по 429 кг

В грузовик максимум сможем погрузить всего 7 мешков (8 * 501 > 4000 кг).

Делаем 8 поездков: перевезем 56 мешков (вес 56 * 501 = 28056 кг).

На складе осталось 8 мешков + 8 мешков, ктр мы отложили. Общий вес, ктр осталось перевезти 15 * 501 + 429 = 7944 кг.

Остается сделать 9ю и 10ю поездку.