How do you create a general locked-box problem?

Question

In this question, I presented a puzzle involving seven locks, with a Grand Vizier and four slaves.

But I would like to use this style of puzzle in some of my own secret-unlocking riddles, in order to require that a person solve a specific number of problems in order to proceed, without regard for what order they solve them in or which ones they decide to solve. To do this, I make each riddle reveal a specific section of a secret key upon being solved, which is analogous to getting one person to use all his keys to unlock some of the locks on the box.

For example, consider the following:

I have two level A riddles, four level B riddles, and six level C riddles, and I want the challenger to pass if and only if he's solved at least one of the following sets:

• One level A riddle and two level B riddles.
• One level A riddle, one level B riddle, and two level C riddles.
• Two level B riddles and three level C riddles.
• All six level C riddles.

How do I go about finding a configuration of keys that would make these conditions (or any other conditions I might care to devise) hold?

Answer 1

In order to construct the solution to this problem in the general space, it's helpful to ignore the Grand Vizier. The Grand Vizier can hold all the keys except one, which all the slaves hold, and that answers that component minimally.

I have discovered a generic method for generating solutions to these puzzles given arbitrary values. The general method relies on some stuff which I develop in the beginning, but if you want to just go ahead and read that, it's below.

tl;dr? This is how you do it: list out all the possible combinations of ones and zeros for $(N-R+1)$ ones, filling in the rest with zeros. Assign each unique combination to its own key, and boom! Generic solution matrix!

To cover the even more generic solution you've requested would take an insanely long document, and would probably best just be written as a paper. I'm not going to do that here, but I will generally outline how this might work.

---

A Method for $N$ or $N-1$ slaves

I will demonstrate the method for $N$ of $N$ slaves, and $N-1$ of $N$ slaves, as well as a generic method below.

If it is $N$, then trivially give each slave a key - then they must all be together.

If it is $N-1$, then things become a little trickier. Construct a table with N rows and columns (including the first one, which is numbered):

_______________
S1|  |  |  |  |
S2|  |  |  |  |
S3|  |  |  |  |
S4|  |  |  |  |
S5|  |  |  |  |

In this example, there are five slaves, numbered. Give the first two slaves a key:

_______________
S1| 1|  |  |  |
S2| 1|  |  |  |
S3|  |  |  |  |
S4|  |  |  |  |
S5|  |  |  |  |

Then, for each remaining space in the first column, create a new key and copy it into the corresponding space in the first row:

_______________
S1| 1| 2| 3| 4|
S2| 1|  |  |  |
S3| 2|  |  |  |
S4| 3|  |  |  |
S5| 4|  |  |  |

Then, insert new keys into the second column:

_______________
S1| 1| 2| 3| 4|
S2| 1| 5|  |  |
S3| 2| 5|  |  |
S4| 3|  |  |  |
S5| 4|  |  |  |

Repeat the above until you have filled in the grid:

_______________
S1| 1| 2| 3| 4|
S2| 1| 5| 6| 7|
S3| 2| 5| 8| 9|
S4| 3| 6| 8|10|
S5| 4| 7| 9|10|

This grid requires $N-1$ slaves to open the box. You also need to remember to give them the Vizier's key.

Your original problem's filled matrix is:

____________
S1| 1| 2| 3|
S2| 1| 4| 5|
S3| 2| 4| 6|
S4| 3| 5| 6|

In general, if you want $N-1$ slaves to open the box, you must have $N*(N-1)/2$ keys. For four slaves, this is $4*3/2=12$; for $5$ slaves, this is $5*4/2=10$. Add one key if you want a Vizier.

---

The Generic Method

First, let's go back and change the way we've been representing this problem. Let's instead create a matrix of keys and slaves, and use 1s and 0s to represent which slaves hold which keys.

4/4 Required  3/4 Required      2/4 Required 
------------  ----------------  ------------
Key|1|2|3|4|  Key|1|2|3|4|5|6|  Key|1|2|3|4|
------------  ----------------  ------------
 S1|1|0|0|0|   S1|1|1|1|0|0|0|   S1|1|1|1|0|
 S2|0|1|0|0|   S2|1|0|0|1|1|0|   S2|1|1|0|1|
 S3|0|0|1|0|   S3|0|1|0|1|0|1|   S3|1|0|1|1|
 S4|0|0|0|1|   S4|0|0|1|0|1|1|   S4|0|1|1|1|

