Богатенький Буратино

[Ktina]

Лиса Алиса и Кот Базилио предложили Буратино заработать денег. Буратино должен выписать в строчку цифры от 1 до 9, каждую цифру ровно 1 раз. Алиса обещала дать Буратино один сольдо за каждое двузначное число в этой цепочке, делящееся на три. Базилио, в свою очередь, обещал дать Буратино один сольдо за каждое двузначное число в этой цепочке, делящееся на 8. На какую максимальную сумму дохода может рассчитывать Буратино?

[mihaild]

От Базилио получим максимум 4 (вторая цифра должна быть четной), от Алисы - максимум 7 (из 8 возможных пар есть минимум одна, в которой одно число делится на 3, а другое нет).
11 получим, например, за 572481639.

[Ktina]

mihaild
Большое спасибо!
У меня в примере число было немного другое:
963724815.
Складывается ощущение, что фрагмент "72481" обязан быть.

[mihaild]

Ktina в сообщении #1343359 писал(а):

Складывается ощущение, что фрагмент "72481" обязан быть.

Да, и это легко доказывается.

[waxtep]

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

Да, и это легко доказывается.

$\texttt{963248157}$

[mihaild]

Да, соврамши. 248 обязательно должно быть, 7248 не обязательно должно быть 2481 тоже: 963248751.

[waxtep]

Можно и $\texttt{248}$ избежать, какая коварная задачка: $\texttt{396481572}$

[wrest]

Удивительно, но PARI/GP перебирает все числа всего за 3 секунды.
Вот все 20 чисел на 11 сольдо:

(Оффтоп)

157248396
157248963
396157248
396481572
396487215
396572481
396724815
572481396
572481639
572481693
572481963
724815396
724815639
724815693
724815963
963157248
963248157
963248751
963572481
963724815

Функция soldo берет на вход вектор (массив) из чисел и считает сольдо
soldo(v)=my(c=0);for(i=1,#v-1,num=10*v[i]+v[i+1];if(num%3==0,c=c+1);if(num%8==0,c=c+1));return(c)
Функция forperm встроенная -- перебирает все перестановки. Ну и печатает те, для которых дают больше 10 сольдо:
forperm(9,p,if(soldo(p)>10,print(fromdigits(Vec(p)))))

[Sender]

Т.е. обязательная подстрока - 48.

[wrest]

А сколько сольдо по максимуму получит Буратино, если Алиса и Базилио будут делить не на 3 и 8, а на другие числа, не равные единице (не обязательно разные)? Больше 14 может?

[waxtep]

Больше $14$ (достижимого на трешках) точно никак - нет ни одного простого числа $\leqslant\left\lfloor\dfrac{100}8\right\rfloor$, чтобы на него все восемь пар делились. Вот можно $12$, если один считает трешки, а другая - семерки: $\mathrm{784215639}$. А $13$, вроде бы, недостижимо

-- 03.10.2018, 16:04 --

wrest,

(Оффтоп)

прошу прощения, можете код под кат прятать? На мобильном экран разносит просто жуть