Переворачиваем список целых чисел

Недавно Александр Муньис опубликовал новую математическую игру, которую назвал «Переверни список целых чисел». Заключается она в следующем.

• Составьте список разных положительных чисел (например, 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

Обратите внимание:

• Общее количество списков (разрешимых или нет) с наибольшим значением n и длиной k составляет

• Неизменно, 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, на котором созданы таблицы, доступен здесь.