The question we have to ask is: why these particular combinations? If you notice, all columns in the 4/4 matrix have one 1; all in the 3/4 have 2; all in the 2/4 have 3; and trivially, all in the 1/4 have 4. This points to a formula: there exist $(N-R+1)$ copies of each key, where $N$ is the number of slaves, and R is the number required. I have yet to prove this, but it appears to be consistent.

Note, as a curiosity, that 4/4 and 2/4 are effectively the "inverses" of each other (i.e. 1 swaps with 0). With $5x5$, I'll demonstrate (but again, unfortunately, not prove) that the solutions for problems whose distance from the center of $(2,N)$ (which is $(N+2)/2)$ is equivalent are inverses.

Here are the 5x5 matrices:

5/5 Required    4/5 Required               3/5 Required               2/5 Required
--------------  -------------------------  -------------------------  -------------
Key|1|2|3|4|5|  Key|1|2|3|4|5|6|7|8|9|10|  Key|1|2|3|4|5|6|7|8|9|10|  Key|1|2|3|4|5|
--------------  -------------------------  -------------------------  --------------
 S1|1|0|0|0|0|   S1|1|1|1|1|0|0|0|0|0| 0|   S1|1|1|1|1|1|1|0|0|0| 0|   S1|1|1|1|1|0|
 S2|0|1|0|0|0|   S2|1|0|0|0|1|1|1|0|0| 0|   S2|1|1|1|0|0|0|1|1|1| 0|   S2|1|1|1|0|1|
 S3|0|0|1|0|0|   S3|0|1|0|0|1|0|0|1|1| 0|   S3|1|0|0|1|1|0|1|1|0| 1|   S3|1|1|0|1|1|
 S4|0|0|0|1|0|   S4|0|0|1|0|0|1|0|1|0| 1|   S4|0|1|0|1|0|1|1|0|1| 1|   S4|1|0|1|1|1|
 S5|0|0|0|0|1|   S5|0|0|0|1|0|0|1|0|1| 1|   S5|0|0|1|0|1|1|0|1|1| 1|   S5|0|1|1|1|1|

No, I won't make you suffer through 6x6 matrices, but these are worth a good inspection. Note that 4/5 and 3/5 are equivalent. $(N+2)/2$ for these is 3.5; 4 and 3 are equidistant and are inverses; so are 5 and 2. But this is an aside.

So, this is ridiculous and all - what's the pattern here?

Well, take a look again! The pattern is that the distribution of keys matches all possible combinations of ones and zeros for that number of keys. For instance, the 4/5 matrix has two keys. All of the columns of that matrix are the unique combinations of those numbers in this space.

The number of keys? That's just the factorial divided by duplicates! You have five entries in 4/5, so you have $5!$ combinations of keys - but you have to take out $3!$ for the three zeros, and $2!$ for the two ones, which gives you $5!/(3!*2!) = 10 \mbox{ keys}$. For 3/4, it's $4!/(2!*2!) = 6\mbox{ keys}$. For 3/11, there are $11!/(9!*2!) = 55\mbox{ keys}$. For 2/40, there are $40!/(38!*2!) = 780\mbox{ keys}$.

It's now possible to prove why equidistant matrices would be pseudo-inverses of each other, but the proof for this part is left to the reader. $N$ slaves, $K$ keys - $N!/(K!(N-K)!)$

---

How do I make a solution matrix, then?

List out all the possible combinations of ones and zeros for $(N-R+1)$ ones, filling in the rest with zeros. Assign each unique combination to its own key, and boom! Generic solution matrix!

---

But what about my problem?

Your problem gives three different keyrings: the A-class, B-class, and C-class keyrings. In order to specify each set of keyrings, you need to append an additional set of restricting keys. These keys will be literally equal to the matches required for keys in each of the combinations. You can create an additional matrix to append to the problem to represent these combinations.

Each class's matrix is generated based on the number of that class required; everything else gets keys for that class. Then, remove sets of keys which are equivalently distributed to each participant.

The example you have provided is, quite frankly, too long to give a solution for in this answer. However, using this method, you can generate however many combinations and conditions you would like.

Answer 2

I came up with and solved this problem independently.

Let any set of riddles which should be enough to open the box be called sufficient. Define a nearly-sufficient set as one which should not open the box, but will become sufficient if any other riddle is solved.

