Neat little problem!
May. 20th, 2009 01:35 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
michiexileIf The next time someone asks me what group theory is good for, I should get them the following story / problem.
ETA: The key here is in recognizing that the way the Warden arranges the numbers is in fact a permutation. And there are some damn useful facts about permutation floating about that will help this problem immensely.
One really nice fact about permutations is that any permutation can be broken down into a composition of disjoint cycles. And one (kinda tricky) combinatorial thing one could figure out is the following:
Given some n and some k < n, how many of the n! permutations of n things have no cycles longer than k?
If this proportion could be figured out, or at least bounded, it might shed some light on how to make a really neat strategy for our beloved death row prisoners.
Now, the number of permutations of 100 elements that have a cycle of length 100 are precisely 99!: We can order the images within that cycle in 100! ways, but it is cyclically invariant, so we get each element 100 times that way. Alternatively, we can argue that by cyclical invariance, we can write the smallest element in a cycle first, so only the remaining elements get permuted, yielding 99!.
The number of permutations of 100 elements that have a cycle of length 99 are given by first choosing the elements in that cycle and then ordering them - so we get (100 C 99) * 98!.
The number of permutations of 100 elements that have a cycle of length 98 are given by first choosing these elements, then ordering them in the cycle, and then permuting the rest, so we get (100 C 98) * 97! * 2.
And this entry gives the pattern for all the elements. Hence, the total number of long permutations is given by the sum
Σk=51100 (100 C k) * (k-1)! * (100-k)!
which we can rewrite, by using the expression for the binomial coefficient in factorials, to
Σk=51100 (100!/(100-k)!k!) * (k-1)! * (100-k)! =
Σk=51100 100!/k
So the proportion of these among all the 100! permutations is exactly
Σk=51100 1/k
which we can easily compute using your favourite calculator program to be
Hence, the proportion of short permutations the complement of this, working out to about 0.31.
Now, in order to USE this knowledge, the prisoners should agree on the following strategy:
Each, in turn, goes in to the office and picks the box with his own number. In it, he will find another number, so he follows the instruction on the paper bit, and goes to that box. Continuing in the same manner, he will follow the paper trail, as it were, until he reaches his own number.
Since the numbers are permuted, doing this will ALWAYS get you back to your own number, since you are in your own cycle by definition. The only issue is whether your cycle will be short enough - all cycles have to be shorter than 50 for this to work. However, the probability of THIS occurring, we computed above - and it comes out to about 0.31. So this strategy would drastically improve on any more independent strategy.
There was this prison once, with 100 prisoners on death row. Out of a whim, the warden (with support from the judicial system - and let's not get into the sociologics of this!) decides on a game for the prisoners to try to get their freedom.
The warden assigns to each prisoner one of the numbers 1-100, writes the same numbers on pieces of paper, and distributes them at random among 100 covered compartments in a desk drawer in his office.
The prisoners are then summoned into the office, one after another, and get to choose and look at the numbers contained in 50 of the 100 compartments.
The prisoners are allowed to come up with a strategy before the game starts, but once the whole thing starts, they are kept in isolation, and also not allowed to change the drawer contents, or otherwise try to communicate.
If all prisoners manage to pick their own number among the papers they find, then they all go free.
If but one single prisoner fails to find their own number, then all prisoners are executed.
Note that if every prisoner picks 50 compartments at random, then the probability that all go free is 1/2100, or about 10-30.
Can you figure out a strategy that will perform better? The best I know of has a freedom rate of about 30/100.
ETA: The key here is in recognizing that the way the Warden arranges the numbers is in fact a permutation. And there are some damn useful facts about permutation floating about that will help this problem immensely.
One really nice fact about permutations is that any permutation can be broken down into a composition of disjoint cycles. And one (kinda tricky) combinatorial thing one could figure out is the following:
Given some n and some k < n, how many of the n! permutations of n things have no cycles longer than k?
If this proportion could be figured out, or at least bounded, it might shed some light on how to make a really neat strategy for our beloved death row prisoners.
Now, the number of permutations of 100 elements that have a cycle of length 100 are precisely 99!: We can order the images within that cycle in 100! ways, but it is cyclically invariant, so we get each element 100 times that way. Alternatively, we can argue that by cyclical invariance, we can write the smallest element in a cycle first, so only the remaining elements get permuted, yielding 99!.
The number of permutations of 100 elements that have a cycle of length 99 are given by first choosing the elements in that cycle and then ordering them - so we get (100 C 99) * 98!.
The number of permutations of 100 elements that have a cycle of length 98 are given by first choosing these elements, then ordering them in the cycle, and then permuting the rest, so we get (100 C 98) * 97! * 2.
And this entry gives the pattern for all the elements. Hence, the total number of long permutations is given by the sum
Σk=51100 (100 C k) * (k-1)! * (100-k)!
which we can rewrite, by using the expression for the binomial coefficient in factorials, to
Σk=51100 (100!/(100-k)!k!) * (k-1)! * (100-k)! =
Σk=51100 100!/k
So the proportion of these among all the 100! permutations is exactly
Σk=51100 1/k
which we can easily compute using your favourite calculator program to be
> sum . map (1.0/) $ [51..100]
0.6881721793101949
Hence, the proportion of short permutations the complement of this, working out to about 0.31.
Now, in order to USE this knowledge, the prisoners should agree on the following strategy:
Each, in turn, goes in to the office and picks the box with his own number. In it, he will find another number, so he follows the instruction on the paper bit, and goes to that box. Continuing in the same manner, he will follow the paper trail, as it were, until he reaches his own number.
Since the numbers are permuted, doing this will ALWAYS get you back to your own number, since you are in your own cycle by definition. The only issue is whether your cycle will be short enough - all cycles have to be shorter than 50 for this to work. However, the probability of THIS occurring, we computed above - and it comes out to about 0.31. So this strategy would drastically improve on any more independent strategy.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-05-12 10:26 am (UTC)Hmm. I'm having trouble managing that even on the condition that the first two prisoners pick their own numbers, let alone all 100...
Let x equal the number of compartments selected in common by both prisoners 1 and 2 (anywhere between 0 and 50).
Probability that Prisoners 1 and 2 satisfy the success condition can be broken down into the sum of two cases:
Case 1: Prisoner 1 picks compartments containing both 1 and 2 (probability=50/100 * 49/99), and then Prisoner 2 picks compartment containing 2 (probability = x/50, given that it's among the ones picked by Prisoner 1). Total = x*49/9900.
Case 2: Prisoner 1 picks compartments containing 1 but not 2 (probability = 50/100 * 50/99), and then Prisoner 2 picks compartment containing 2 (probability = (50-x)/50, given that Prisoner 1 has not picked compartment 2). Total = (50-x)*50/9900.
This is maximised by setting x=0, which gives total probability 2500/9900 or just over 25%.
What have I missed?
no subject
Date: 2009-05-12 10:37 am (UTC)The preamble is _VERY_ relevant to the problem.
no subject
Date: 2009-05-12 12:52 pm (UTC)Just to clarify a few points:
- Are all 100 numbers used? Wording suggests this but doesn't actually state it.
- Papers are distributed 'at random' - can I take this to mean one per compartment?
no subject
Date: 2009-05-12 01:02 pm (UTC)no subject
Date: 2009-05-12 09:48 pm (UTC)