Разбиение на равные суммы

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

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

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

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

  1. Равные суммы последовательного блока
  2. Конструкция и точный результат

    Сначала: Равные суммы последовательного блока

  3. Ответ: да

    Сначала: Конструкция и точный результат

  4. Наибольшая степень больше суммы остальных

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

  5. Ответ: нет

    Сначала: Наибольшая степень больше суммы остальных

  6. Все четырёхэлементные подмножества

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

  7. Конструкция и точный результат

    Сначала: Все четырёхэлементные подмножества

  8. Ответ

    Сначала: Конструкция и точный результат

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

Множество чисел назовём хорошим, если его можно разбить на два подмножества с одинаковой суммой чисел.

а) Является ли множество {200; 201; 202; ...; 299} хорошим?

б) Является ли множество {2; 4; 8; ...; 21002^{100}} хорошим?

в) Сколько хороших четырёхэлементных подмножеств у множества {1; 2; 4; 5; 7; 9; 11}?

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

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

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

Шаг 1. Попарно соединяем наименьшее с наибольшим, следующее со следующим с конца и так далее. Все пары имеют одинаковую сумму. Если количество пар чётно, половину пар отдаём в каждую группу - суммы равны.
Шаг 2. Приводим полученный набор, параметры или распределение.
T=(((200;299);(201;298);(202;297);(203;296);(204;295);(205;294);(206;293);(207;292);(208;291);(209;290);(210;289);(211;288);(212;287);(213;286);(214;285);(215;284);(216;283);(217;282);(218;281);(219;280);(220;279);(221;278);(222;277);(223;276);(224;275));((225;274);(226;273);(227;272);(228;271);(229;270);(230;269);(231;268);(232;267);(233;266);(234;265);(235;264);(236;263);(237;262);(238;261);(239;260);(240;259);(241;258);(242;257);(243;256);(244;255);(245;254);(246;253);(247;252);(248;251);(249;250)))\mathcal T=\left(\left(\left(200;299\right);\left(201;298\right);\left(202;297\right);\left(203;296\right);\left(204;295\right);\left(205;294\right);\left(206;293\right);\left(207;292\right);\left(208;291\right);\left(209;290\right);\left(210;289\right);\left(211;288\right);\left(212;287\right);\left(213;286\right);\left(214;285\right);\left(215;284\right);\left(216;283\right);\left(217;282\right);\left(218;281\right);\left(219;280\right);\left(220;279\right);\left(221;278\right);\left(222;277\right);\left(223;276\right);\left(224;275\right)\right);\left(\left(225;274\right);\left(226;273\right);\left(227;272\right);\left(228;271\right);\left(229;270\right);\left(230;269\right);\left(231;268\right);\left(232;267\right);\left(233;266\right);\left(234;265\right);\left(235;264\right);\left(236;263\right);\left(237;262\right);\left(238;261\right);\left(239;260\right);\left(240;259\right);\left(241;258\right);\left(242;257\right);\left(243;256\right);\left(244;255\right);\left(245;254\right);\left(246;253\right);\left(247;252\right);\left(248;251\right);\left(249;250\right)\right)\right)
Шаг 3. Да. Приведённая конструкция выполняет все условия.
Шаг 1. Сумма степеней двойки от первой до предпоследней равна наибольшей степени минус два. Поэтому группа с наибольшим числом тяжелее любой группы из остальных, и равное разбиение невозможно.
n=100n=100
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. Выбираем все сочетания четырёх чисел из данного конечного множества. Если общая сумма нечётна, равное разбиение невозможно. Иначе проверяем все поднаборы этих четырёх чисел на половину суммы. Для каждого подходящего четырёхэлементного множества приводим одно разбиение; каждый набор учитывается только один раз.
Шаг 2. Приводим полученный набор, параметры или распределение.
T=(((1;2;4;5);(2;4);(1;5));((1;2;4;7);(1;2;4);(7));((1;5;7;11);(5;7);(1;11));((2;4;5;7);(4;5);(2;7));((2;4;5;11);(2;4;5);(11));((2;4;7;9);(4;7);(2;9));((2;4;9;11);(4;9);(2;11));((5;7;9;11);(7;9);(5;11)))\mathcal T=\left(\left(\left(1;2;4;5\right);\left(2;4\right);\left(1;5\right)\right);\left(\left(1;2;4;7\right);\left(1;2;4\right);\left(7\right)\right);\left(\left(1;5;7;11\right);\left(5;7\right);\left(1;11\right)\right);\left(\left(2;4;5;7\right);\left(4;5\right);\left(2;7\right)\right);\left(\left(2;4;5;11\right);\left(2;4;5\right);\left(11\right)\right);\left(\left(2;4;7;9\right);\left(4;7\right);\left(2;9\right)\right);\left(\left(2;4;9;11\right);\left(4;9\right);\left(2;11\right)\right);\left(\left(5;7;9;11\right);\left(7;9\right);\left(5;11\right)\right)\right)
Шаг 3. Записываем полученный ответ.
88

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

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