2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Богатенький Буратино
Сообщение02.10.2018, 21:59 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение02.10.2018, 22:10 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение02.10.2018, 22:29 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение02.10.2018, 22:31 
Заслуженный участник
Аватара пользователя


16/07/14
8353
Цюрих
Ktina в сообщении #1343359 писал(а):
Складывается ощущение, что фрагмент "72481" обязан быть.
Да, и это легко доказывается.

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение03.10.2018, 00:48 
Аватара пользователя


07/01/16
1426
Аязьма
mihaild в сообщении #1343361 писал(а):
Да, и это легко доказывается.
$\texttt{963248157}$ ;-)

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение03.10.2018, 01:25 
Заслуженный участник
Аватара пользователя


16/07/14
8353
Цюрих
Да, соврамши. 248 обязательно должно быть, 7248 не обязательно должно быть 2481 тоже: 963248751.

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение03.10.2018, 10:39 
Аватара пользователя


07/01/16
1426
Аязьма
Можно и $\texttt{248}$ избежать, какая коварная задачка: $\texttt{396481572}$

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение03.10.2018, 11:05 


05/09/16
11467
Удивительно, но 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)))))

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение03.10.2018, 11:14 


14/01/11
2916
Т.е. обязательная подстрока - 48. :-)

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение03.10.2018, 15:32 


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

 Профиль  
                  
 
 Re: Богатенький Буратино
Сообщение03.10.2018, 15:57 
Аватара пользователя


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

-- 03.10.2018, 16:04 --

wrest,

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group