So, I have a combinatorics problem that I have partially solved but I need a little help finishing.
The problem goes like this:
There are $M$ people and $R$ of them are required to open a safe with multiple locks. You must find a way to evenly distribute, to $M$ people, the keys to these locks such that any group of $R$ people has each key but no group of $R-1$ does.
The first part of the problem requires knowing the minimum number of keys. This is a common combinatorics problem that has been asked and answered previously on this forum. The solution is $n_{keys} = {M \choose R-1}$
The second part of the problem entails figuring out how many copies of the keys are required to be able to evenly distribute the keys while still ensuring that no group of $R-1$ can open the safe.
For example: When $M = 4$, $R = 2$, $n_{keys} = 4$. But it is impossible to distribute just 4 keys to the 4 people while ensuring any 2 of them have all 4 keys. The only way is to make 3 copies of the keys. and distribute them [0,1,2],[0,1,3],[0,2,3],[1,2,3].
Can anyone help me work out a general solution for the number of copies required?
Thanks!
I managed to solve the problem myself by trial and error with the help of some code.
The solution is:
$n_{copies}=M−(R−1)$.