Неделимые глыбы и грузовики

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

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

  1. Почему граница по общей массе не достигается
  2. Допустимая загрузка следующего количества

    Сначала: Почему граница по общей массе не достигается

  3. Ответ: да

    Сначала: Допустимая загрузка следующего количества

  4. Почему граница по общей массе не достигается

    Сначала: Ответ: да

  5. Допустимая загрузка следующего количества

    Сначала: Почему граница по общей массе не достигается

  6. Ответ: нет

    Сначала: Допустимая загрузка следующего количества

  7. Почему граница по общей массе не достигается

    Сначала: Ответ: нет

  8. Допустимая загрузка следующего количества

    Сначала: Почему граница по общей массе не достигается

  9. Ответ

    Сначала: Допустимая загрузка следующего количества

Разобранный пример

Имеются каменные глыбы: 50 штук по 800 кг, 60 штук по 1000 кг и 60 штук по 1500 кг (раскалывать глыбы нельзя).

а) Можно ли увезти все эти глыбы одновременно на 60 грузовиках, грузоподъёмностью 5 тонн каждый, предполагая, что в грузовик выбранные глыбы поместятся?

б) Можно ли увезти все эти глыбы одновременно на 38 грузовиках, грузоподъёмностью 5 тонн каждый, предполагая, что в грузовик выбранные глыбы поместятся?

в) Какое наименьшее количество грузовиков, грузоподъёмностью 5 тонн каждый, понадобится, чтобы вывезти все эти глыбы одновременно, предполагая, что в грузовик выбранные глыбы поместятся?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Общая масса требует хотя бы 38 грузовиков, и для ровно 38 каждый должен быть загружен ровно на 5000 кг. Остаток массы по модулю 500 показывает, что число глыб по 800 кг в каждом полном грузовике кратно пяти; больше пяти не помещается. Поэтому пятьдесят таких глыб занимают десять грузовиков, в каждом ещё одна глыба 1000 кг. Оставшиеся двадцать восемь полных грузовиков не могут содержать больше двух глыб по 1500 кг каждый: при трёх остаток 500 кг не заполняется глыбами по 1000. Максимум пятьдесят шесть таких глыб вместо необходимых шестидесяти - противоречие.
Шаг 2. Сначала в десять грузовиков кладём по пять глыб 800 кг и одной 1000 кг. Для оставшихся глыб проверяем число грузовиков с двумя глыбами 1000 и двумя 1500; оставшиеся тысячные укладываем по пять, полуторатонные - по три и при необходимости остаток в отдельный грузовик. Приведённая таблица количества грузовиков и их содержимого соблюдает вместимость и использует весь запас.
T=((10;5;1;0);(15;0;2;2);(4;0;5;0);(10;0;0;3))\mathcal T=\left(\left(10;5;1;0\right);\left(15;0;2;2\right);\left(4;0;5;0\right);\left(10;0;0;3\right)\right)
Шаг 3. Да. Приведённая конструкция выполняет все условия.
Шаг 1. Общая масса требует хотя бы 38 грузовиков, и для ровно 38 каждый должен быть загружен ровно на 5000 кг. Остаток массы по модулю 500 показывает, что число глыб по 800 кг в каждом полном грузовике кратно пяти; больше пяти не помещается. Поэтому пятьдесят таких глыб занимают десять грузовиков, в каждом ещё одна глыба 1000 кг. Оставшиеся двадцать восемь полных грузовиков не могут содержать больше двух глыб по 1500 кг каждый: при трёх остаток 500 кг не заполняется глыбами по 1000. Максимум пятьдесят шесть таких глыб вместо необходимых шестидесяти - противоречие.
Шаг 2. Сначала в десять грузовиков кладём по пять глыб 800 кг и одной 1000 кг. Для оставшихся глыб проверяем число грузовиков с двумя глыбами 1000 и двумя 1500; оставшиеся тысячные укладываем по пять, полуторатонные - по три и при необходимости остаток в отдельный грузовик. Приведённая таблица количества грузовиков и их содержимого соблюдает вместимость и использует весь запас.
T=((10;5;1;0);(15;0;2;2);(4;0;5;0);(10;0;0;3))\mathcal T=\left(\left(10;5;1;0\right);\left(15;0;2;2\right);\left(4;0;5;0\right);\left(10;0;0;3\right)\right)
Шаг 3. Нет. Доказанная граница исключает возможность.
Шаг 1. Общая масса требует хотя бы 38 грузовиков, и для ровно 38 каждый должен быть загружен ровно на 5000 кг. Остаток массы по модулю 500 показывает, что число глыб по 800 кг в каждом полном грузовике кратно пяти; больше пяти не помещается. Поэтому пятьдесят таких глыб занимают десять грузовиков, в каждом ещё одна глыба 1000 кг. Оставшиеся двадцать восемь полных грузовиков не могут содержать больше двух глыб по 1500 кг каждый: при трёх остаток 500 кг не заполняется глыбами по 1000. Максимум пятьдесят шесть таких глыб вместо необходимых шестидесяти - противоречие.
Шаг 2. Сначала в десять грузовиков кладём по пять глыб 800 кг и одной 1000 кг. Для оставшихся глыб проверяем число грузовиков с двумя глыбами 1000 и двумя 1500; оставшиеся тысячные укладываем по пять, полуторатонные - по три и при необходимости остаток в отдельный грузовик. Приведённая таблица количества грузовиков и их содержимого соблюдает вместимость и использует весь запас.
T=((10;5;1;0);(15;0;2;2);(4;0;5;0);(10;0;0;3))\mathcal T=\left(\left(10;5;1;0\right);\left(15;0;2;2\right);\left(4;0;5;0\right);\left(10;0;0;3\right)\right)
Шаг 3. Записываем полученный ответ.
3939

Открыть задачу целиком

Попробовать самостоятельно