Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Password lock

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.

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 957

Re: Password lock

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,


240 books currently added on Goodreads

Offline

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

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: Password lock

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,

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 957

Re: Password lock

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)


240 books currently added on Goodreads

Offline

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

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: Password lock

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.

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

Hi;

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


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 957

Re: Password lock

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


240 books currently added on Goodreads

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 957

Re: Password lock

Read the thread!

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


240 books currently added on Goodreads

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 957

Re: Password lock

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.


240 books currently added on Goodreads

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

Nehushtan wrote:

Yes.

Ok...sorry about that.

Nehushtan wrote:

No.

Oh, I see.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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

smile

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


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 957

Re: Password lock

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)


240 books currently added on Goodreads

Offline

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

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: Password lock

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 smile

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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! sad


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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! smile

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)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: Password lock

Phrontister, you are a genius!!!

Many thanks to all of you, though!

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Password lock

Phrontister, you are a genius

And so young too... only 27.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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

CPZyHIE.jpg

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


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

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

Nehushtan
Member
Registered: 2013-03-09
Posts: 957

Re: Password lock

Super job! up


240 books currently added on Goodreads

Offline

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

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Password lock

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.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

Board footer

Powered by FluxBB