In the case given, the nearly-sufficient sets are:

• Both A riddles, any B riddle, and any C riddle (24 ways);
• Both A riddles, and any five C riddles (6 ways);
• All four B riddles, and any two C riddles (15 ways);
• Any B riddle, and any five C riddles (24 ways).

Every set that is not sufficient is a subset of at least one nearly-sufficient set (as long as it is still possible, add riddles to the set without making it sufficient; when it becomes impossible, the result is nearly-sufficient).

For any nearly-sufficient set, there must be a key that none of the riddles in that set gives (otherwise you would be able to open the box after solving only that set of riddles). But every other riddle must give that key (otherwise it would not be possible to open the box even though the set of solved riddles would become sufficient). Call this key pivotal for that nearly-sufficient set.

No two nearly-sufficient sets can have the same pivotal key, so there must be at least one key for every nearly-sufficient set.

Now, assign a pivotal key for every nearly-sufficient set. If we solve an insufficient set of riddles, then it is a subset of some nearly-sufficient set. We have not acquired the pivotal key for that set, so we cannot open the box.

Is it possible for us to solve a sufficient set of riddles and not be able to open the box? If so, then we are still missing a key. That key is pivotal for one of the nearly-sufficient sets. If we do not have that key, then we have not solved any riddles that are not in that set. But this is impossible, because a sufficient set cannot be a subset of a nearly-sufficient set. So if we solve a sufficient set of riddles, then we will be able to open the box.

For the case in the question, there are 69 nearly-sufficient sets, so 69 keys are needed. For every nearly-sufficient set, all the riddles not in that set should give the corresponding key when solved.

Answer 3

Each set of keys fundamentally represents a set of possible combinations of choices that need to be an allowed condition. You add keys to deal with more possible situations, so as long as the number of situations that can occur is enumerable, then it should be possible to make a solution.

For example, in the original problem, you have the vizier with each of 4 slaves (4 cases) and 4 different cases of slaves (1,2,3), (1,2,4), (1,3,4) and (2,3,4). It may be somewhat non-trivial to determine which keys go where, but if the possible cases that need to work can be enumerated, then the keys can be assigned.

Answer 4

There is a generic approach for the optimal solution to the "Requires $M$ of $N$ slaves" problem. I'm not sure whether it's the one Emrakul describes, because TL;DR. It certainly doesn't need to be that complicated. Take any $M-1$ subset of the slaves. There must be a key which none of them have, but which all of the other slaves have. So $\binom{N}{M-1}$ locks are necessary and sufficient.

This can be extended in a suboptimal way to a wider class of problem featuring people who count as an integral number of slaves. For example, in your desired approach to the Vizier + 4 slaves problem, the Vizier counts as 2 slaves, so that's a 3 of 6 problem. But this is a suboptimal way of solving the wider class, because in the generic construction 3 of 6 would take 15 locks.

Your example problem:

• One level A riddle and two level B riddles.
• One level A riddle, one level B riddle, and two level C riddles.
• Two level B riddles and three level C riddles.
• All six level C riddles.

is trickier, because the third constraint means that B should be $\frac32$ C, so the second constraint means that A should be $\frac52$ C and the first constraint means that A should be 3 C. We have to double things up: C is two slaves, B is three slaves, A is six slaves, and you need 12 slaves to proceed. That means that you have one extra slave in the second case, but since there's no way of removing a single slave from the set that's not a problem. What is a problem is requiring $\binom{36}{11} = 600805296$ keys.

Answer 5

Instead of keys, have the questions enable access to pebbles. The final box requires you to tip a balance by putting a certain number of pebbles on the scale. A puzzle gives you pebbles essentially based on the score of the puzzle. For example, you want all these to be equivalent:

• One level A riddle and two level B riddles.
• One level A riddle, one level B riddle, and two level C riddles.

This tells me a B is worth two Cs.

• Two level B riddles and three level C riddles.

This tells me an A is worth 3 Cs

• All six level C riddles.

This actually makes you slightly inconsistent. Using C=1, B=2, and A=3 the four criteria you have are worth 7, 7, 7, and 6 points. So change the last rule to "all seven level C riddles" and you basically just need them to earn 7 pebbles somehow. Or keep it as-is but give them a one-pebble bonus for answering all the puzzles of a given level.

Simple to explain and to describe.