Password lock

anna_gg · 2016-01-30 21:48:54

There is a lock with the combination between 111-333 (3 digits, each with values 1, 2 or 3, duplicates allowed, of course).
The lock is defective and we could use only two digits to open the lock. For example, if the password is 123, the lock opens when you try 1*3, or *23, or 12*. Compose a strategy to find the minimum number of tries to open the lock, under the worst situation and prove that this strategy is optimal.

Nehushtan · 2016-01-31 03:24:59

anna_gg wrote:

For example, if the password is 123, the lock opens when you try 1*3, or *23, or 12*.

Do you mean any one of 1*3, *23, 12* can open the lock, or just one of them will?

If any one of them works,

anna_gg · 2016-01-31 04:01:16

Any of them, but the "any" (asterisk or wildcard) digit must be in the correct position. For example 231 won't open the lock, but 223 will.

Nehushtan wrote:

anna_gg wrote:
For example, if the password is 123, the lock opens when you try 1*3, or *23, or 12*.
Do you mean any one of 1*3, *23, 12* can open the lock, or just one of them will?
If any one of them works,

Nehushtan · 2016-01-31 07:26:42

In other words, if the password is 123, then all of the following will open the lock, right?

[list=*]
[*]123, 223, 323, 113, 133, 121, 122[/*]
[/list]
My question was whether the wildcard could be in any position, or whether it was in a definite (but unknown) position. In the former case, the lock will open for any of the above seven combinations; in the latter case, then, for example, if the wildcard is in the centre, only 113, 123 and 133 will open the lock.

Last edited by Nehushtan (2016-01-31 07:34:16)

anna_gg · 2016-01-31 08:04:59

Right, all 7 combinations will open the lock.

Nehushtan wrote:

In other words, if the password is 123, then all of the following will open the lock, right?
[list=*]
[*]123, 223, 323, 113, 133, 121, 122[/*]
[/list]
My question was whether the wildcard could be in any position, or whether it was in a definite (but unknown) position. In the former case, the lock will open for any of the above seven combinations; in the latter case, then, for example, if the wildcard is in the centre, only 113, 123 and 133 will open the lock.

phrontister · 2016-02-02 17:20:00

Hi;

Last edited by phrontister (2017-02-26 23:17:51)

Nehushtan · 2016-02-02 19:41:46

That's the same minimum number as in my method (post #2).

phrontister · 2016-02-02 20:01:01

True, but you've got the wild as the third digit even though its actual position is unknown. That leads to many permutations other than the minimum number in your post.

Nehushtan · 2016-02-02 20:23:59

Read the thread!

Last edited by Nehushtan (2016-02-02 20:56:26)

phrontister · 2016-02-02 21:38:09

Hi Nehushtan;

Nehushtan wrote:

Read the thread!

I may have misunderstood something here.

Are you saying that if the correct combination is 123 (with wild's position unknown), and you entered 111, 112, 131, 132, 211, 212, 213, 221, 222, 231, 232, 233, 311, 312, 313, 321, 322, 331, 332, and 333 (none of which will open the lock, as I understand it) before using one of the seven successful combinations you listed in post #5, that your method still holds?

Last edited by phrontister (2016-02-02 21:47:29)

Nehushtan · 2016-02-02 21:56:23

phrontister wrote:

I may have misunderstood something here.

Yes.

phrontister wrote:

Are you saying that if the correct combination is 123 (with wild's position unknown), and you entered 111, 112, 131, 132, 211, 212, 213, 221, 222, 231, 232, 233, 311, 312, 313, 321, 322, 331, 332, and 333 (none of which will open the lock, as I understand it) before using one of the seven successful combinations you listed in post #5, that your method still holds?

No.

phrontister · 2016-02-02 22:06:40

Nehushtan wrote:

Yes.

Ok...sorry about that.

Nehushtan wrote:

No.

Oh, I see.

phrontister · 2016-02-03 01:07:39

Hi Nehushtan;

Leaving aside the theoretical approach for a bit, I'd now like us to put your method to a practical test...just to dispel any doubts I may have about it working.

I happen to have a combination lock identical to anna_gg's, but unfortunately I don't know the code to open it. So I'd like you to post, in this thread, the codes that will open the lock in a number of tries not exceeding the maximum number you mentioned in posts 2 and 11.

Now, I should let you know in advance that this is a tricky little lock that employs strict avoidance tactics to ensure a worst-case scenario - just like the puzzle's lock!

You can post any number of codes at a time, their quantity not exceeding the maximum number you've stated...although, just out of curiosity should that maximum be reached without success, we could continue until the lock is opened to see how many extra tries it may take. Up to you.

I'll try the codes on the lock in the order that you post them, and then respond with progress reports about their success (or otherwise) as we go.

Your turn...

Last edited by phrontister (2016-02-03 01:17:49)

Nehushtan · 2016-02-03 03:02:49

Sigh.

Okay, for people who still don't get it...let's just suppose the password is 133.

Person A comes along and tries to open the lock. They don't know the password but they assume the first digit is 3. So they go through all the combinations with fist digit 3: 311, 312, 313, 321, 322, 323, 331, 332, 333. The last one works. If they had tried it earlier they'd have opened the lock sooner. But these are the only combinations with first digit 3, so it is impossible to fail to open the lock after 9 tries (unless you're forgetful and repeat an already tried combination).

Person B comes along and thinks they can do better than A by assuming the first digit is 2. They go 211, 212, 213, 221, 222, 223, 231, 232, 233 – and find that they can't do better than the first person. The only way they can do it faster is by being a luckier guesser with the other two digits – but even without luck, the lock can still be opened after 9 tries at the very most.

Along comes person C and says, "I'll take the first digit to be 1." But this is just a fluke: they just happen to guess the first digit correctly. This way they can open the lock after at most four wrong tries (111, 112, 121, 122); the next one is bound to open the lock. So it is at most 5 steps for this lucky person.

This shows that by fixing the first digit and trying combinations for the other two, you can open the lock after no more than 9 steps. You can try any of 1, 2, 3 as the fixed first digit. If you're lucky and are correct with this digit, you should be able to open the lock after no more than 5 steps, but even without luck, and your guess for the first digit is wrong, you still shouldn't take more than 9 steps to open the lock.

Last edited by Nehushtan (2016-02-03 03:10:00)

anna_gg · 2016-02-03 03:30:34

I think Phrontister's strategy in post #6 is a good starting point, but I believe (though I cannot prove it!!) that it can be done in 5 guesses, if you pick some other sets instead of the triplets. Maybe this way we manage to eliminate all 6 of the remaining combinations.
Can anyone write a program to test all possible combinations of 5 guesses (from the total of 27) - I think they are 80730 - to see which 5 will finally open the lock? Of course, I may be wrong

phrontister · 2016-02-03 04:13:38

Hi Nehushtan;

Thanks for your explanation...I finally got it! Your method works perfectly well.

I'm very sorry about having dragged you through this for so long before the penny dropped for me!

phrontister · 2016-02-03 17:17:07

anna_gg wrote:

...it can be done in 5 guesses, if you pick some other sets instead of the triplets. Maybe this way we manage to eliminate all 6 of the remaining combinations.

I tried a dozen or so combinations, and they all worked like the triplets in eliminating 21 options as long as they contained, in total, three 1's, three 2's and three 3's. The six remaining options in my tries didn't appear to be able to eliminated other than singly.

Yes, there are 80,730 (only) combinations of 5 guesses from the total of 27 - and I've saved the list in Excel and M - but I haven't been able to devise a program to do what we need.

Other numbers of guesses and combinations:
6 guesses from 27 options = 296,010 combinations;
7 guesses from 27 options = 888,030 combinations;
8 guesses from 27 options = 2,220,075 combinations;
9 guesses from 27 options = 4,686,825 combinations...which are very quickly reduced by Nehushtan's strategy and mine.

Last edited by phrontister (2016-02-04 03:03:05)

phrontister · 2016-02-04 02:58:08

Well, surprise, surprise! Here I was thinking that 9 would win, but it looks like 5 wins...as Anna thought it would.

I found 54 different combinations (listed below) that 'will' open the lock on the fifth try.

I say 'will', because I haven't tested them all...although the 10 random combinations I tried all worked. The other 44 should too, because all 54 were found by the same program.

Each set of codes will open the lock irrespective of the order in which they're tried.

111	122	212	221	333
111	122	233	312	321
111	123	213	221	332
111	123	232	313	321
111	132	212	231	323
111	132	223	312	331
111	133	213	231	322
111	133	222	313	331
111	222	233	323	332
111	223	232	322	333
112	121	211	222	333
112	121	233	311	322
112	123	213	222	331
112	123	231	313	322
112	131	211	232	323
112	131	223	311	332
112	133	213	232	321
112	133	221	313	332
112	221	233	323	331
112	223	231	321	333
113	121	211	223	332
113	121	232	311	323
113	122	212	223	331
113	122	231	312	323
113	131	211	233	322
113	131	222	311	333
113	132	212	233	321
113	132	221	312	333
113	221	232	322	331
113	222	231	321	332
121	132	213	322	331
121	132	222	231	313
121	133	212	323	331
121	133	223	231	312
121	212	233	313	332
121	213	232	312	333
122	131	213	321	332
122	131	221	232	313
122	133	211	323	332
122	133	223	232	311
122	211	233	313	331
122	213	231	311	333
123	131	212	321	333
123	131	221	233	312
123	132	211	322	333
123	132	222	233	311
123	211	232	312	331
123	212	231	311	332
131	212	223	313	322
131	213	222	312	323
132	211	223	313	321
132	213	221	311	323
133	211	222	312	321
133	212	221	311	322

anna_gg wrote:

Compose a strategy to find the minimum number of tries to open the lock, under the worst situation and prove that this strategy is optimal.

My strategy was to do a brute force search of the 80,730 possible combinations of 5 choices from 27 (the maximum number of different guesses possible), which was successful. To make sure that 5 was the minimum number, I also tried 3 and 4, but no luck there. Not very elegant; but then, neither am I!

I think a good strategy now would be for the lock operator to memorise one of the solutions, and here I'd recommend {112,121,211,222,333} as being one of the easier sets to remember, because it comprises the two triplets {2,2,2} and {3,3,3}, and the three permutations of {1,1,2}.

Having taken so long to properly understand both the problem and Nehushtan's method (and also because there are so many solutions!), I feel a little uneasy about the result, so someone please check a few of the combinations and let me know how they performed.

Thanks!

Last edited by phrontister (2016-02-04 03:17:09)

anna_gg · 2016-02-04 10:06:28

Phrontister, you are a genius!!!

Many thanks to all of you, though!

Last edited by anna_gg (2016-02-04 10:07:09)

bobbym · 2016-02-04 10:47:56

Phrontister, you are a genius

And so young too... only 27.

phrontister · 2016-02-04 11:16:18

Thanks! I'll take off my dunce cap, then!

Last edited by phrontister (2017-02-26 23:15:08)

phrontister · 2016-02-04 22:17:20

Hi;

Here are images of the 54 solutions, displaying one solution per row.

The 5 tries were applied in ascending order, and the images display the progress.

Last edited by phrontister (2017-02-26 23:14:14)

Nehushtan · 2016-02-05 01:07:27

Super job!

phrontister · 2016-02-05 03:31:17

Thanks!

I generated the list of 80730 combinations in M and pasted it into an Excel spreadsheet, which I used for the rest. That was the least time-consuming option for me.

Math Is Fun Forum

#1 2016-01-30 21:48:54

Password lock

#2 2016-01-31 03:24:59

Re: Password lock

#3 2016-01-31 04:01:16

Re: Password lock

#4 2016-01-31 07:26:42

Re: Password lock

#5 2016-01-31 08:04:59

Re: Password lock

#6 2016-02-02 17:20:00

Re: Password lock

#7 2016-02-02 19:41:46

Re: Password lock

#8 2016-02-02 20:01:01

Re: Password lock

#9 2016-02-02 20:23:59

Re: Password lock

#10 2016-02-02 21:38:09

Re: Password lock

#11 2016-02-02 21:56:23

Re: Password lock

#12 2016-02-02 22:06:40

Re: Password lock

#13 2016-02-03 01:07:39

Re: Password lock

#14 2016-02-03 03:02:49

Re: Password lock

#15 2016-02-03 03:30:34

Re: Password lock

#16 2016-02-03 04:13:38

Re: Password lock

#17 2016-02-03 17:17:07

Re: Password lock

#18 2016-02-04 02:58:08

Re: Password lock

#19 2016-02-04 10:06:28

Re: Password lock

#20 2016-02-04 10:47:56

Re: Password lock

#21 2016-02-04 11:16:18

Re: Password lock

#22 2016-02-04 22:17:20

Re: Password lock

#23 2016-02-05 01:07:27

Re: Password lock

#24 2016-02-05 03:31:17

Re: Password lock

Board footer