Сколько цифр могут равняться разности своих соседей?

[wrest]

mihaild в сообщении #1732719 писал(а):

Второе число - время работы.

Круто. Но и у меня допилилось до примерно этих показателей +/- платформа (планшет все-таки)

СТРОГО ДОКАЗАНО: G(22) = 14
Верхняя грань доказана: k = 15 -> UNSATISFIABLE
=======================================================
Перестановка : [10, 6, 16, 22, 14, 8, 5, 13, 18, 11, 7, 4, 3, 9, 12, 21, 20, 1, 19, 17, 2, 15, 0]
Хороших точек: 14
Валидность   : ОК

        === task stats ===
        User time   : 500.05s
        Real time   : 507.21s
        System time : 3.14s
        CPU         : 99%
        Memory RSS  : 53784KB
        Exit status : 0
        === end stats ===
~/py-scripts $

Ну и тут мы уже видим разнообразие решений: наши решения для n=22 не совпадают и несимметричны.

[waxtep]

Такое еще соображение, недоказанное и незапрограммированное и, возможно, тривиальное:

1. Для любого $n$ существует хотя бы одна оптимальная последовательность, где два или более "нехороших" числа подряд если и встречаются, то только с краю (не доказано; все пока найденные - таковы);

2. Т.о. не надо перебирать все возможные перестановки, а достаточно перебрать все возможные варианты сочленения последовательностей, каждая из к-рых состоит сплошь из хороших чисел, кроме двух крайних, а сочленение производится по общей крайней точке (не запрограммировано, тут надо уже культурно, а не тяп-ляп);

3. Кажется, это должно быть довольно быстро: всего последовательностей, содержащих хотя бы одну хорошую точку, где-то в районе $\frac{n(n-1)}{2}$, и выбор каждой следующей последовательности существенно уменьшает количество оставшихся вариантов.

Для исходной задачи $n=9$ работает (правда, без доказательства, только нахождение) даже жадный алгоритм: берем одну из самых длинных хороших цепочек 9,5,4,1,3 (две других не дают оптимального решения), пришиваем к ней одну из самых длинных оставшихся 2,7,9 (единственная альтернатива 7,2,9 не дает оптимального решения), и в конце пришиваем 8,6,2 - вуаля! Но, например, для $n=15$ так, кажется, уже не работает: мне не удалось найти оптимальную последовательность, содержащую одну из самых длинных хороших цепочек 14,9,5,4,1,3 или 13,8,5,3,2,1 или 11,7,4,3,1,2. Правда возился на бумаге, мог пропустить