# Tag Info

121

9 days. Every day, each prisoner with an unknown key passes it to the next cell to the left (or to the next guy in alphabetic order, sentence length, age... w/e, just agree on the order on that first day). Since they know where in the order the owner of their own key is (relative to them), they know on which day to expect their key - they get to keep that, ...

32

The probability is $1/2$. We have a permutation that maps each box to the box whose key it contains. Once we open a box, we can open the box it maps to. So, we can open all the boxes exactly if there is no all-steel cycle. Label the boxes $1$ through $100$. We denote the permutation in cycle format like $(31)(542)(6)$. To make this canonical, write each ...

32

If every prisoner has a number assigned, that each other prisoner knows, they can leave the prison after 13 days. On day $i$, prisoner $i$ gives his key to the person that holds his key, it is returned on day $i+1$. So, at the start of day 12 every prisoner is holding the key he had in the beginning, and he knows who's key it is. On day 12 they hand over all ...

27

Using only combinations of either single or double button presses: Using 1 press Using 2 presses Using 3 presses Using 4 presses Using 5 presses Total For anyone curious as to my internal process of coming up with these values, I made a quick chart of each type of press combo and how many variations there were for each type, with x indicating it has ...

21

17

I don't know if this works, necessarily, but I think it does. Organize the prisoners $A$ through $J$. On day 1, prisoner $A$ puts his key outside the cell of whoever has his key (we'll call him $A_2$). Nobody else moves keys. On day 2, $A_2$ returns the key he receives to prisoner $A$'s cell. Day 3 starts, and prisoner $B$ puts his key outside of $B_2$'s ...

15

You have all the possibilities using only single button press Then the possible combinations using one pair are: Then you have the possibilities using multiples pairs: Adding all cases, you get: Which is the expected answer from the question!

14

The best solution I've found has 7 locks. The Grand Vizier has keys 1, 2, 3, 4, 5, 6. Slave 1 has keys 1, 2, 3, 7. Slave 2 has keys 1, 4, 5, 7. Slave 3 has keys 2, 4, 6, 7. Slave 4 has keys 3, 5, 6, 7. A couple of things simplify the deduction of this puzzle: If the Grand Vizier has every key but one, and every slave has the missing key, that reduces ...

13

The first day, "while no one is watching", a prisoner takes his key and tries it in the lock of each of nine other cells. The prisoner swaps his key for the one that is in the cell that opens. The prisoner then tests that key in the remaining eight doors, and swaps again. The prisoner repeats the process for the remaining seven etc. The first night the ...

10

As @JonTheMon said, there are $5!=120$ possible combinations for the keys. The correct ordering must be in this list: 1: ABCDE 2: ABCED 3: ABDCE 4: ABDED 5: ABECD 6: ABEDC ... 115: EDABC 116: EDACB 117: EDBAC 118: EDBCA 119: EDCAB 120: EDCBA So, before you start asking questions, create this list since it is probably too hard to do on the fly. Then, go ...

10

It then dawns on me: Old answer: I enter because I believe

10

Well, let's see. It's possible for 1 to 5 buttons to be pushed to create a combination, so let's calculate the number of possibilities for each individually, assuming you can pick the order of the buttons to be pushed. 1 Button 2 Buttons 3 Buttons 4 Buttons 5 Buttons Total

9

You can do it with $2N$ locks. Make one chain $123...N$. If we see $123...p$ on the wall, we know the artifact was taken by $p$ or $p+1$. Make another chain $246...N13...(N-1)$. Added: you can do it with $N+3$ locks. Make the $123...N$ chain as above. Then make a three lock chain. Give a key to the first lock to every even number, a key to the last ...

9

Just in case it's possible to put the keys in specific locations in a cell... Each prisoner draws a map of the prison on his floor (or a grid and each prisoner chooses a square that everyone else knows about, or a set of unique locations in the cell, etc). On day one, each prisoner puts his current key in the cell of the person who has his actual key, in ...

9

2 days Day 0 (strategy discussion) Each prisoner is given a number. One prisoner is chose. In his cell is designed a 10 x 10 grid (using chalk if available, other wise distance from the walls). Day 1 Each prisoner brings the key in they were given to the designated cell. They place the key in the row corresponding to their number and the column ...

9

Kendall Frey's answer gives an example of how to do this with 7 locks, this proves that minimum is not greater than 7. Unfortunately, Kendall Frey's answer does not give an answer to the question what exactly is the minimum number of locks. I met a similar puzzle, and can take the honour to prove that 7 is the minimum. To do this I need to add one more ...

9

The question doesn't place any constraints on the design of the box, so we can exploit that to get a 6-lock solution. So we can either handle the two use cases with two lids, each covering half of the top of the box, or we can have one lid with a set on locks on one side and a set of locks on the other side, such that the locks on the side we're not ...

9

It sounds like the code is one of the following Because So the strategy could be

8

Definitions Consider a lock $L$ consisting of $m$ wheels, where the $i$th wheel has $k_i$ digits (assume $k_i\geq 2$). I will use the notation $L=\{k_1,k_2,\ldots,k_m\}$. The number of combinations $L$ can be set to, which I call the size of $L$ which I write as $|L|$, is simply the product of the $k_i$: $$|L|=\prod_{i=1}^m k_i$$ The worst-case number ...

8

8

Your children's solution is pretty certainly invalid. The puzzle's constrains are clear: you have one key which opens one of the locks, and you must convince me that you have one key without revealing to me which one it is. There is no mention of any other key-holders, so any valid solution must not be contingent on their existence. This is not a ...

7

The limit for n is Because

7

Reasoning... The digital sum of the 5th factorial is 11! = 9, not 36 since you must then add 3+6. The only possible combinations to get 9 as digital sum I can get is 4,7,7,9, therefore 7 must be the numer repeating, leading to only two possible solutions. You can check both and open the door

7

The answers above all seem to rely on having access to the locks, and everyone seems to have forgotten about the numbers. The answer below works so long as none of the numbers are 0 (though you could probably alter it a bit to have it function even then).

7

I believe the salesman may be underestimating the possibilities. In addition to Excited Raichu's 325 arrangements there are the following possibilities: 1) 2) 3) 4) So the total could be at least

6

Trenin's answer simply lists all the permutations in alphabetical order and does a binary search. It works, with the only drawback that memorizing (or computing on the fly) the index of all the possibilities is difficult, and that it assumes that the guards can handle questions like "Is ABDCE alphabetically before ACDBE?" Here's a method that asks only ...

6

This solution is for revenge! Warning: it's long and assumes mathematical maturity. I don't think anyone will even read it all. I seriously hope someone else posts an elegant solution. But I had to post this, because this problem is Putnam 2013 B5, which I failed to solve during the test despite working on it for an hour. I never looked at a solution, so ...

6

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 ...

6

Well, I spent a lot of time to make this out. But now I have got the solution ready. It's not spoilerware, because it's too long (moderation, anyone?) But first I will restate a bit simpler version of 270(269?) transmissions' solution, to get those of you, who didn't get it, into the parcel business. I use term "delivery score" (ds) as amount of parcels a ...

6

I found two solutions. I numbered the keys and locks from 1 to 9 and built a simple matrix: A "0" means that the key would not fit into the corresponding lock. A "1" means that the key fits. Then, a -1 means that a key would fit, but that the lock is already occupied by another key. So my solutions would be: and

Only top voted, non community-wiki answers of a minimum length are eligible