Дискретная математика.

[karandash_oleg]

1) Найти перестановку $(1,2,3,4,5,6,7)$, $lex$ под номером 59.

2) $\{a,b,c,d,e\}$ -- слова длины 8. Какое слово идет под номером $25$.

3) Найти остаток от деления $29^{15^{31}}$ на 13.

Правильно ли я понимаю, что в третьем можно так:

3) $29^{15^{31}}\equiv 3^{15^{31}} (\bmod 13)$

$3^{15^{31}}\equiv 27^{5\cdot 15^{30}} (\bmod 13)$

$27^{5\cdot 15^{30}}\equiv 1^{5\cdot 15^{30}} (\bmod 13)$

$1\equiv 1^{5\cdot 15^{30}} (\bmod 13)$

Следовательно остаток будет 1.

1) В первом нужно будет просто в лоб выписывать вот так или нет?

$(1,2,3,4,5,6,7)$

$(1,2,3,4,5,7,6)$

$(1,2,3,4,6,5,7)$

$(1,2,3,4,6,7,5)$

$(1,2,3,4,7,5,6)$

$(1,2,3,4,7,6,5)$

......

Правильно? (есть ли способ попроще?)

Во второй задаче пока что не понимаю -- с чего начать, подскажите, пожалуйста!

[mihailm]

1) Да
3) Какая будет на 24 месте?
2) Начать также как в 3), выписывать по очереди

[iifat]

mihailm в сообщении #1130753 писал(а):

1) Да

Вы, по-моему, номера перепутали.
karandash_oleg
3) Да, можно и так. Подозреваю, задача на малую теорему Ферма — она вам известна? Хотя ваше решение, пожалуй, короче.

[svv]

1) Начните выписывать в лоб, но только для того, чтобы уловить закономерность и потом быстро решить.
После нескольких выписанных перестановок Вы понимаете, что из $7!$ перестановок у первых $5!=120$ (и у $59$-й в том числе) в начале будут стоять $1$ и $2$.
Из этих $120$ у первых $4!=24$ третья цифра будет $3$, у вторых $24$ третья цифра будет $4$, у третьих $24$ (и Вашей в том числе) третья цифра будет $5$.
Теперь задача сводится к такой: какой будет перестановка цифр $3,4,6,7$ под номером $59-2\cdot 24=11$ в лексикографически упорядоченном списке всех перестановок?

Итак, задача решается рекурсивно, сводясь на каждом шаге к аналогичной для меньшего количества элементов.

[mihailm]

mihailm в сообщении #1130753 писал(а):

1) Да
3) Какая будет на 24 месте?...

1) и 3) конечно, надо поменять местами.

[karandash_oleg]

svv в сообщении #1130769 писал(а):

1) Начните выписывать в лоб, но только для того, чтобы уловить закономерность и потом быстро решить.
После нескольких выписанных перестановок Вы понимаете, что из $7!$ перестановок у первых $5!=120$ (и у $59$-й в том числе) в начале будут стоять $1$ и $2$.
Из этих $120$ у первых $4!=24$ третья цифра будет $3$, у вторых $24$ третья цифра будет $4$, у третьих $24$ (и Вашей в том числе) третья цифра будет $5$.
Теперь задача сводится к такой: какой будет перестановка цифр $3,4,6,7$ под номером $59-2\cdot 24=11$ в лексикографически упорядоченном списке всех перестановок?

Итак, задача решается рекурсивно, сводясь на каждом шаге к аналогичной для меньшего количества элементов.

Спасибо, кажется понял. Мне дальше проще так, после того как определились с третьей цифрой!

$49$-ая перестановка будет $\{1,2,5,3,4,6,7\}$. Далее шесть перестановок последних трех цифр дают $55$-ую перестановку.

$55$-ая перестановка будет $\{1,2,5,3,7,6,4\}$

$56$-ая перестановка будет $\{1,2,5,4,3,6,7\}$

$57$-ая перестановка будет $\{1,2,5,4,3,7,6\}$

$58$-ая перестановка будет $\{1,2,5,4,6,3,7\}$

$59$-ая перестановка будет $\{1,2,5,4,6,7,3\}$

Правильно ли я понял?

