Груз массой 36 т упакован в невесомые ящики. Масса груза в каждом ящике не превышает 1 т. Какое наименьшее количество четырехтонных грузовиков понадобится, чтобы наверняка можно было увезти этот груз (грузовики запрещается перегружать!)?

задан 14 Апр '14 14:29

@nynko: задача состоит в том, чтобы найти наименьшее возможное количество грузовиков одинаковой вместимости (4 тонны), учитывая, что вес каждого ящика меньше тонны, нам для этого надо найти наименьшее количество ящиков, то есть, чтобы вес каждого ящика стремился к тонне, но не достигал его (если уж чисто математически). А почему ящики по 501 кг, можно только по три в четырехтонный грузовик, их можно будет аж семь штук (всего 3507 кг) туда загрузить.

(14 Апр '14 16:29) kirill1771
10|600 символов нужно символов осталось
3

Новое решение
1) (Более простой случай) Пусть у всех, кроме одного ящика, одна масса и она равна $%k$%, где $%k \in (0;1)$%, будем рассматривать самый неудобный "плохой" случай, когда в каждом грузовике после погрузки остается как можно больше места, то есть нам надо найти максимальное значение $%4-4k$%, но при этом это количество места должно быть меньше веса одного ящика (чтобы его нельзя было еще загрузить), то есть $%4-4k < k \Leftrightarrow k> 0,8$%, возьмем пока не самое "плохое" значение (а оно равно $%8,00...01$%), но чтобы оно было близко к нему, например $%0,81$%, тогда всего будет $%45$% ящиков - $%44$% с весом по $%0,81$% и $%1$% с весом $%0,36$%; после погрузки в каждом грузовике будет находится по $%3,24$% тонны веса, тогда понадобится $%12$% грузовиков для погрузки.
Теперь следует заметить, что при уменьшении веса одного ящика на $%9\cdot10^{-3n}$% тонны, где $%n \in N$%, вес в каждом грузовике будет уменьшаться на $%4\cdot9\cdot10^{-3n}=36\cdot10^{-3n}$%, а количество грузовиков (после загрузки грузов одинаковой массы) будет равно, если мы поделим $%36$% на $%3,23+36\cdot10^{-3n}$% и округлим в меньшую сторону, $%36/3,23=11,1455...$%, а $%3,23+36\cdot10^{-3n}$% стремится к этому значению (но не достигает), заметим, что после погрузки $%11$% грузовиков остается еще $%36-11\cdot3,24=0,36$% тонны груза, а в каждом грузовике есть еще по $%4-3,24=0,676$% свободного места, поэтому для оставшегося веса не надо будет брать новый грузовик, а поместить его в любой из этих. А если вес будет стремиться к $%3,23$%, то всободное место (в каждом грузовике) будет стремиться к $%4-3,23=0,677$%, а вес груза, оставшегося без грузовиков - к $%0,47$%, поэтому его в этом случае $%11$% грузовиков хватит.

