Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№106

Некоторые из марафонских задач привели к появлению новых последовательностей в OEIS. Макс Алексеев предложил использовать обратный механизм.

Конкурсная задача №106 (от 3 баллов)

Последовательность A116983 из OEIS определяется так:
a(n) есть порядковый номер n! при лексико-графическом упорядочении наборов цифр числа n! (система счисления десятичная). Последнее число, представленное в OEIS, - a(14). Требуется найти еще несколько членов A116983.

Примечание:
Три балла будут присуждаются за нахождение a(15). За нахождение большего числа членов последовательности можно заработать больше баллов (но шкала, конечно, не линейная).

Решение

Приведу решение Кирилла Веденского.

Алгоритм выглядит достаточно простым: посчитаем количество перестановок, следующих до данной.
Для этого суммируем количество перестановок:
- в которых первая цифра меньше исходной;
- в которых первая цифра такая же, а вторая цифра меньше исходной;

- в которых первые N-2 цифр такие же, а N-1-я цифра меньше исходной;

Проиллюстрируем на примере 8! = 40320.
Количество перестановок, в которых первая цифра меньше исходной:
4! (первая цифра 0) + 4!/2! (первая цифра 2, есть две цифры 0) + 4!/2
(первая цифра 3, есть две цифры 0)
Количество перестановок, в которых первая цифра такая же, а вторая цифра меньше исходной;
0 (нет таких)
Количество перестановок, в которых первые 2 цифры такие же, а третья цифра меньше исходной;
2! + 2!
Количество перестановок, в которых первые 3 цифры такие же, а четвертая цифра меньше исходной;
1!

Итого 53 перестановки, значит, 8! - 54-я перестановка из всех перестановок цифр {4, 0, 3, 2, 0}.

15! = 1307674368000

Расписываем в то же порядке:
12!/(3!2!2!2!)
11!/(3!2!2!2!)
0
9!/(2!2!2!) + 9!/(3!2!2!) + 9!/(3!2!2!) + 9!/(3!2!)
8!/(2!2!) + 8!/(3!2!) + 8!/(3!2!)
7!/2! + 7!/3! + 7!/3! + 7!/3!
6!/2! + 6!/3!
5!/2!
4!/2!
3!/2!
0
0

Итого a(15) = 10939036.

Обсуждение

Способ нахождения членов последовательсти A116983 вполне алгоритмичен, чем и воспользовались некоторые участники, написав программки для вычисления членов A116983. Вот список первых 56 элементов последовательности:

a(1) = 1
a(2) = 1
a(3) = 1
a(4) = 1
a(5) = 4
a(6) = 6
a(7) = 11
a(8) = 54
a(9) = 150
a(10) = 648
a(11) = 5013
a(12) = 9849
a(13) = 19345
a(14) = 1060707
a(15) = 10939036
a(16) = 4343045
a(17) = 2498014850
a(18) = 5271260976
a(19) = 78029366100
a(20) = 531495923280
a(21) = 805809810981
a(22) = 1936900666393
a(23) = 28724010464057580
a(24) = 29052364970866225
a(25) = 75805259574286872
a(26) = 7466893805506395652
a(27) = 80374513001512054041
a(28) = 107970218135938755545
a(29) = 470625860768285164823489
a(30) = 1092067058367696093174712
a(31) = 23984179502628809216577528
a(32) = 28431347279097359718381340
a(33) = 5150626025769827081670834298
a(34) = 1383260201138264136247099733688
a(35) = 40096653135679607283637405247475
a(36) = 3027594894915571935964583506118250
a(37) = 82517117748871209433749833265061771
a(38) = 10023949507379486198666370320376
a(39) = 29591831094276619678264441606954339281
a(40) = 46163337982794725066771282077346710635365
a(41) = 167123778203520614156182186766168917610
a(42) = 4272219633615780983161453419886264089692720
a(43) = 3546219319786770869389311505619069504631590
a(44) = 3204643067047695510545225270846590879418010540
a(45) = 301067471734634074167312982076454590413566273570
a(46) = 3478763899948438152773353635560057199222936720
a(47) = 314243141648440488497781888595628832937846875377365
a(48) = 14170607816144726336291784998260829063896134279304644
a(49) = 81202660426509885662918837537639284122923959544881921
a(50) = 13644407265774224299787535849835296136167182364020957
a(51) = 3052207259954845501804716327832959568946835875197382056
a(52) = 177399590232335095419162842190728774132068534221263601977
a(53) = 63105836544205896419818591639582430508711794388085938746998
a(54) = 1806209354593919702746922384504295016188456176805030340137733
a(55) = 308850865213754797767705699091611299087770935471801259228401390
a(56) = 58908915753538772653766821227935807457550571804703650490041199

И это, разумеется тоже не предел! Например, Анатолий Казмерчук добрался до a(1214), Петр Бежик (по его словам: он прислал меньше членов A116983, чем продекларировал) - аж до a(1300).

Отмечу, что по традиции на задачу, которая показалась скучной, как мне, так и участникам Марафона (см. эстетическую оценку), прислано рекордное для тура количество ответов :)

Награды

За правильное решение задачи ММ106 Виктор Филимоненков получает 3 призовых балла, Николай Дерюгин (он добрался до a(22)) - 4 баклла, Кирилл Веденский (он дошел до a(56) - 5 баллов, а Анатолий Казмерчук и Петр Бежик (им покорились более 1000 членов последовательности) - по 7 баллов.

Эстетическая оценка задачи - 2.3 балла


 

 


Страница: [[marathon:problem_106]]

marathon/problem_106.txt · Последние изменения: 2009/09/21 12:30 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006