|
|
| Author |
Message |
gjedwards@gmail.com
science forum addict
Joined: 20 May 2006
Posts: 70
|
 Posted: Sun May 21, 2006 12:43 am Post subject:
fixing a burglar alarm
|
|
|
I can't remember the 4 digit code (from symbols 0 thru 9) to my burglar
alarm. It works by you typing in the 4 digits but it only needs to see
them in the right order - there's no 'start' as such.
In other words if you type the sequence 0,1,2,3,4,5, then you've
already tested 3 codes:
0123
1234
2345
The code does NOT have be made of unique digits.
Optimal strategy to find solution in shortest time?
Is it unique (other than permutations of the symbols, eg. swapping 1
with 2) ?
Any other insights?
Sorry if this is trivial and/or a well known puzzle. |
|
| Back to top |
|
 |
mensanator@aol.compost
science forum Guru
Joined: 24 Mar 2005
Posts: 826
|
| Posted: Sun May 21, 2006 12:58 am Post subject:
Re: fixing a burglar alarm
|
|
|
gjedwards@gmail.com wrote:
| Quote: | I can't remember the 4 digit code (from symbols 0 thru 9) to my burglar
alarm.
|
YOUR burglar alarm?
| Quote: | It works by you typing in the 4 digits but it only needs to see
them in the right order - there's no 'start' as such.
In other words if you type the sequence 0,1,2,3,4,5, then you've
already tested 3 codes:
0123
1234
2345
The code does NOT have be made of unique digits.
Optimal strategy to find solution in shortest time?
Is it unique (other than permutations of the symbols, eg. swapping 1
with 2) ?
Any other insights?
Sorry if this is trivial and/or a well known puzzle. |
|
|
| Back to top |
|
|
David Ames
science forum addict
Joined: 06 May 2005
Posts: 77
|
| Posted: Sun May 21, 2006 12:22 pm Post subject:
Re: fixing a burglar alarm
|
|
|
mensanator@aol.compost wrote:
| Quote: | gjedwards@gmail.com wrote:
I can't remember the 4 digit code (from symbols 0 thru 9) to my burglar
alarm.
YOUR burglar alarm?
It works by you typing in the 4 digits but it only needs to see
them in the right order - there's no 'start' as such.
In other words if you type the sequence 0,1,2,3,4,5, then you've
already tested 3 codes:
0123
1234
2345
The code does NOT have be made of unique digits.
Optimal strategy to find solution in shortest time?
Is it unique (other than permutations of the symbols, eg. swapping 1
with 2) ?
Any other insights?
Sorry if this is trivial and/or a well known puzzle.
|
Try alt.locksmithing if you want comments.
David Ames |
|
| Back to top |
|
|
gjedwards@gmail.com
science forum addict
Joined: 20 May 2006
Posts: 70
|
| Posted: Sun May 21, 2006 1:05 pm Post subject:
Re: fixing a burglar alarm
|
|
|
Well, it was my alarm (somebody else had reset the code) and I did find
the code by sitting there pressing buttons in order. It took about 20
minutes which was remarkably lucky because my not-well-thought-out
strategy could have taken much longer. Which led me to think about an
optimal strategy for the problem.
I don't think it's a trivial bit of code-breaking math, but I may be
wrong. |
|
| Back to top |
|
|
cbrown
science forum Guru
Joined: 02 Jun 2005
Posts: 371
|
| Posted: Sun May 21, 2006 6:54 pm Post subject:
Re: fixing a burglar alarm
|
|
|
gjedwards@gmail.com wrote:
| Quote: | I can't remember the 4 digit code (from symbols 0 thru 9) to my burglar
alarm. It works by you typing in the 4 digits but it only needs to see
them in the right order - there's no 'start' as such.
In other words if you type the sequence 0,1,2,3,4,5, then you've
already tested 3 codes:
0123
1234
2345
The code does NOT have be made of unique digits.
Optimal strategy to find solution in shortest time?
Is it unique (other than permutations of the symbols, eg. swapping 1
with 2) ?
Any other insights?
Sorry if this is trivial and/or a well known puzzle.
|
It's well-known (but not particularly trivial!); the solution is called
a de Bruijn sequence; see, e.g.:
http://en.wikipedia.org/wiki/De_Bruijn_sequences
http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html
It has length, in this case, of 10^4 + 3 (as there are 10^4 possible
4-digit codes).
By their construction, a de Bruijn sequence can be "wrapped around":
for example, if there were only two buttons, 0 and 1, and one only
needed to enter three codes, the 10-digit sequence:
0001110100
----------
000
001
010
011
100
101
110
111
can also be though of as a repeating loop or necklace of length 2^3= 8:
00011101.00011101.00011101.00011101....
The problem you describe has come up many times on sci.math, with
various add-ons (the lock times out for 5 seconds if an incorrect
pattern is entered, etc., etc.). Serahc on "lock" and "de Bruijn" in
google groups.
Cheers - Chas |
|
| Back to top |
|
|
Robert B. Israel
science forum Guru
Joined: 24 Mar 2005
Posts: 2151
|
| Posted: Sun May 21, 2006 7:07 pm Post subject:
Re: fixing a burglar alarm
|
|
|
In article <1148172219.561527.13760@y43g2000cwc.googlegroups.com>,
<gjedwards@gmail.com> wrote:
| Quote: | I can't remember the 4 digit code (from symbols 0 thru 9) to my burglar
alarm. It works by you typing in the 4 digits but it only needs to see
them in the right order - there's no 'start' as such.
In other words if you type the sequence 0,1,2,3,4,5, then you've
already tested 3 codes:
0123
1234
2345
The code does NOT have be made of unique digits.
Optimal strategy to find solution in shortest time?
Is it unique (other than permutations of the symbols, eg. swapping 1
with 2) ?
Any other insights?
|
What you're looking for is a de Bruijn sequence B(10,4), which will give
you a sequence of 10003 digits that contains each possible 4-tuple
exactly once. There are lots of them. See e.g.
<http://en.wikipedia.org/wiki/De_Bruijn_sequence>
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada |
|
| Back to top |
|
|
gjedwards@gmail.com
science forum addict
Joined: 20 May 2006
Posts: 70
|
| Posted: Sun May 21, 2006 8:24 pm Post subject:
Re: fixing a burglar alarm
|
|
|
|
Thanks! |
|
| Back to top |
|
|
gjedwards@gmail.com
science forum addict
Joined: 20 May 2006
Posts: 70
|
| Posted: Sun May 21, 2006 8:24 pm Post subject:
Re: fixing a burglar alarm
|
|
|
|
Thanks! |
|
| Back to top |
|
|
gjedwards@gmail.com
science forum addict
Joined: 20 May 2006
Posts: 70
|
| Posted: Sun May 21, 2006 8:25 pm Post subject:
Re: fixing a burglar alarm
|
|
|
|
Thanks! |
|
| Back to top |
|
|
gjedwards@gmail.com
science forum addict
Joined: 20 May 2006
Posts: 70
|
| Posted: Sun May 21, 2006 8:25 pm Post subject:
Re: fixing a burglar alarm
|
|
|
|
Thanks! |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Jan 08, 2009 11:11 pm | All times are GMT
|
|
Personal Loans | Loans and Credit Cards | Personal Loan | Car Accident Lawyer Los Angeles | Credit Cards
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
