2
$\begingroup$

I have some issues with a problem I found on this page: http://www.mast.queensu.ca/~peter/inprocess/prisoners.pdf

The problem goes as follows:
"A group of 100 condemned prisoners are offered the chance to play the following game. They will be each be allowed to enter a room one at a time in any order they wish until all 100 have gone in once. In the room there is a long table with a row of 100 identical wooden boxes numbered in order from 1 to 100. Each box can be opened and inside it there is the name of one of the prisoners, such that each of the 100 names appears exactly once. However, the ordering of the names in the boxes is random. Once inside the room, each prisoner is allowed to open and look inside 50 boxes—any 50 that he wants. After he has opened his 50 boxes he must leave the room, making sure that the boxes are in exactly the same state as he found them, and he is no longer able to communicate with any other prisoner. The reprieve that they have been granted is that at the end of the game they will all be spared on condition that every prisoner manages to find the box that contains his own name. On the other hand, if at least one of the prisoners fails to find his name, they will all be executed at dawn. Let’s be clear about this—in order to escape execution, it is necessary that every prisoner find his own name."

Now there is a strategy so that to probability of success is about 30%. Prisoner 1 goes in the room, opens box 1 and if he finds his number, he can leave, if not, then he opens the box whose number he has drawn in the previous box. He needs to find his number within 50 tries. Then prisoner 2 does the same with box 2 etc.

My problem basically is the calculation of the number of permutations having a cycle of length k. On page 3 it is said that there are $\binom {100}{k}$ ways to choose the elements of that cycle, $(k-1)!$ ways to arrange the elements and $(100-k)!$ for the remaining elements. I see why it is $(k-1)!$ arrangements (because it's a cycle and thus there are $(k-1)$ other arrangements that describe the same cycle), but why do we not do this to the remaining elements not being in the long cycle? Why don't we also take every possible permutation of the remaining numbers? Why is it not $(100-k-1)!$?

$\endgroup$
1
$\begingroup$

The formula that the author is trying to construct is :

How many permuntations of $n$ integers (from $1$ to $n$) form a cycle of length $k$?

By identifying that it doesn't matter which elements form the cycle, he reduces the problem to:

How many permuntations of $n$ integers (from $1$ to $n$) form a cycle of length $k$ with the first $k$ elements?

So the problem is broken into 2 parts. First, how many ways are there to arrange the first $k$ elements? The reason that it is $(k-1)!$ instead of $k!$, is because you cannot have a fixed point. If any $m^{\text{th}}$ element is $m$, then you have a cycle of length $1$ instead of length $k$. So the first element can't be $1$, the second element can't be $2$, etc.

So choose the first element, you have $k-1$ choices. Suppose you pick $a_1$. Then pick the $a_1^{\text{th}}$ element...it can't be $1$ and it can't be $a_1$, so you have $k-2$ choices. So pick $a_2$. Then pick the $a_2^{\text{th}}$ element. You can't choose $a_2$ or anything that has been chosen so far or $1$, so there are $k-3$ choices. The final $a_k$ choice must be $1$ to complete the cycle, so there are $(k-1)!$ cycles of the first $k$ elements.

Second, how many ways are there to arrange the remaining elements. This is where the author cheats a bit. He silently only considers the cases where $k > n/2$, meaning that you don't have to consider the possibility that there are multiple cycles of length $k$. Consequently , any arrangement of the remaining values is a valid count, even if it has fixed points or no fixed points or other cycles, since there aren't enough remaining elements to form cycle of length $k$. So there are $(n - k)!$ ways to arrange the remaining elements.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

In the long cycle, we have to make sure it is a single cycle. For the rest, you do not need to make sure it is a single cycle, so you can permute all $100-k$ elements in any order at all. Even the identity permutation is acceptable. For the long cycle, you have to make sure you get a single cycle, which is why you only have $(k-1)!$ for $k$ elements

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, let's say we have 8 prisoners instead of 100 and we have this permutation $(12)(5)(34678)$. We have $(8-5)!$ ways to arrange the numbers 1,2,5. So would this permutation $(21)(5)(34678)$ be also acceptable? Because $(12)$ and $(21)$ are exactly the same, so wouldn't we just count them twice? $\endgroup$ – CDO Jun 25 '15 at 1:00
  • $\begingroup$ You can arrange the numbers in $3!=6$ ways. Each arrangement corresponds to $(f(1),f(2),f(5))$ Translating into cycle notation $125 \to (1)(2)(5)$, while $215 \to (12)(5)$. If you try writing cycle notation directly, you will find more than $6$ arrangements, but some will be the same like you show. $\endgroup$ – Ross Millikan Jun 25 '15 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.