Насчет второй задачи все еще нет идей.

[ewert]

karandash_oleg в сообщении #1130747 писал(а):

2) $\{a,b,c,d,e\}$ -- слова длины 8. Какое слово идет под номером $25$.

Т.е., собственно: как записывается число 24 в пятеричной системе счисления?

[svv]

Вы правильно поняли идею, но перестановка, которую Вы записали как $55$-ю, на самом деле $54$-я, и соответственно дальнейшие номера тоже съедут вниз на $1$. А настоящую $59$-ю Вы ещё не выписали.

А, не заметил: ошибка на $1$ ещё с $49$-й, которая должна быть $48$-й.

[arseniiv]

karandash_oleg
Надеюсь, вам зачтут запись перестановок, которая по виду ничем не отличается от записи множества.

karandash_oleg в сообщении #1130781 писал(а):

Насчет второй задачи все еще нет идей.

Нет идей, что означает задание, или нет идей, как решать? Я не с первого раза понял, что там спрашивается, и если вы также, то вот что: «Слова длины 8 над алфавитом $\{a,b,c,d,e\}$, перечисляются лексикографически. Найдите 25-е». (Хотя я мог понять и не так, как задумывал автор.) Это даже проще, чем с перестановками:

$$aaaaaaaa, aaaaaaab,\ldots$$

Совет svv на этот случай переносится тоже.

P. S. Ага, ewert понял задание так же.

P. P. S. (1) Вообще, строго говоря, нельзя лексикографически перечислять строки над алфавитом, если на нём не задан линейный порядок. Понятно, что имелось в виду $a<b<c<d<e$, но… (2) Также вообще-то младшим концом строки может быть и левый, а не только правый. Но будем надеяться, что правый. Иногда используют слова «антилексикографический порядок», но тем обычно только увеличивают путаницу.

[ewert]

P.S. Иначе понять вторую задачу просто невозможно (причём в обоих смыслах).

P.P.S. На любом алфавите задан линейный порядок по определению алфавита.

[karandash_oleg]

svv в сообщении #1130786 писал(а):

Вы правильно поняли идею, но перестановка, которую Вы записали как $55$-ю, на самом деле $54$-я, и соответственно дальнейшие номера тоже съедут вниз на $1$. А настоящую $59$-ю Вы ещё не выписали.

А, не заметил: ошибка на $1$ ещё с $49$-й, которая должна быть $48$-й.

Разве у 48-ой третья цифра не 4?

[svv]

С $49$-й я ошибся, извините. Но $55$-я — да, должна быть $54$-й.
Перестановок, начинающихся с $1253...$ шесть, и они имеют номера $49,50,51,52,53,54$. Последняя из них — это $1253764$.

[arseniiv]

ewert в сообщении #1130793 писал(а):

P.P.S. На любом алфавите задан линейный порядок по определению алфавита.

Ну, если так (я думал, это просто множество — желательно, конечное или счётное), то хорошо. Хотя здесь всё равно нельзя сказать, что указано, какой из $5!$ порядков задан. Ведь $\{a,b,c,d,e\} = \{c,e,a,d,b\}$.

[karandash_oleg]

Спасибо, теперь понял формулировку второй задачи.

Тогда получается, что первые $5$ вариантов, это когда последняя цифра пробегает значения $abcde$, а первые семь цифр $a$.

Еще будут $5$ вариантов, когда первые $6$ цифр $a$, $7$-ая цифра будет $b$, последняя цифра пробегает значения $abcde$

Аналогично с $7$-ая цифрой будет $c,d,e$. Последний вариант, когда седьмая цифра $e$ будет как раз $25$-ым $aaaaaeee$.

Правильно?

-- 11.06.2016, 16:10 --

svv в сообщении #1130796 писал(а):

С $49$-й я ошибся, извините. Но $55$-я — да, должна быть $54$-й.
Перестановок, начинающихся с $1253...$ шесть, и они имеют номера $49,50,51,52,53,54$. Последняя из них — это $1253764$.

Спасибо, понял, разобрался!

[arseniiv]

karandash_oleg в сообщении #1130798 писал(а):

Правильно?

Рассуждали вы правильно, а в строке $aaaaaaee$ опечатались.