Если рассматривать случай, когда вес каждого ящика будет произвольным, то минимум то самая "плохая" ситуация будет, когда в один грузовик будет загружен $%3,00...011$% тогда после загрузки $%11$% грузовиков останется $%36-33,00...033=2,00...067<3$%, а этот вес можно будет распределить в остальные грузовики, так как в каждом было по $%3,00...011$%, то его в нем были грузы с весами $%1;1;0,5;0,500...011$% (например) - здесь важно именно последние два груза, вместе они чуть больше единицы, а по отдельности (если рассмотреть все возможные варианты их весов), то один из них в любом случае будет меньше или равен $%0,5$% (хотя на самом деле, главное - их сумма, чуть больше одной тонны), поэтому, если оставшийся вес распределить "худшим" способом, например, на три груза по $%1;1;0,00...067$%, то в каждом заполненном грузовике можно заменить грузы, которые будут в сумме чуть больше $%1$% на грузы весом $%1$% (тогда этот грузовик полностью заполнится), эти "вытеснянные" гурзы весом чуть болье $%1$%, поместим в другой грузовик №1 вместо одной единицы, потом из еще одного грузовика №2 возьмем такие же два груза и поменяем их местами с оставшимся грузом весом в тонну в грузовике №1, тогда в нем будут шесть грузов в сумме дающих чуть больше $%3$% тонн (но не достигающих $%3,1$% тонны), и мы в него сможем поместить груз весом $%00...067$% (даже если бы мы в начале оставшейся вес распрелилили на три груза приблизительно поровну, то предыдущие два все равно бы заменили два груза, дававшие в сумме чуть больше $%1$%, так как вес каждого их них был бы чуть меньше $%0,7$% и наш третий груз "вошел бы" в этот грузовик), а оставшиеся два груза весом в тонну (каждый) грузим в грузовик №2, который полностью заполняется, таким образом при наихудшей ситуации можно все грузы уместить в $%11$% грузовиков.

ссылка

отвечен 14 Апр '14 15:33

изменен 15 Апр '14 12:20

@kirill: десяти машин может не хватить. Пусть имеется 44 одинаковых груза каждый весом в 9/11 тонны. Тогда вес пяти грузов превышает 4 тонны, и на одну машину войдёт не более 4 грузов. Итого потребуется 11 машин.

Рассмотрение 37 ящиков -- это частный случай. К тому же грузы могут иметь разные веса, то есть общая ситуация выглядит сложнее.

