Сумма соседних разностей по кругу

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

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

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

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

  1. Расстановка, достигающая нужной суммы
  2. Ответ

    Сначала: Расстановка, достигающая нужной суммы

  3. Чётность суммы

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

  4. Ответ: нет

    Сначала: Чётность суммы

  5. Верхняя граница через максимумы

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

  6. Расстановка, достигающая нужной суммы

    Сначала: Верхняя граница через максимумы

  7. Ответ

    Сначала: Расстановка, достигающая нужной суммы

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

По кругу в некотором порядке расставлены натуральные числа от 1 до 12. Между каждыми двумя соседними числами написали модуль их разности. Затем исходные числа стёрли.

а) Приведите пример расстановки, когда сумма полученных чисел равна 32.

б) Может ли сумма полученных чисел быть равна 29?

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

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

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

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

Шаг 1. Выписываем перестановку чисел и суммируем модули всех соседних разностей, включая последнюю с первой. Для заданной суммы конечный разбор перестановок фиксирует 1 на первом месте и поочерёдно дописывает неиспользованные числа; отбрасываются только префиксы, чья сумма уже превышает требуемую. Для максимума чередуем малые и большие числа, что достигает доказанной верхней границы.
T=(1;2;3;4;5;6;8;10;7;11;9;12)\mathcal T=\left(1;2;3;4;5;6;8;10;7;11;9;12\right)
Шаг 2. Записываем найденное значение.
(1;2;3;4;5;6;8;10;7;11;9;12)\left(1;2;3;4;5;6;8;10;7;11;9;12\right)
Шаг 1. По модулю 2 разность по модулю равна обычной разности. Сумма обычных разностей по замкнутому кругу равна нулю, поэтому сумма модулей всегда чётная.
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. В сумме соседних разностей каждое число получает коэффициент 2 в локальном максимуме, −2-2 в локальном минимуме и 0 в остальных местах. Максимумы и минимумы чередуются, их одинаковое количество k≤⌊N2⌋k\leq\left\lfloor \frac{N}{2}\right\rfloor. Поэтому сумма не больше удвоенной разности суммы kk наибольших и kk наименьших чисел, то есть 2k(N−k)2k(N-k). Это не больше 2⌊N2⌋⌈N2⌉2\left\lfloor \frac{N}{2}\right\rfloor \left\lceil \frac{N}{2}\right\rceil.
Шаг 2. Выписываем перестановку чисел и суммируем модули всех соседних разностей, включая последнюю с первой. Для заданной суммы конечный разбор перестановок фиксирует 1 на первом месте и поочерёдно дописывает неиспользованные числа; отбрасываются только префиксы, чья сумма уже превышает требуемую. Для максимума чередуем малые и большие числа, что достигает доказанной верхней границы.
T=(1;7;2;8;3;9;4;10;5;11;6;12)\mathcal T=\left(1;7;2;8;3;9;4;10;5;11;6;12\right)
Шаг 3. Записываем найденное значение.
7272

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

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