Last epiphany a friend asked me the following puzzle: "You have k king cakes and p persons eating. Each person gets exactly one equal sized piece of each cake, and of course each cake has exactly one king in one piece. What is the probability that each person has picked at least one king?"
Some facts
- Since we are asking for each person to have at least one king,
kmust be equal or bigger thanp. - Each cake is divided into
pequal sized pieces, because each person gets one piece of each cake. - The question "picking at least one king" is what makes the puzzle so difficult.
Abstraction
The problem is equal to repeatedly throwing a dice. Each king has the same chance to be picked by any person. So you could throw a dice with p surfaces for each king. You get a sequence of k numbers, say n(1)...n(k), each with value 1..p. The interpretation of this is that person n(i) has picked the king from the i-th cake. So now we deal with possible combinations of k digits, each having a value from 1..p.
Since all persons and cakes are the same, each combination has the same probability.
The question
... is now how many combinations are there, where each p is present at least once, meaning each person gets at least one king. The final probability is given by this value divided by the total number of combinations, which is p^k. E.g. when p=2, k=4, we have 4 bits and can represent 2^4 = 16 different numbers.
An example
Choose k=2, p=2. The combinations are:
1 1 1 2 2 1 2 2The first and the last are not valid, both kings go to the same person and the other one gets none. So we have a probability of
2/4 = 50% that each person gets at least one king.
Choose k=4, p=3. Then the list of combinations is:
1 1 1 1 1 1 1 2 1 1 1 3 1 1 2 1 1 1 2 2 ... 3 3 2 3 3 3 3 1 3 3 3 2 3 3 3 3A total of
3^4 = 81 combinations. As you can see it gets more complicated to write down all possibilities, so we are looking for a more abstract approach.
You could either try to find a formula for all valid combinations directly by finding all that have each p=1..3 occurring at least once, or you compute the inverse, the invalid ones, which are all combinations that have at least one p missing, and subtract it from the total count. An invalid combination would be 1 2 1 1 since 3 is not present which means person 3 gets no king. 1 2 3 x is valid for each x since every p is present.
I chose the second way. I found it easier to think with, but maybe the first works as well. The invalid combinations are those that either lack a 1, 2 or 3, let us call them m1, m2, m3. Each m has (3-1)^4 = 16 combinations. We could sum them up if they were disjoint. For example, 3 3 3 3 is counted twice, once in m1 and a second time in m2. So we have to subtract again all combinations that we counted twice. That is, combinations which are in two of m1, m2, m3. Let us call these possible sets m12, m23, m13. E.g. m12 is missing 1 and 2. There is actually only one combination for that: 3 3 3 3. m12, m23, m13 are disjoint, so we did not again count too much and are almost finished. The total amount of invalid combinations is then m1 + m2 + m3 - m12 - m23 - m13 = 3*(3-1)^4-3*(3-2)^4 = 45. And the final probability is (81-45)/81 = 36/81 = 4/9 ~ 44%.
Generic solution
The tricky part is to count m1, m2, ... mX. Since they are not disjoint, you can not simple sum them up, but have to compute the union. For that you need to know all the possible intersections between the sets. But luckily mankind has solved this before , and I could not explain it better. In short, to compute the union between a number of sets, you add all possible intersections between an odd number of the sets, and subtract all possible intersections between an even number of the sets. You also make use of combinatorics and the binomial coefficient. In our case A1 ∩ ... ∩ An means all combinations that are missing all of the digits 1..i. There are (p low n) such intersections and each counts (p-n)^k elements. So our final formula is:
sum((-1)^(n+1) * (p low n) * (p-n)^k), n=1..pAnd this would be the nice graph for it if Mathematica did plot it:
plot sum[power[-1,n+1]*binomial[p,n]*power[p-n,k],{n,1,p}], p=1..10 and k=1..10
The final result is:
(p^k - sum((-1)^(n+1) * (p low n) * (p-n)^k)) / p^k, n=1..p
A question for you
Is it possible to construct a fair dice for all n?
