Matematické Fórum

Skrytý text:

Najít permutaci s není nijak obtížné: Například dát 9 první, 8 poslední a doplnit to vhodně mezi, třeba takto: 9 4 0 7 5 1 6 2 3 8.

EDIT: Jen pro doplnění: hrubou silou jsem navíc zjistil, že takových permutací je 42.

M(sigma)    počet takových permutací
13                         42
14                      3202
15                    33388
16                  148464
17                  332680
18                  534384
19                  572160
20                  610560
21                  529920
22                  400320
23                  221760
24                  241920

Zajímavé můžou být poslední dva řádky této tabulky (počet stoupne). I když je to vlastně jasné:

M(sigma) je 24 právě tehdy, když permutace (třeba jako slovo z písmen 0,1,2,3,4,5,6,7,8,9) obsahuje podřetězec 987 (nějak zpermutovaný). To je právě v případech (3! možností pro podřetězec z písmen 7,8,9 a pak 8! pořadí objektů 0,1,2,3,4,5,6,"789").

M(sigma) je 23 právě tehdy, když permutace (třeba jako slovo z písmen 0,1,2,3,4,5,6,7,8,9) obsahuje podřetězec 986 (nějak zpermutovaný). To je ve stejném počtu případů jako výše, ale z toho musíme odečíst ta slova, která obsahují nějak zpermutovaný podřetězec 987, tedy obsahují jeden z podřetězců 7986, 7896, 6987 a 6897 - těch je (zdůvodnění podobně jako výše).

Řekl bych, že kdo někdy luštil kakuro, má tady drobounkou výhodu. :-)

Skrytý text:

Označme permutaci jako ABCDEFGHIJ.

Kdyby A+B+C <= 12 a D+E+F <= 12 a G+H+I <= 12, pak protože 0+1+2+3+4+5+6+7+8+9=45, tak zejména J=9.

Ovšem přeci také B+C+D <= 12 a E+F+G <= 12 a H+I+J <= 12, tedy stejně tak A=9.

Proto taková permutace neexistuje.