Расфасовка

[wpoms.]

Для упаковки товара могут быть использованы два вида пакетов, рассчитанные на 11 кг или 12 кг товара. Упаковали партию товара общим весом 5940 кг. Известно, что использовались пакеты по 12 кг, но никто не знает, сколько пакетов каждого вида было использовано. Покажите, что все эти пакеты могут быть разделены на 11 групп равного веса.

@темы: Текстовые задачи, Теория чисел

Comments

[Adjirranirr]

Пусть `u`, `v` — количества пакетов по 11 и по 12 кг. соответственно. Тогда,
`11u + 12v = 5940 = 45*11*12 => 11u = 5940 - 12v \equiv 0 (\text{mod} 12) => u \equiv 0 (\text{mod} 12) => u = 12*n`.

Разделим все пакеты по 11 кг на `n` групп по 132 кг, раскидаем эти группы по 11 мешкам так, чтобы ни в каком из мешков общая масса не превысила 540. Это всегда возможно, если `n <= 44`. Но так как пакеты на 12 кг использовались, то всегда `n <= 44` (если `n = 45`, то `(12n)*11= 5940` и пакетов по 12 кг нет). В каждом из мешков может быть от 0 до 4 групп по 132 кг; при этом, число `540 - 132k = 12*(45 - 11k)` всегда кратно 12 и в каждом мешке недостает `12m` кг до 540. Значит, раскидывая оставшиеся 12 кг пакеты по мешкам, мы получим искомое разбиение.

[Груша Вильямс]

Интересная задачка