13
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by levels A, B, and C? $\endgroup$ – Aza May 15 '14 at 18:49
  • $\begingroup$ The general idea is that the level A riddles are harder, the level B riddles are moderately hard, and the level C riddles are easier. If you want it in terms of the vizier and his slaves, think of the level A riddles as viziers, the level B riddles as magistrates, and the level C riddles as slaves/guards. Each riddle, when solved, yields a set of "keys", and if you get all of them, you can unlock the next challenge. $\endgroup$ – Joe Z. May 15 '14 at 19:27
  • $\begingroup$ It's going to be hard for anyone to quantitatively measure the difficulty of a problem. At some point, there's an algorithm that solves this, and just the application of that algorithm will solve all puzzles. $\endgroup$ – Aza May 15 '14 at 19:32
  • 1
    $\begingroup$ @WendiKidd: I think this is on the border between math and puzzles and cs. Counting the number of each kind of puzzle solved is trivial in software. Determining a set of locks/keys that implement a specific requirement is in the arena of error-correcting codes. There are other configurations of hardware that can do clever things, which can make very neat puzzles. For example, if you want to open a gate if somebody has solved one puzzle out of three, put three padlocks in series to lock the gate. Now we have an additional piece of logic at our disposal. $\endgroup$ – Ross Millikan May 16 '14 at 3:59
  • 1
    $\begingroup$ @joe Having slept, I think I now understand. (Reading one of the answers also helped.) Your "without keeping track of what they've completed" turned the light on for me. You want a set of keys like in the original question (1, 2, 3, 4, 5, 6) and completing any of the puzzle sets listed above should result in the player having at least all 6 of those keys. Thanks for explaining; I've retracted my close vote. $\endgroup$ – WendiKidd May 16 '14 at 19:25
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is all good, but it only shows the case for one Grand Vizier and some number of slaves. I'm asking about a much more general case than that. $\endgroup$ – Joe Z. May 16 '14 at 17:26
  • $\begingroup$ @JoeZ. What other cases are you asking about, specifically, that isn't covered by this? If you want another Grand Vizier, just give each Grand Vizier one key the others don't have, and give the rest to the slaves. $\endgroup$ – Aza May 16 '14 at 17:27
  • $\begingroup$ The example case in my question has three classes of keyholders. $\endgroup$ – Joe Z. May 16 '14 at 17:30
  • $\begingroup$ @JoeZ. What do you mean by three classes of keyholders? I thought those were just metrics for puzzle difficulty? $\endgroup$ – Aza May 16 '14 at 17:32
  • $\begingroup$ Those "metrics for puzzle difficulty" also delineate classes of keyholders. $\endgroup$ – Joe Z. May 16 '14 at 17:34
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think the problem with this is that you describe the need for an enumeration, but the meat of the problem is in how to assign the keys so that each combination is satisfied but anything less isn't. $\endgroup$ – Joe Z. May 16 '14 at 2:28
  • $\begingroup$ If you can enumerate the possible combinations, then some derivation of keys should be able to match it. They keys just have to be assigned such that one combination is unique to each possible outcome. It may involve an extremely large number of keys to be able to do it, but it should be doable. I agree that a better answer would be one that describes precisely the number of keys that need to be involved, but that is far more difficult. $\endgroup$ – AJ Henderson May 16 '14 at 2:41
  • $\begingroup$ I'm still not sure what you mean by "one combination is unique to each possible outcome". That's basically what's stopping me here. $\endgroup$ – Joe Z. May 16 '14 at 2:43
  • $\begingroup$ So for example, using the vizier problem, because the vizeer always needs a slave but it can be any slave, each slave gets one of the same keys and the vizeer gets the rest, but if he needed two slaves, then you would need a set of keys that each slave had all but one of the keys that the vaizer didn't have and have each slave missing a unique key. It requires exponentially more keys to handle, but the situations that result in a win can be uniquely identified, so a formulation of keys can be formed. The keys can be made to only allow given situations by adding more and more keys. $\endgroup$ – AJ Henderson May 16 '14 at 2:48
  • $\begingroup$ I don't think my original explanation was very good though. Also if you have a problem where certain people prevent others from being able to move forward, then I'm not sure it is possible anymore. $\endgroup$ – AJ Henderson May 16 '14 at 2:49
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You could also use the numbers in Peter Taylor's answer, where A=6, B=3, C=2, and 12 points are needed. One case gives 13 points instead of 12, but that's fine because nothing is worth 1 point. $\endgroup$ – f'' Sep 13 '15 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.