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

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

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

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

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

  1. Масса выбранной группы
  2. Заданная разность

    Сначала: Масса выбранной группы

  3. Ответ: да

    Сначала: Заданная разность

  4. Масса выбранной группы

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

  5. Заданная разность

    Сначала: Масса выбранной группы

  6. Ответ: нет

    Сначала: Заданная разность

  7. Масса выбранной группы

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

  8. Наименьшая положительная разность

    Сначала: Масса выбранной группы

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

    Сначала: Наименьшая положительная разность

  10. Ответ

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

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

Есть 4 камня, каждый массой 7 тонн, и 9 камней, каждый массой 22 тонны.

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

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

в) Все камни хотят разложить на две группы. Какое наименьшее положительное значение (в тоннах) может принимать разность суммарных масс камней в этих группах?

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

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

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

Шаг 1. Если в первую группу попали xx камней массы aa и yy камней массы bb, её масса W=ax+byW=ax+by, а масса второй S−WS-W. Разность масс равна ∣2W−S∣|2W-S|. Диапазоны 0≤x≤m0\leq x\leq m, 0≤y≤n0\leq y\leq n конечны и охватывают все разбиения; пустые группы исключаем.
S=226S=226
Шаг 2. Решаем два линейных равенства 2ax+2by=S±D2ax+2by=S\pm D в целых границах количеств камней. Таблица содержит все подходящие пары xx, yy; они задают явное разбиение. Пустой список означает невозможность.
D=8D=8
T=((1;5);(3;4))\mathcal T=\left(\left(1;5\right);\left(3;4\right)\right)
Шаг 3. Да. Указанная конструкция удовлетворяет всем условиям.
Шаг 1. Если в первую группу попали xx камней массы aa и yy камней массы bb, её масса W=ax+byW=ax+by, а масса второй S−WS-W. Разность масс равна ∣2W−S∣|2W-S|. Диапазоны 0≤x≤m0\leq x\leq m, 0≤y≤n0\leq y\leq n конечны и охватывают все разбиения; пустые группы исключаем.
S=226S=226
Шаг 2. Решаем два линейных равенства 2ax+2by=S±D2ax+2by=S\pm D в целых границах количеств камней. Таблица содержит все подходящие пары xx, yy; они задают явное разбиение. Пустой список означает невозможность.
D=0D=0
T={}\mathcal T=\left\{\right\}
Шаг 3. Нет. Необходимое ограничение или полный конечный список исключает такой случай.
Шаг 1. Если в первую группу попали xx камней массы aa и yy камней массы bb, её масса W=ax+byW=ax+by, а масса второй S−WS-W. Разность масс равна ∣2W−S∣|2W-S|. Диапазоны 0≤x≤m0\leq x\leq m, 0≤y≤n0\leq y\leq n конечны и охватывают все разбиения; пустые группы исключаем.
S=226S=226
Шаг 2. При фиксированном xx разность минимальна для одного из ближайших целых yy к S2−axb\frac{\frac{S}{2}-ax}{b}. Учитываем границы yy и исключаем нулевую разность. Для каждого xx достаточно ближайших целых и их соседей; таблица содержит минимальную положительную разность в каждой строке. Наименьшая строка даёт ответ и конструкцию.
T=((0;5;6);(1;5;8);(2;4;22);(3;4;8);(4;4;6))\mathcal T=\left(\left(0;5;6\right);\left(1;5;8\right);\left(2;4;22\right);\left(3;4;8\right);\left(4;4;6\right)\right)
Шаг 3. В таблицах приведены количества, значения или исходные числа, которые непосредственно реализуют найденное распределение. Проверяем соответствующую сумму.
X1=((7;0);(22;5))X_1=\left(\left(7;0\right);\left(22;5\right)\right)
X2=((7;4);(22;4))X_2=\left(\left(7;4\right);\left(22;4\right)\right)
Шаг 4. Записываем найденное значение, достигаемое приведённым вариантом.
66

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

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