[Перевод] Переворачиваем список целых чисел
Недавно Александр Муньис опубликовал новую математическую игру, которую назвал «Переверни список целых чисел». Заключается она в следующем.
Составьте список разных положительных чисел (например, 10 5 3). Ваша цель — перевернуть список, используя «ходы» двух видов:
Разделите одно из чисел на две части, которые в сумме дают целое; например, (10 5 4) может стать (7 3 5 4) или (10 2 3 4).
Объедините два соседних числа в их сумму; например, (7 3 5 4) может стать (7 8 4) или (7 3 9).
Нельзя образовывать число, которое больше максимального числа в исходном списке. Например, если мы пытаемся изменить (10 5 4), то (7 5 3 4) может стать (7 8 4), но не может стать (12 3 4), так как 12 больше, чем 10 — максимальное число исходного списка. Также все элементы списка должны оставаться различными; например, (7 5 3 4) не может стать ни (7 5 7), ни (7 2 3 3 4).
Александр спрашивает: какие эффективные алгоритмы или общие стратегии существуют для решения этих задач? Для данного n должен быть некий список, где n — самое большое число, а количество ходов, необходимых для решения головоломки, является максимальным. Как выглядит максимальная последовательность необходимого количества ходов в зависимости от n? Как выглядят самые «сложные» головоломки? Есть ли способ определить это без брутфорса?
Пользователь HackerNews под никнеймом Someone удачно описал физическую модель игры. Возьмите палочки длиной от 1 до n. Поместите некоторое их подмножество подряд в «жёлоб для решения», остальное — в «неиспользуемый жёлоб». Теперь варианты следующие: заменить две соседние палочки в «жёлобе для решения» на одну неиспользуемую палочку той же длины из «неиспользуемого жёлоба» или же заменить одну палочку в «жёлобе для решения» любыми двумя палочками из «неиспользуемого жёлоба».
Сумма элементов списка остается постоянной; следовательно, то же самое происходит с суммой недостающих элементов (палочек в «неиспользуемом жёлобе»).
Этот инвариант полезен в некоторых доказательствах, приведённых ниже; в частности, обратите внимание, что невозможно разделить элемент a, если сумма палочек в «неиспользуемом жёлобе» не меньше a.
Если для некого исходного списка сумма неиспользуемых элементов меньше, чем n — 1, то ни n — 1, ни n не могут быть разделены; следовательно, они не могут поменяться местами, а значит, список будет неразрешимым.
В целом кажется целесообразным классифицировать возможные исходные положения по их наибольшему значению n и исходной длине k. Например, в случае с (10 3 5) наибольшее значение равно 10, а длина — 3.
Томаш Рокицки уже провел некоторое исследование и OEIS-тификацию. OEIS A372008 предлагает наихудшее количество ходов, необходимое для решения любого разрешимого списка с наибольшим значением n. Его записи — это максимумы каждой строки треугольника M (n, k), записи которого указывают на наихудшее число ходов для решения любого разрешимого списка с наибольшим значением n и длиной k.
(Записи с суффиксом ? получены от Томаша Рокицки, но не проверялись моим более медленным кодом).
n=1: 0
n=2: 0 -
n=3: 0 - -
n=4: 0 - - -
n=5: 0 - - - -
n=6: 0 6 14 6 - -
n=7: 0 4 12 24 26 - -
n=8: 0 4 14 32 64 74 - -
n=9: 0 4 8 18 66 76 86 - -
n=10: 0 4 8 14 20 88 124 126 36 -
n=11: 0 4 8 12 16 26 90? 100? 106? - -
n=12: 0 4 8 12 16 20? 34? 112? 128? 130? - -
n=13: 0 4 8 10 14
n=14: 0 4 8 12 16
n=15: 0 4 8 10 14
n=16: 0 4 8 12
n=17: 0 4 8 10
n=18: 0 4 8 12
n=19: 0 4 8 10
n=20: 0 4 8Между тем, количество C (n, k) разрешимых списков с наибольшим значением n и длиной k это:
n=1: 1
n=2: 1 0
n=3: 1 0 0
n=4: 1 0 0 0
n=5: 1 0 0 0 0
n=6: 1 8 26 12 0 0
n=7: 1 12 82 294 244 0 0
n=8: 1 14 126 760 2316 1846 0 0
n=9: 1 16 168 1344 8238 31678 47164 0 0
n=10: 1 18 216 2016 15098 89078 336154 480598 2640 0
n=11: 1 20 270 2880 25200 181308 1039174? 3907420? 5673092? 0 0
n=12: 1 22 330 3960 39600 332582? 2323524? 12999906? 47886678? 67645030? 0 0
n=13: 1 24 396 5280 59400 ? ? ? ? ? ? ? 0
n=14: 1 26 468 6864 85800 ? ? ? ? ? ? ? ? 0
n=15: 1 28 546 8736 120120 ? ? ? ? ? ? ? ? 0 0
n=16: 1 30 630 10920 ? ? ? ? ? ? ? ? ? ? 0 0
n=17: 1 32 720 13440 ? ? ? ? ? ? ? ? ? ? ? ? 0
n=18: 1 34 816 16320 ? ? ? ? ? ? ? ? ? ? ? ? ? 0
n=19: 1 36 918 19584 ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0
n=20: 1 38 1026 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0Обратите внимание:
Неизменно, C (n, 1) = 1 и M (n, 1) = 0.
Для n ≥ 2 у нас есть C (n, n) = 0, так как если исходный список содержит все n возможных чисел, законных ходов нет.
Рассмотрим список длиной k = n — 1. Только одно число a < n отсутствует в первоначальном списке; это значит, мы не сможем разделить наибольшее значение n на само себя, лишь манипулировать элементами слева и справа от n. Итак, чтобы список был разрешимым, сумма элементов слева от n должна быть равна сумме элементов справа от n. Таким образом недостающий элемент должен иметь ту же чётность, что и n (n + 1) / 2. Теперь, если n — 1 изначально находится в левой части, нам обязательно нужно разделить его и восстановить в правой части, то есть сумма недостающих чисел должна быть не менее n — 1;, но это невозможно, поскольку лишь a является недостающим элементом. Итак, недостающий элемент a должен быть n — 1, и он должен иметь ту же чётность, что и n (n + 1) / 2, чтобы мы могли разделить остаток поровну между левой и правой частями. Согласно этой логике, C (n, n — 1) заведомо равен нулю для n ∈ {11, 12, 15, 16, 19, 20…}. С другой стороны, он может быть ненулевым, например, C (10, 9) = 2640.
Интуитивно кажется правдоподобным, что ∀k∃m∀n > m: C (n, k) = Total (n, k).
Для n ≥ 7 у нас есть C (n, 2) = Total (n, 2) и M (n, 2) = 4. Доказательство от пользователя SevenNinths смотрите здесь.
Для n ≥ 9 у нас, кажется, есть C (n, 3) = Total (n, 3) и M (n, 3) = 8.
Для n ≥ 9 у нас, кажется, есть C (n, 4) = Total (n, 4);, но пока M (n, 4) колеблется между 10 и 12. Будет ли оно стабилизироваться до 12 (предполагая, что ∀k∃m∀n > m: M (n, k) = 4(k — 1)), или здесь происходит что-то более сложное?
Пользователь SevenNinths приводит конструктивное доказательство того, что ∀n ≥ 7: M (n, 2) = 4, в виде безупречного алгоритма, позволяющего перевернуть любой двухэлементный список с n ≥ 7. Интуитивно можно предположить, что надежный алгоритм должен существовать также для списков из 3, 4 и более элементов. Обратите внимание, что алгоритм SevenNinths сохраняет длину всех промежуточных списков равной 4 или меньше, даже для очень больших n. Опять же, интуитивно из этого следует, что должна существовать достаточная длина L (n, k) < n для того, чтобы каждый разрешимый список с наибольшим значением n и исходной длиной k мог быть разрешён без создания списка длиннее чем L (n, k). Предположение для L (n, k) может значительно ускорить решение брутфорсом за счёт сокращения пространства поиска.
Достаточной длиной промежуточного списка L (n, k) для разрешаемых списков с наибольшим значением n и длиной k, является:
n=1: 1
n=2: 1 -
n=3: 1 - -
n=4: 1 - - -
n=5: 1 - - - -
n=6: 1 4 4 4 - -
n=7: 1 4 5 5 5 - -
n=8: 1 4 5 6 7 7 - -
n=9: 1 4 5 7 7 8 8 - -
n=10: 1 4 5 7 8 9 9 9 9 -
n=11: 1 4 5 7 8 9 ? ? ? - -
n=12: 1 4 5 6 8 ? ? ? ? ? - -
n=13: 1 4 5 7 8 ? ? ? ? ? ? ? -
n=14: 1 4 5 6 7 ? ? ? ? ? ? ? ? -
n=15: 1 4 5 7 8 ? ? ? ? ? ? ? ? - -
n=16: 1 4 5 6 ? ? ? ? ? ? ? ? ? ? - -
n=17: 1 4 5 7 ? ? ? ? ? ? ? ? ? ? ? ? -
n=18: 1 4 5 6 ? ? ? ? ? ? ? ? ? ? ? ? ? -
n=19: 1 4 5 7 ? ? ? ? ? ? ? ? ? ? ? ? ? - -
n=20: 1 4 5 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? - -Код C++17, на котором созданы таблицы, доступен здесь.
