По кругу в некотором порядке расставлены натуральные числа от 1 до 12. Между каждыми двумя соседними числами написали модуль их разности. Затем исходные числа стёрли.
а) Приведите пример расстановки, когда сумма полученных чисел равна 32.
б) Может ли сумма полученных чисел быть равна 29?
в) Какое наибольшее значение может принимать сумма полученных чисел?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Выписываем перестановку чисел и суммируем модули всех соседних разностей, включая последнюю с первой. Для заданной суммы конечный разбор перестановок фиксирует 1 на первом месте и поочерёдно дописывает неиспользованные числа; отбрасываются только префиксы, чья сумма уже превышает требуемую. Для максимума чередуем малые и большие числа, что достигает доказанной верхней границы.
T=(1;2;3;4;5;6;8;10;7;11;9;12)
Шаг 2. Записываем найденное значение.
(1;2;3;4;5;6;8;10;7;11;9;12)
Шаг 1. По модулю 2 разность по модулю равна обычной разности. Сумма обычных разностей по замкнутому кругу равна нулю, поэтому сумма модулей всегда чётная.
Шаг 2. Нет. Доказанная необходимая граница исключает возможность.
Шаг 1. В сумме соседних разностей каждое число получает коэффициент 2 в локальном максимуме, −2 в локальном минимуме и 0 в остальных местах. Максимумы и минимумы чередуются, их одинаковое количество k≤⌊2N⌋. Поэтому сумма не больше удвоенной разности суммы k наибольших и k наименьших чисел, то есть 2k(N−k). Это не больше 2⌊2N⌋⌈2N⌉.
Шаг 2. Выписываем перестановку чисел и суммируем модули всех соседних разностей, включая последнюю с первой. Для заданной суммы конечный разбор перестановок фиксирует 1 на первом месте и поочерёдно дописывает неиспользованные числа; отбрасываются только префиксы, чья сумма уже превышает требуемую. Для максимума чередуем малые и большие числа, что достигает доказанной верхней границы.