Free the Bunny Prisoners
Analysys
The problem can be rearrange as follow:
If you have N bunnies, and M locks, distribute M distinct keys among the bunnies so that it will always require num_required bunnies to open the locks, and no bunny should have the same key twice.
Let us now consider this simple situation, let us say we have chosen $\text{num_required} - 1$ bunnies at random, and we were to choose 1 more bunny to get the complete set of keys to open the prison door. We know that these $\text{num_required} - 1$ bunnies cannot open the door by themselves and hence the remaining $\text{num_bunnies} - \text{num_required} + 1$ bunnies must have a key that these $\text{num_required} - 1$ bunnies don’t. We have total $\binom{\text{num_buns}}{\text{num_required} - 1}$ combination of each $\text{num_required}- 1$ bunnies pair, so we have also $\binom{\text{num_buns}}{\text{num_required} - 1}$ distinct keys. And there should be $\text{num_buns} - \text{num_required} + 1$ copies of each distinct key among the bunnies.
Note that $\binom{\text{num_buns}}{\text{num_required} - 1} = \binom{\text{num_buns}}{\text{num_buns} - \text{num_required} + 1}$
Thus, for the example of N = 5 and M = 3, there are $\binom{5}{3 - 1}$ distinct keys (10 keys).
We must distribute $5 - 3 + 1$ copies of all $10$ keys amongst the bunnies in such a way that any 3 bunnies we pair together have, amongst them, at least one copy of every key.
- we count number of distinct keys we have with formula $\binom{\text{num_buns}}{\text{num_required} - 1}$.
- Find the number of copies per key $\text{num_buns} - \text{num_required} + 1$.
- Yield combinations of keyholders one at a time, and we give key to each keyholder.
Reference
- Combination
- Pigeonhole principle
- Google Foobar Round 4
- foobar_4-1_free_the_bunny_prisoners.py
- 鸽笼原理
- 4.1_bunny.py