Сумма попарных различий групп

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

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

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

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

  1. Граница суммы различий
  2. Ответ: нет

    Сначала: Граница суммы различий

  3. Граница суммы различий

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

  4. Ответ: нет

    Сначала: Граница суммы различий

  5. Граница суммы различий

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

  6. Разбиение с соседними суммами

    Сначала: Граница суммы различий

  7. Ответ

    Сначала: Разбиение с соседними суммами

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

Натуральные числа от 1 до 12 разбивают на четыре группы, в каждой из которых есть по крайней мере два числа. Для каждой группы находят сумму чисел этой группы. Для каждой пары групп находят модуль разности найденных сумм и полученные 6 чисел складывают.

а) Может ли в результате получиться 0?

б) Может ли в результате получиться 1?

в) Каково наименьшее возможное значение полученного результата?

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

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

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

Шаг 1. Нулевой результат требует четырёх одинаковых целых сумм групп, что невозможно, когда общая сумма не делится на четыре. Сумма шести попарных модулей по модулю два равна трём общим суммам, то есть чётна при чётной общей сумме. Поэтому единица исключается. Если крайние суммы различаются хотя бы на два, сумма всех модулей не меньше трёх разностей крайних, то есть хотя бы шесть. Иначе суммы различаются максимум на один; при общей сумме с остатком два  mod 4\bmod 4 их ровно две меньших и две больших, и результат равен четырём.
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. Нулевой результат требует четырёх одинаковых целых сумм групп, что невозможно, когда общая сумма не делится на четыре. Сумма шести попарных модулей по модулю два равна трём общим суммам, то есть чётна при чётной общей сумме. Поэтому единица исключается. Если крайние суммы различаются хотя бы на два, сумма всех модулей не меньше трёх разностей крайних, то есть хотя бы шесть. Иначе суммы различаются максимум на один; при общей сумме с остатком два  mod 4\bmod 4 их ровно две меньших и две больших, и результат равен четырём.
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. Нулевой результат требует четырёх одинаковых целых сумм групп, что невозможно, когда общая сумма не делится на четыре. Сумма шести попарных модулей по модулю два равна трём общим суммам, то есть чётна при чётной общей сумме. Поэтому единица исключается. Если крайние суммы различаются хотя бы на два, сумма всех модулей не меньше трёх разностей крайних, то есть хотя бы шесть. Иначе суммы различаются максимум на один; при общей сумме с остатком два  mod 4\bmod 4 их ровно две меньших и две больших, и результат равен четырём.
Шаг 2. Берём две группы с суммой ⌊T4⌋\left\lfloor \frac{T}{4}\right\rfloor и две с суммой ⌊T4⌋+1\left\lfloor \frac{T}{4}\right\rfloor +1. Для каждого целевого значения перебираем подмножества ещё свободных чисел из полного исходного конечного набора, оставляя не меньше двух элементов в каждой группе. Приведённое разбиение использует все числа ровно один раз и достигает нижней границы.
T=((1;3;4;5;6);(2;7;10);(9;11);(8;12))\mathcal T=\left(\left(1;3;4;5;6\right);\left(2;7;10\right);\left(9;11\right);\left(8;12\right)\right)
Шаг 3. Записываем полученный ответ.
44

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

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