Krdytkyu

In a game, $60$ kids have the chance to win presents. The organiser gives every kid a number between $1$ and $60$, so that all kids have different numbers. In a room, there is a cupboard with $60$ drawers.

Now the organiser randomly puts the number of exactly $1$ kid into each of the drawers and closes them afterwards.

The kids enter the room sequentially. Every kid is allowed to to open $30$ drawers in a random order and has to close them with its content afterwards.

If all kids find their numbers in their drawers, then every kid gets a present. If not, nobody gets any present.

Before the first kid enters the room, all kids can talk to each other, after that, they are not allowed to do anymore.

a) How can one find out the number of permutations from $1$ to $60$, which have a cyclic permutation of length $l > 30$?

b) How can one use a) to develop a strategy for the kids, so that all kids get a present with the probability of $1-H_{60}-H_{30}$?

$H_n$ is the n-th harmonic number with $H_n = sum_{k=1}^n frac{1}{k}$

So to structure this a bit:

• 
  $60$ kids


• numbers $1,..,60$
  


• drawers $1,..,60$
  


• every kid opens $30$ drawers

I know that the notation for cyclic permutation goes as following:

For $n in mathbb{N}$ and different numbers $i_1,i_2,...,i_k in [n]$ the cycle $(i_1,i_2,...,i_k)$ denotes the permutation $pi in S_n$ with

I'm pretty new to combinatorics, so I don't know how to find out the number of permutations from $1$ to $60$, which have a cyclic permutation of length $l > 30$...

I'm summarizing the Wikipedia article mentioned in the comments.

Disjoint Cycle Notation

Any permutation $pi$ can be decomposed in the composition of disjoint cycles, where
$$pi = (mathrm{cycle 1})(mathrm{cycle 2})...$$

For example, the permutation $pi(1)=3$, $pi(2)=4$, $pi(3)=1$,$pi(4)=2$ can be written as
$$pi = (1,3)(2,4)$$

Note that $pi=(3,1)(2,4)=(3,1)(4,2)=(1,3)(4,2)$ are equivalent.

Counting the permutations

Now we find the number of permutations of $Z_60$ which have a cycle of length greater than 30.

First we note that a permutation can only have one such cycle (since cycles are disjoint). We define $l$ to be the length of this cycle. Then we note that two such permutations ($l > 30$) are different if the lengths of their largest cycle are different. So we can say that the number of permutations with $l>30$ is equal to
$$sum_{k=31}^{60}{n_k}$$
where $n_k$ is the number of permutations with $l=k$.

Now we just need to calculate $n_l$. We know that there are $60choose{l}$ possible ways to choose the values of the largest cycle, and there are $frac{l!}{l} = (l-1)!$ ways to order the values in the notation to produce a different cycle (the position of the first element is a free choice, but after that the representation is determined, so there are $l$ ways to write the same cycle). For the values not in the main cycle, there are $(60-l)!$ different permutations. Therefore,
$$n_l = {60 choose l} (l-1)! (60-l)! = frac {60!} l$$

Now we just directly sum the $n_l$ to find the number $n$ of such permutations.

$$n = 60! (frac 1 {31} + ... frac 1 {60})$$

Probability

We know there are $60!$ permutations in total so the probability a randomly selected permutation has a cycle of length greater than 30 is

$$n/60! = (frac 1 {31} + ... frac 1 {60}) approx 0.68488$$

Therefore the probability a permutation has no cycle of length greater than 30 is $$1-0.68488 approx 0.31512$$