(15 Апр '14 1:19) falcao

@falcao: спасибо, я немного условие недопонял, сейчас перепишу.

(15 Апр '14 2:13) kirill1771

@student, @falcao: я исправил решение.

(15 Апр '14 2:13) kirill1771

@kirill1771: я правильно понимаю, что Ваш ответ к этой задаче -- это 12 грузовиков? Если да, то нужно две вещи. Первая: обосновать, что 12 точно хватит при любом распределении весов. Рассмотрения частных случаев здесь недостаточно, а понятия "лучших" и "худших" случаев не определены достаточно строго. Но это простая часть. Главное (если ответ 12 верен) -- это доказать, что 11 машин не всегда хватает. Здесь уже достаточно одного конкретного примера. Мой пример с 9/11 показывает, что 10 машин недостаточно, но его надо усилить.

(15 Апр '14 12:06) falcao

@falcao: я вчера когда дописывал, то не учел одного, что когда вес остается, его можно распределить в остальные грузовики (какой бы конфигурации не были грузы), поэтому я еще раз исправил ответ, получается $%11$%.

(15 Апр '14 12:12) kirill1771

@kirill1771: если ответ 11, то возникает та проблема, на которую я указывал выше. Здесь надо рассматривать все случаи, ничего не упуская. Поэтому рассуждения для части случаев (пусть и достаточно "разумно" отобранных) не будет считаться полным. Скажем, первая же фраза, когда у всех грузов кроме одного вес одинаков, уже сужает число вариантов. Тут проблема в том, что мы заранее не имеем представления, какой же именно случай на деле будут "самый плохой".

(15 Апр '14 14:10) falcao

@falcao: да, первый случай можно вообще из ответа убрать, он ничего не дает. А разве, самым плохим не будет случай, когда после загрузки $%n$% (11 в моем ответе) грузовиков, остается как можно больший вес груза (якобы на двенадцатый грузовик)?

(15 Апр '14 14:20) kirill1771

@kirill1771: я в итоге разобрался с этой задачей -- мне она показалась не слишком простой. Там надо было догадаться до некоторого промежуточного утверждения, которое доказывается несложно, но только после того, как оно сформулировано. Стало также ясно, каков будет ответ для общего случая.

В Вашем рассуждении делаются предположения, которые ниоткуда не следуют. Например, почему самая "плохая" ситуация будет при x=3,00...011? Это непонятно. Почему не 3,14, к примеру? Ответ 11 верен, но требуется аккуратное доказательство, с полным обоснованием.

(16 Апр '14 0:11) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
3

Загружаем машину, последний ящик который не помещается, оставляем возле машины. И так четыре раза. Четыре оставшихся ящика грузим на ещё одну машину $%(4\cdot1=4\text{ } т)$%. Аналогично грузим ещё пять машин.

Груза останется не более $%36-8\cdot4=4$% т, которые увезёт одиннадцатая машина.

ссылка

отвечен 3 Фев '15 0:56

10|600 символов нужно символов осталось
1

Изложу своё решение, найденное сегодня.

Достаточно легко показать, что 12 грузовиков хватает, и несложно привести пример, когда 10 машин мало. После этого возникает вопрос, в какую сторону надо рассуждать? Усиливать доказательство для 12, снижая оценку до 11, или совершенствовать контрпример, из которого бы следовало, что и 11 грузовиков мало? Сразу это не было ясно. Но в итоге выяснилось, что правильным является первый путь. Докажем такую лемму.

Лемма. Пусть даны положительные числа, каждое из которых не больше 1. Предположим, что их сумма больше 3,2. Тогда из этих чисел можно выделить часть, которая в сумме даёт значение больше 3,2, но не больше 4.

Прежде чем доказывать лемму, выведем из неё тот факт, что 11 грузовиков хватает. Пока у нас остаётся более 3,2 тонн не вывезенного материала, применяем лемму, и выделяем часть камней весом более 3,2, которая при этом помещается на грузовик. Тогда на 10 грузовиках мы сможем вывезти более 32 тонн. У нас останется не более 4 тонн, которые поместятся на последний, 11-й грузовик.

Итак, осталось доказать лемму. Будем проводить индукцию по количеству слагаемых. Я буду использовать такую схему, при котором утверждение доказывается для $%n$% слагаемых, в предположении, что оно верно для любого количества слагаемых, меньшего $%n$%. Рассмотрение базы индукции при этом не требуется.

Заметим, что слагаемых у нас как минимум 4, так как сумма трёх чисел не больше 3, а у нас она по условию больше 3,2. Рассмотрим несколько случаев, которые всё исчерпывают.

1) Каждое из чисел больше 0,8. Этот случай лёгкий, потому что тогда мы берём произвольные 4 числа. Их сумма больше 3,2, и при этом не превосходит 4.

2) Сумма чисел не больше 4. Этот случай тоже лёгкий, так как здесь мы берём все числа.

3) Сумма чисел больше 4, и имеется слагаемое, не превосходящее 0,8. Это то, что нам осталось рассмотреть. Здесь мы рассматриваем сумму без учёта упомянутого слагаемого. Она больше 3,2, и слагаемых в ней меньше, чем было. Значит, по индукционному предположению из этих чисел можно набрать требуемую сумму.

Лемма доказана. Роль числа 0,8 как "критического" здесь можно объяснить так. Если его слегка уменьшить, то на одну машину поместится 5 камней. При этом вывезти удастся много. Если чуть увеличить, то 4 камня дадут вместе 3,2, и тогда сработает описанное выше решение с вывозом 32 тонн на 10 грузовиках.

Можно показать, что для случая $%n$% грузовиков, максимальный суммарный вес, который заведомо можно на них вывезти, составляет 0,8+3,2n. При n=11 получается ровно 36. Если суммарный вес хотя бы чуть-чуть превышает 36 тонн, то для такого веса можно построить пример, показывающий, что 11 грузовиков мало. Выглядит он так: рассматриваем 45 камней одинакового веса, чуть превышающего 0,8. На один грузовик помещается не более 4 таких камней, и 11 грузовиков не хватит. Общий сформулированный факт доказывается на основании леммы.

ссылка

отвечен 16 Апр '14 0:44

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×59

задан
14 Апр '14 14:29

показан
3825 раз

обновлен
3 Фев '15 0:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru