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

[gipokrat]

Все цифры натурального числа попарно различны.

Назовём цифру хорошей, если она не является первой или последней цифрой числа и равна модулю разности двух своих соседей.

1. Каково наибольшее возможное количество хороших цифр?

2. Найдите все натуральные числа, в которых достигается это наибольшее количество.

[wrest]

gipokrat
Прямой перебор 10! перестановок это же по нонешним временам быстро, у меня 20 сек на планшете в интерпретаторе pari/gp.

[gipokrat]

wrest в сообщении #1732424 писал(а):

gipokrat
Прямой перебор 10! перестановок это же по нонешним временам быстро, у меня 20 сек на планшете в интерпретаторе pari/gp.

Ну так неинтересно. Хочется всё-таки понять, почему ответ именно такой, а не просто перебрать варианты.

[wrest]

gipokrat в сообщении #1732425 писал(а):

Ну так неинтересно. Хочется всё-таки понять, почему ответ именно такой, а не просто перебрать варианты.

Ну и ещё можно обобщить. Сейчас имеем перестановки чисел $d \in \{0..9\}$ можно посчитать что будет для $d \in \{0..n\}$

[gipokrat]

wrest в сообщении #1732426 писал(а):

Ну и ещё можно обобщить. Сейчас имеем перестановки чисел $d \in \{0..9\}$ можно посчитать что будет для $d \in \{0..n\}$

Для исходной задачи у меня получились ровно четыре числа:

314597268,
862795413,
3145972680,
8627954130.

Причём по существу это одно и то же решение с точностью до обращения числа и приписывания нуля в конце: 862795413 — это 314597268, записанное в обратном порядке, а два десятизначных решения получаются приписыванием справа нуля.


А над Вашим обобщением надо подумать.

[waxtep]

Посчитал для $3\leqslant n\leqslant12$, тоже полным перебором, уже для $n=12$ его хочется назвать "невообразимо долгим" (минут сорок). Интересно бы конечно уметь рисовать это карандашом на бумаге. Ноль я игнорирую (он ничему не помогает), вот результат в формате $n$, кол-во хороших чисел, и "наименьшая" в естественном смысле расстановка, для которой максимум достигается:

1. [3, [1, Vecsmall([1, 2, 3])]] 
2. [4, [2, Vecsmall([2, 1, 3, 4])]] 
3. [5, [2, Vecsmall([1, 2, 3, 5, 4])]] 
4. [6, [2, Vecsmall([1, 2, 3, 5, 4, 6])]] 
5. [7, [3, Vecsmall([1, 3, 4, 7, 2, 5, 6])]] 
6. [8, [4, Vecsmall([1, 3, 4, 7, 5, 2, 6, 8])]] 
7. [9, [5, Vecsmall([3, 1, 4, 5, 9, 7, 2, 6, 8])]] 
8. [10, [6, Vecsmall([6, 2, 8, 10, 7, 3, 1, 4, 5, 9])]] 
9. [11, [6, Vecsmall([1, 3, 4, 7, 11, 5, 6, 2, 8, 10, 9])]] 
10. [12, [7, Vecsmall([1, 5, 6, 11, 7, 4, 3, 9, 12, 10, 2, 8])]] 

Забавно выглядит для $n=10$, число с краю не может быть меньше шестерки

[wrest]

waxtep

n=13, max_good=8
Permutation: 12 8 4 1 5 6 11 9 2 7 3 10 13 0

n=14, max_good=9
Permutation: 13 7 6 1 4 5 9 14 11 3 8 2 10 12 0

n=15, max_good=9
Permutation: 11 7 4 3 6 9 15 14 1 13 5 8 2 10 12 0

n=16, max_good=10
Permutation: 6 1 7 8 15 11 4 5 9 14 12 2 10 3 13 16 0

-- добавлено через 33 минуты --

Похоже на то, что максимум равен $\left \lfloor \dfrac{3(n-2)}{4}\right \rfloor$

[waxtep]

wrest, о, круто, - это Вы перебор быстрее делаете, или нашли какой-то другой способ? $n=15$ кстати необычно выглядит, для меньших $n$ всегда "горы" с фибоначчи-образными склонами разделяют "долины" из трех несвязанных между собой чисел, а тут появляется участок иного вида 1 13 5 - "полка" между двумя горными системами. Кхм, ну, лучше нарисовать конечно

[wrest]

waxtep в сообщении #1732670 писал(а):

о, круто, - это Вы перебор быстрее делаете, или нашли какой-то другой способ?

Перебор с отсечением и прочими оптимизационными блек-джеками, на Си и в многопотоке.
Но поиск только одного максимума. Хотя второй тривиален - симметрия. Есть ли ещё? Их программа не ищет.

[waxtep]

wrest в сообщении #1732671 писал(а):

Но поиск только одного максимума. Хотя второй тривиален - симметрия. Есть ли ещё? Их программа не ищет.

По крайней мере, для $n=13$ это лексикографически младший максимум, т.е. оно обязано начинаться на $12$ и заканчиваться на $13$, если игнорить ноль. Здесь полный перебор у меня занял 4,5 часа, так что в вопросе расчетов с дистанции схожу

[wrest]

waxtep в сообщении #1732685 писал(а):

Здесь полный перебор у меня занял 4,5 часа, так что в вопросе расчетов с дистанции схожу

Вот функция на pari/gp побыстрее

(Оффтоп)

find_perm(n) = {
  \\ ============================================================
  \\ Задача: найти перестановку чисел 0..n, максимизирующую
  \\ количество "хороших троек" подряд идущих элементов,
  \\ для которых выполняется: a[i-1] = |a[i-2] - a[i]|
  \\
  \\ Алгоритм: backtracking с битовой маской использованных чисел
  \\ и отсечением по верхней оценке (если даже все оставшиеся
  \\ позиции дадут +1 к счёту, рекорд не будет побит — ветку
  \\ не исследуем).
  \\ ============================================================

  \\ curr   — текущая перестановка длины n+1 (индексы 1..n+1)
  \\ best   — хранит рекорд: best[1] = лучший счёт,
  \\                         best[2] = соответствующая перестановка
  \\ Упаковали счётчик в вектор, потому что ~var в PARI/GP
  \\ работает только для векторов/матриц, но не для скаляров.
  my(curr = vector(n + 1), best = [-1, vector(n + 1)]);

  \\ Лямбда с анонимной рекурсией через self().
  \\ Параметры curr_ref и best_ref передаются по ссылке (~),
  \\ чтобы изменения внутри лямбды были видны снаружи
  \\ (замыкания в PARI/GP захватывают переменные по значению).
  my(backtrack(~curr_ref, ~best_ref, pos, mask, current_g) =
    \\ --- Базовый случай: перестановка достроена ---
    if(pos > n + 1,
      if(current_g > best_ref[1],
        best_ref[1] = current_g;     \\ новый рекорд по счёту
        best_ref[2] = curr_ref       \\ сохраняем копию перестановки
      ),
      \\ --- Отсечение (pruning) ---
      \\ Максимально возможный прирост = число оставшихся позиций.
      \\ Если даже он не даёт побить рекорд — ветку не идём.
      if(current_g + max(0, n + 1 - pos) > best_ref[1],
        \\ --- Перебор всех кандидатов на позицию pos ---
        for(v = 0, n,
          \\ Проверяем битовой маской, что число v ещё не использовано
          if(!bittest(mask, v),
            curr_ref[pos] = v;

            \\ Считаем прирост счёта: +1 если образовалась "хорошая тройка"
            my(new_g = current_g);
            if(pos >= 3,
              if(curr_ref[pos - 1] == abs(curr_ref[pos - 2] - curr_ref[pos]),
                new_g++
              )
            );

            \\ Рекурсивный вызов:
            \\   pos + 1                  — переходим к следующей позиции
            \\   bitxor(mask, shift(1,v)) — помечаем v как использованное
            \\   new_g                    — обновлённый счёт
            \\ ~curr_ref, ~best_ref       — пробрасываем ссылки дальше
            self()(~curr_ref, ~best_ref,
                   pos + 1, bitxor(mask, shift(1, v)), new_g)
          )
        )
      )
    )
  );

  \\ Запуск перебора: стартовая позиция 1, маска 0 (ничего не занято),
  \\ счёт 0.
  backtrack(~curr, ~best, 1, 0, 0);

  \\ Возвращаем [лучший_счёт, лучшая_перестановка]
  [best[1], best[2]]
}

Запуск

? find_perm(13)
time = 32,689 ms.
[8, [12, 8, 4, 1, 5, 6, 11, 9, 2, 7, 3, 10, 13, 0]]
?

-- добавлено через 10 минут --

gipokrat в сообщении #1732425 писал(а):

Хочется всё-таки понять, почему ответ именно такой, а не просто перебрать варианты.

Есть некоторые соображения, что верхняя граница не больше $\left \lfloor \dfrac{3(n-2)}{4}\right \rfloor$ но вот доказательство, вероятно, не поместится на поля этого форума
Суть в том, что нам надо составить максимальное количество "троек Фибоначчи", отсюда и ограничение в 3/4, ну и две цифры на концах не участвуют.

[mihaild]

Ortools claims that this pattern breaks at $n=17$ already.

 n, 3*(n-2)/4, (optimality proven, best permutation, best value)
5 2.25 (True, [1, 4, 5, 3, 2], 2)
6 3.0 (True, [1, 3, 4, 2, 6, 5], 2)
7 3.75 (True, [5, 3, 2, 4, 6, 1, 7], 3)
8 4.5 (True, [2, 3, 5, 8, 7, 1, 6, 4], 4)
9 5.25 (True, [3, 1, 4, 5, 9, 7, 2, 6, 8], 5)
10 6.0 (True, [6, 2, 8, 10, 7, 3, 1, 4, 5, 9], 6)
11 6.75 (True, [2, 6, 8, 5, 3, 4, 7, 11, 10, 1, 9], 6)
12 7.5 (True, [8, 2, 10, 12, 9, 3, 6, 5, 1, 4, 7, 11], 7)
13 8.25 (True, [12, 8, 4, 1, 5, 6, 11, 9, 2, 7, 3, 10, 13], 8)
14 9.0 (True, [12, 10, 2, 8, 3, 11, 14, 9, 5, 4, 1, 6, 7, 13], 9)
15 9.75 (True, [13, 11, 2, 9, 3, 12, 15, 8, 7, 1, 5, 6, 4, 10, 14], 9)
16 10.5 (True, [6, 1, 7, 8, 15, 11, 4, 5, 9, 14, 12, 2, 10, 3, 13, 16], 10)
17 11.25 (True, [12, 7, 5, 2, 4, 6, 10, 16, 15, 1, 14, 11, 3, 8, 9, 17, 13], 10)
18 12.0 (True, [15, 12, 3, 13, 16, 9, 7, 2, 8, 10, 18, 14, 4, 1, 5, 6, 11, 17], 11)
19 12.75 (True, [9, 5, 14, 19, 13, 6, 2, 8, 10, 18, 11, 7, 4, 3, 12, 15, 1, 16, 17], 12)
20 13.5 (True, [11, 17, 13, 4, 16, 20, 14, 6, 8, 1, 9, 10, 19, 12, 7, 5, 2, 3, 15, 18], 12)
21 14.25 (False, [12, 3, 15, 18, 13, 5, 8, 6, 14, 20, 4, 16, 7, 9, 1, 10, 11, 21, 19, 2, 17], 13)

[wrest]

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

Ortools claims that this pattern breaks at $n=17$ already.

Ну там и раньше, на 6, ломается. Я списал это на "краевые эффекты".

Через SAT-солверы, кстати, интересный подход. Разумное время тратит? Рост времени какой (сложность)?

[wrest]

wrest в сообщении #1732706 писал(а):

Рост времени какой (сложность)?

Запилил поиск через SAT-солвер (локально, на планшете, в один поток).
Получается так:
n=15 время 70c
n=16 время 136c
n=17 время 399c
n=18 время 1083c

А ведь неплохо! Что-то вроде $O (\log N)$ где $N=n!$

[mihaild]

wrest в сообщении #1732706 писал(а):

Разумное время тратит? Рост времени какой (сложность)?

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

 15 2.211945056915283 9.75 (True, [5, 14, 10, 4, 6, 1, 7, 8, 15, 12, 3, 9, 2, 11, 13], 9)
16 18.424837112426758 10.5 (True, [6, 1, 7, 8, 15, 11, 4, 5, 9, 14, 12, 2, 10, 3, 13, 16], 10)
17 23.06130576133728 11.25 (True, [9, 2, 11, 13, 5, 8, 6, 14, 1, 15, 16, 12, 4, 3, 7, 10, 17], 10)
18 21.799165725708008 12.0 (True, [15, 12, 3, 13, 16, 9, 7, 2, 8, 10, 18, 14, 4, 1, 5, 6, 11, 17], 11)
19 73.69717478752136 12.75 (True, [9, 5, 14, 19, 13, 6, 2, 8, 10, 18, 11, 7, 4, 3, 12, 15, 1, 16, 17], 12)
20 159.32881927490234 13.5 (True, [5, 15, 11, 4, 7, 6, 13, 19, 10, 9, 1, 8, 12, 20, 17, 3, 14, 2, 16, 18], 12)
21 142.90941619873047 14.25 (True, [18, 14, 4, 16, 20, 13, 7, 6, 1, 5, 10, 15, 2, 17, 19, 11, 8, 3, 9, 12, 21], 13)
22 450.7276964187622 15.0 (True, [9, 1, 10, 11, 21, 17, 4, 13, 3, 16, 19, 12, 7, 5, 15, 20, 18, 2, 6, 8, 14, 22], 14)
23 318.8404383659363 15.75 (True, [16, 3, 19, 22, 12, 10, 2, 9, 11, 20, 14, 6, 1, 7, 8, 15, 23, 18, 5, 13, 4, 17, 21], 15)

wrest в сообщении #1732715 писал(а):

Что-то вроде $O (\log N)$ где $N=n!$

$\log(n!) \approx n \cdot \log n$, на что совсем непохоже. Больше похоже на $O(\log(2^{2^n})$ ИМХО.