MathDB
2017 Discrete #5

Source:

October 12, 2022
2017Discrete Math Test

Problem Statement

A <spanclass=latexitalic>shuffle</span><span class='latex-italic'>shuffle</span> is a permutation of the integers 1,2,3,4,51,2,3,4,5. More formally, a shuffle is a function f:{1,2,3,4,5}{1,2,3,4,5}f:\{1,2,3,4,5\}\rightarrow\{1,2,3,4,5\} such that if iji\neq j then f(i)f(j)f(i)\neq f(j). For example, 123452315412345\mapsto23154 denotes a shuffle ff so that f(1)=2f(1)=2, f(2)=3f(2)=3, f(3)=1f(3)=1, f(4)=5f(4)=5, and f(5)=4f(5)=4. A shuffle can be repeated some number of times to obtain another shuffle. For example, if ff is the shuffle 123452315412345\mapsto23154 from above, then repeating ff twice gives the shuffle g(x)=f(f(x))g(x)=f(f(x)) which is 123453124512345\mapsto31245. How many shuffles are there that, when repeated 66 times, give the shuffle 123451234512345\mapsto12345?