Разбиение камней на три группы

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

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

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

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

  1. Все распределения трёх типов камней
  2. Требуемое соотношение масс

    Сначала: Все распределения трёх типов камней

  3. Ответ: нет

    Сначала: Требуемое соотношение масс

  4. Все распределения трёх типов камней

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

  5. Требуемое соотношение масс

    Сначала: Все распределения трёх типов камней

  6. Конструкция

    Сначала: Требуемое соотношение масс

  7. Ответ: да

    Сначала: Конструкция

  8. Все распределения трёх типов камней

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

  9. Два соседних разрыва

    Сначала: Все распределения трёх типов камней

  10. Конструкция

    Сначала: Два соседних разрыва

  11. Ответ

    Сначала: Конструкция

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

Есть 4 камня, каждый массой 100 тонн, 5 камней, каждый массой 25 тонн, и 6 камней, каждый массой 4 тонны.

а) Можно ли разложить все эти камни на три группы так, чтобы суммарные массы этих групп были равны?

б) Можно ли разложить все эти камни на три группы так, чтобы суммарная масса первой группы была на 50 тонн больше суммарной массы второй группы, но на 50 тонн меньше суммарной массы третьей группы?

в) Все камни хотят разложить на три группы с суммарными массами m1,m2m_1,m_2 и m3m_3 так, что m1≥m2≥m3m_1\ge m_2\ge m_3. Найдите такое наименьшее число dd, что m1−m2≤dm_1-m_2\le d и m2−m3≤dm_2-m_3\le d.

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

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

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

Шаг 1. Для каждого типа с mm камнями в первые две группы можно положить xx, yy камней, где xx, y≥0y\geq 0 и x+y≤mx+y\leq m; в третьей останется m−x−ym-x-y. Перемножение трёх конечных списков даёт все разбиения. Массы групп непосредственно вычисляются по этим девяти количествам.
S=549S=549
Шаг 2. Из общей массы находим требуемые три массы для равенства или заданной разности соседних групп. Если они нецелые, разбиение невозможно. Иначе проверяем их по полному списку распределений; найденные количества дают конструкцию.
X1=(183;183;183)X_1=\left(183;183;183\right)
Шаг 3. Нет. Необходимое ограничение или полный конечный список исключает такой случай.
Шаг 1. Для каждого типа с mm камнями в первые две группы можно положить xx, yy камней, где xx, y≥0y\geq 0 и x+y≤mx+y\leq m; в третьей останется m−x−ym-x-y. Перемножение трёх конечных списков даёт все разбиения. Массы групп непосредственно вычисляются по этим девяти количествам.
S=549S=549
Шаг 2. Из общей массы находим требуемые три массы для равенства или заданной разности соседних групп. Если они нецелые, разбиение невозможно. Иначе проверяем их по полному списку распределений; найденные количества дают конструкцию.
X1=(183;133;233)X_1=\left(183;133;233\right)
Шаг 3. В таблицах приведены количества, значения или исходные числа, которые непосредственно реализуют найденное распределение. Проверяем соответствующую сумму.
T=((1;1;2);(3;1;1);(2;2;2))\mathcal T=\left(\left(1;1;2\right);\left(3;1;1\right);\left(2;2;2\right)\right)
Шаг 4. Да. Указанная конструкция удовлетворяет всем условиям.
Шаг 1. Для каждого типа с mm камнями в первые две группы можно положить xx, yy камней, где xx, y≥0y\geq 0 и x+y≤mx+y\leq m; в третьей останется m−x−ym-x-y. Перемножение трёх конечных списков даёт все разбиения. Массы групп непосредственно вычисляются по этим девяти количествам.
Шаг 2. Упорядочиваем массы трёх групп и вычисляем больший из двух соседних разрывов. В таблице для каждого распределения камней первого типа указан минимальный результат по всем распределениям двух других типов. Это исчерпывает все случаи; общий минимум достигается приведёнными девятью количествами.
T=(((0;0;4);255);((0;1;3);117);((0;2;2);51);((0;3;1);117);((0;4;0);255);((1;0;3);117);((1;1;2);17);((1;2;1);17);((1;3;0);117);((2;0;2);51);((2;1;1);17);((2;2;0);51);((3;0;1);117);((3;1;0);117);((4;0;0);255))\mathcal T=\left(\left(\left(0;0;4\right);255\right);\left(\left(0;1;3\right);117\right);\left(\left(0;2;2\right);51\right);\left(\left(0;3;1\right);117\right);\left(\left(0;4;0\right);255\right);\left(\left(1;0;3\right);117\right);\left(\left(1;1;2\right);17\right);\left(\left(1;2;1\right);17\right);\left(\left(1;3;0\right);117\right);\left(\left(2;0;2\right);51\right);\left(\left(2;1;1\right);17\right);\left(\left(2;2;0\right);51\right);\left(\left(3;0;1\right);117\right);\left(\left(3;1;0\right);117\right);\left(\left(4;0;0\right);255\right)\right)
Шаг 3. В таблицах приведены количества, значения или исходные числа, которые непосредственно реализуют найденное распределение. Проверяем соответствующую сумму.
X1=((1;1;2);(2;3;0);(4;2;0))X_1=\left(\left(1;1;2\right);\left(2;3;0\right);\left(4;2;0\right)\right)
X2=(166;183;200)X_2=\left(166;183;200\right)
Шаг 4. Записываем найденное значение, достигаемое приведённым вариантом.
1717

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

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