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
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.
No comments:
Post a Comment