Permute till you drop

Probability Level 5

Let Z n \mathbb{Z}_n denote the set of all positive integers less than or equal to an integer n n , and let σ \sigma denote a permutation of Z n \mathbb{Z}_n .

What is the maximum value of k k such that there exists a permutation σ \sigma defined on Z 10 \mathbb{Z}_{10} , for which σ k ( Z 10 ) = Z 10 \sigma^{k}(\mathbb{Z}_{10})=\mathbb{Z}_{10} , but σ i ( Z 10 ) ≠ Z 10 , ∀ 1 < i < k \sigma^i(\mathbb{Z}_{10})\neq \mathbb{Z}_{10}, \forall 1<i<k

Note : Here

  1. f ( S ) = S f(S)=S means that f ( x ) = x , ∀ x ∈ S f(x)=x,\forall x \in S .

  2. f ( S ) ≠ S f(S) \neq S means that f ( x ) = x f(x)=x is NOT satisfied for at least one element x ∈ S x \in S .

  3. σ m ( S ) = σ ∘ σ ∘ ⋯ ∘ σ ⏟ m times ( S ) \sigma^m(S)=\underset{m\text{ times}}{\underbrace{\sigma \circ \sigma \circ \cdots \circ \sigma}} (S)


The answer is 30.

Janardhanan Sivaramakrishnan by Janardhanan Sivaramakris… , 42

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

The maximum value of k k would happen if the permutation is composed of sub-cycles of length c 1 , c 2 , ⋯ , c m c_1,c_2,\cdots,c_m such that c 1 + c 2 + ⋯ + c m = 10 c_1+c_2+\cdots+c_m=10 and k = L C M ( c 1 , c 2 , ⋯ , c m ) k=LCM(c_1,c_2,\cdots,c_m) is maximized.

This occurs when there are three sub-cycles of length 2 , 3 , 5 2,3,5 in the permutation, making k = 30 k=30 .

An example of such a permutation

σ = ( 1 2 3 4 5 6 7 8 9 10 2 1 4 5 3 10 6 7 8 9 ) \sigma = \left(\begin{array}{rrrrrrrrrr}1&2&3&4&5&6&7&8&9&10\\ 2&1&4&5&3&10&6&7&8&9\end{array}\right)

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Thanks for the link @Agnishom Chattopadhyay . I figured the logic and was sure that there would be an associated series, but could not search it.

Janardhanan Sivaramakrishnan - 4 years, 11 months ago

Can you provide a more detailed solution or relevant material?

Rushikesh Jogdand - 4 years, 11 months ago

Also see: A000793

Agnishom Chattopadhyay - 4 years, 11 months ago

Thanks., but I was looking for an explanation of the solution (and question too). It'd be better if you provide link to some material on the topic or much simply, just provide name of terms and topics regarding this. I'd google them.

Rushikesh Jogdand - 4 years, 11 months ago

Log in to reply

Look up Symmetry Group and Permutations

Agnishom Chattopadhyay - 4 years, 11 months ago

can you clarify the first 2 sentences? thanks!!!

Willia Chang - 4 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...