Есть 4 камня, каждый массой 100 тонн, 5 камней, каждый массой 25 тонн, и 6 камней, каждый массой 4 тонны.
а) Можно ли разложить все эти камни на три группы так, чтобы суммарные массы этих групп были равны?
б) Можно ли разложить все эти камни на три группы так, чтобы суммарная масса первой группы была на 50 тонн больше суммарной массы второй группы, но на 50 тонн меньше суммарной массы третьей группы?
в) Все камни хотят разложить на три группы с суммарными массами m1,m2 и m3 так, что m1≥m2≥m3. Найдите такое наименьшее число d, что m1−m2≤d и m2−m3≤d.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Для каждого типа с m камнями в первые две группы можно положить x, y камней, где x, y≥0 и x+y≤m; в третьей останется m−x−y. Перемножение трёх конечных списков даёт все разбиения. Массы групп непосредственно вычисляются по этим девяти количествам.
S=549
Шаг 2. Из общей массы находим требуемые три массы для равенства или заданной разности соседних групп. Если они нецелые, разбиение невозможно. Иначе проверяем их по полному списку распределений; найденные количества дают конструкцию.
X1=(183;183;183)
Шаг 3. Нет. Необходимое ограничение или полный конечный список исключает такой случай.
Шаг 1. Для каждого типа с m камнями в первые две группы можно положить x, y камней, где x, y≥0 и x+y≤m; в третьей останется m−x−y. Перемножение трёх конечных списков даёт все разбиения. Массы групп непосредственно вычисляются по этим девяти количествам.
S=549
Шаг 2. Из общей массы находим требуемые три массы для равенства или заданной разности соседних групп. Если они нецелые, разбиение невозможно. Иначе проверяем их по полному списку распределений; найденные количества дают конструкцию.
X1=(183;133;233)
Шаг 3. В таблицах приведены количества, значения или исходные числа, которые непосредственно реализуют найденное распределение. Проверяем соответствующую сумму.
T=((1;1;2);(3;1;1);(2;2;2))
Шаг 4. Да. Указанная конструкция удовлетворяет всем условиям.
Шаг 1. Для каждого типа с m камнями в первые две группы можно положить x, y камней, где x, y≥0 и x+y≤m; в третьей останется m−x−y. Перемножение трёх конечных списков даёт все разбиения. Массы групп непосредственно вычисляются по этим девяти количествам.
Шаг 2. Упорядочиваем массы трёх групп и вычисляем больший из двух соседних разрывов. В таблице для каждого распределения камней первого типа указан минимальный результат по всем распределениям двух других типов. Это исчерпывает все случаи; общий минимум достигается приведёнными девятью количествами.
Шаг 3. В таблицах приведены количества, значения или исходные числа, которые непосредственно реализуют найденное распределение. Проверяем соответствующую сумму.