1. Free the Bunny Prisoners
    1. Analysys
    2. Reference

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.

  1. we count number of distinct keys we have with formula $\binom{\text{num_buns}}{\text{num_required} - 1}$.
  2. Find the number of copies per key $\text{num_buns} - \text{num_required} + 1$.
  3. Yield combinations of keyholders one at a time, and we give key to each keyholder.

Free The Bunny Prisoners

Reference