Решение задачи 365

Условие:

Несколько ящиков вместе весят 10 тонн, причём каждый весит не больше 1 тонны. Какого наименьшего числа трёхтонок заведомо достаточно, чтобы увезти весь груз?

Решение:

Оценка:
Будем разбивать все ящики на группы так, чтобы в каждой группе суммарный вес не превосходил 3 тонн. Назовем группу плохой, если суммарный ее вес не превосходит 2 тонн, иначе назовем хорошей. Покажем, что всегда можно разбить на группы так, чтобы было не более одной плохой группы. Действительно, пусть есть две плохие группы. Переложим любой ящик из первой плохой группы во вторую. Заметим, что суммарный вес второй группе до сих пор не превышает 3 тонн, так как все ящики весят не более 1 тонн. Продолжаем этот процесс до тех пор, пока вторая группа не станет хорошей. Повторяя аналогичные действия с другими парами плохих групп, добьемся того, что останется максимум одна плохая группа. Хороших групп не может быть больше четырех, значит всего групп не более пяти. Значит, пять трехтонок заведомо хватит.

Пример:
Покажем, что четырех трехтонок не всегда хватит. Пусть имеется 13 одинаковых ящиков, то есть каждый весит по 10/13 тонн или 10000/13 килограммов. В один грузовик четыре ящика положить не получится, так как 10*4/13 > 3, значит в трехтонку влезет максимум три ящика. Это значит, что четырьмя трехтонками не обойтись.

Ответ: Пять.