2
$\begingroup$

On another SE site (here ) I found the following puzzle.

Suppose we have, say, a hundred open locks, numbered from 1 to 100. The riddle is the following: you hold a key which opens one of the locks. However, the keys are numbered as well: if you show me the key, and show me that you can use it to open a lock, I will know exactly which key you own.

How can I convince you that I hold a key opening one of the locks, but without revealing to you which key it is? And even more, without revealing anything at all, except that I can open at least one of the locks?

The solution is as follows:

-You create two intertwined "circles of 50 locks". Namely, you attach lock 1 to lock 2, which you also attach to lock 3... which you attach to lock 49, which you attach to lock 50, which you attach to lock 1.
This gives you a circle of 50 locks in a chain. You do exactly the
same thing with the locks 51 to 100, except that the circle goes
through the first circle of locks.

-You hand me the intertwined circle of locks, and leave me for some time. To convince you, I must hand you back the two circles of locks, but separated.

I thought this would be a good puzzle to get my kids (10 and 12) thinking, and entertaining at the same time. I was absolutely sure there was no way they would get any close answer, but thought if I give them a ridiculously high incentive (an HTC Vive as a reward), then they'd stick at thinking about it and motivate them throughout the days to explore new avenues of thought.

There are actually two solutions I know of. One in the puzzle quote above, the other being the use of knots. (eg: Make a prezel style knot out of a chain of padlocks and then hand the observer the unknotted chain).

What my 2 sons came up with was the following (after about 2 days of hard thinking):

Invite all the other key holders. Lock all the locks and show them to the verifier. Then unlock all 100 locks.

Here is my dilemma. Do they get the HTC Vive or not? There are some objections to the above answer: 1) You don't necessarily have the contacts to the other key holders 2) One key holder may have two keys and you may have none.

Anyway I leave it to community consensus. :-)

$\endgroup$
  • $\begingroup$ The puzzle didn't even mention any other key holders, who's to say they exist? $\endgroup$ – Mike Earnest Mar 28 '18 at 13:29
  • $\begingroup$ @Mike Earnest Well, yes. It seems to me there's no perfect answer really. One can always come up with some objection. Even to the above legit answers (eg: could have borrowed a key, could have hidden a friend with key, etc). Where does one draw the line? Please add your comment as answer and let's see how the masses decide :-) $\endgroup$ – Sentinel Mar 28 '18 at 13:35
  • $\begingroup$ It proves that you are able to open a lock, one way or another. Isn't having a friend with a key that would lend it the same as having the key? $\endgroup$ – Florian Bourse Mar 28 '18 at 13:40
  • $\begingroup$ The question seems more convoluted than it needs to be. I place some blame on the wording if this was how it was given to anyone. In my mind, it should be stated that any unlocking must be done away from the verifier because the lock number gives away the key (and the verifier can at least determine which one you have in your hand based on seeing which one isn't in the remaining set of locks). I think this additional stipulation makes it clearer what's needed to prove the key without revealing it. $\endgroup$ – John Mar 28 '18 at 18:10
8
$\begingroup$

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 technicality. In a comment, you mentioned that even the canonical solution can not be called a perfect answer because of any number of objections:

could have borrowed a key, could have hidden a friend with key, etc

In both of these cases, you do indeed have a key at the moment you claim, even though it is temporary. There are other possible objections: maybe you picked the lock, maybe you broke the lock and somehow concealed the damage. But again, these all assume you have things not mentioned in the puzzle (lock picking skills, welding torches).

$\endgroup$
  • $\begingroup$ I am not sure what you are saying. From the point of view of any verifier, you could be concealing a midget key holder in your inner pocket. What precisely is your point? $\endgroup$ – Sentinel Mar 28 '18 at 23:26
  • 2
    $\begingroup$ I think Mike is saying what I often express in this way: In general, a puzzle solver is not given free license to invent their own rules or scenarios. Especially for puzzles not tagged "lateral thinking", the right answer to a puzzle will be the one that uses what the puzzle gave you or hinted at, without inventing facts, rules, or interpretations out of thin air to make a "solution" work. Puzzle posters can't close every loophole… and shouldn't have to. Your children's solution relies on inventing other key holders and a scenario where they're all available to participate, so fits poorly. $\endgroup$ – Rubio Mar 29 '18 at 14:58
0
$\begingroup$

First a review of the question context:

I don't know if this is exactly on topic here, or whether Parenting.SE would deal better with "My kids gave me an unexpected solution to my problem, should I reward them or tell them it isn't the one I thought of, so it's wrong?"

It seems you were prepared to buy the Vive given they found the correct answer, so lets assume the reward is arbitrary. It seems then to be a question of "Should I class an answer that is more lateral than intended still correct?", and that your puzzle had rather loose constraints. You can ask them then to try again with the amendment "You don't know where the other 99 keys are", or you can reward their problem solving via non-spatial methods, it's up to you how you value their methods compared to the expected one.

As to whether their solution is valid, since it isn't specified that your friend cannot interact with the other key holders, the friend you are trying to prove key possession to could simply ensure that anyone entering the room only possessed one key, thus if all 100 are open, you must also have one. Doing this without direct observation of the keys is non-trivial however:

To generalise, we could have one holder with 100 keys, the OP with one, and 98 others with none. It is impossible to force someone to use their second key, so impossible to determine that one person has two keys independently of the other guests. You must therefore ensure that each of the 100 has a key. Using the childrens method, each of the 100 would end up inviting the other 99, clearly not solving the problem...

$\endgroup$
  • 3
    $\begingroup$ yes but then each of the party member has to prove he owns 1 key without revealing it, should they all get the 2 chains of locks and separate them? $\endgroup$ – Florian Bourse Mar 28 '18 at 13:28

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.