Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Like Looking for a PIN in a Hamiltonian

Date: 10/27/2011 at 05:08:59
From: Michael
Subject: difficult PIN code combinatorics

Hi,

We have an electronic PIN code for our door. It requires 4 numbers, 0 - 9.

The device only checks the last 4 numbers entered. So if the code is 4567,
it will open the door even when 1234567 is entered.

Logically, to try and go through all numbers, if the last number is the
correct one, it would require 10,003 key presses: 4 digits for the first
code plus 9,999 additional codes.

My question is: How do you find out if it is even possible to enter 10,003
digits without entering duplicates? If this is possible, how many
different such codes would there be? If it is not possible, how many
digits are needed to enter all possibilities?

Though I'd appreciate a solution, I would be even happier if you could
just tell me how to go about solving this question. I don't know where to
start with such a problem.

Thank you very much.




Date: 10/27/2011 at 22:39:52
From: Doctor Vogler
Subject: Re: difficult PIN code combinatorics

Hi Michael,

Thanks for writing to Dr. Math.

I would consider this to be a question about graph theory. In graph
theory, a "graph" is a set of points or nodes or "vertices," together with
some links or "edges" that connect some of the vertices. If the subject is
new to you, then you might want to search our archives for a few problems
dealing with graphs and graph theory, or look on the Internet for an
introduction to the subject. For a start, you might look at the Wikipedia
articles on the subject:

    http://en.wikipedia.org/wiki/Graph_theory 
    http://en.wikipedia.org/wiki/Graph_%28mathematics%29 
    http://en.wikipedia.org/wiki/Directed_graph 

In your case, you have 10,000 different four-digit codes, and by punching
a new digit, you get from one code to another code. If you make a vertex
for each code and for each new digit that you might try at each code, and
you connect them with a directed edge to represent the new four-digit code
that this takes you to, then you will have a directed graph (or "digraph")
with 10,000 vertices and 100,000 directed edges.

In order to make it a simple graph, let's remove the 10 edges that go from
a code to itself when the code has all four numbers the same. Then we have
a strongly-connected simple directed graph with 10,000 vertices and 99,990
directed edges.

What you want is a path through this graph that touches every vertex
exactly once without repeating any. That's called a Hamiltonian path:

    http://en.wikipedia.org/wiki/Hamiltonian_path 
    http://en.wikipedia.org/wiki/Hamiltonian_path_problem 

It turns out that it is, in general, not easy to determine if a graph even
has a Hamiltonian path.

So what do we do? Simplify, simplify, simplify!

First, see if you can answer your problem if you had two-digit or
three-digit combinations (instead of four) and there were only two or
three or four different possible digits (instead of ten). Start with 2 and
2, so that you only have four vertices. Connect them up so that you have a
picture of your digraph, and find a Hamiltonian path or prove that there
isn't one. With only four vertices, this shouldn't be hard.

But maybe 2 and 2 is a bit *too* simple. Then try 2 and 3, and 3 and 2, in
which case you will have 9 and 8 vertices, respectively. Solve the problem
again. Try increasing those numbers slowly and answering your question
each time, and look for patterns as you go. If you find that you can get a
Hamiltonian path in the same (or a similar) way each time, then try to
prove that it works in the 4 and 10 case, too. Or, if you find that you
can prove that there is no Hamiltonian path in the same (or a similar) way
each time, then try to use those same ideas to prove that there is no
Hamiltonian path in the 4 and 10 case.

Good luck! It seems like an interesting problem. If you have any questions
about this or need more help, please write back and show me what you have
been able to do, and I will try to offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 10/28/2011 at 07:27:48
From: Michael
Subject: Thank you (difficult PIN code combinatorics)

I have never even heard of graph theory, but what you told me looks like
the correct way to go. Thank you very much for such a detailed explanation
and the effort you have put into your research for this question. I will
definitely have a look at this.

But if anyone does come up with a solution for this, please let me 
know. :-)

Michael



Date: 10/29/2011 at 15:51:48
From: Doctor Vogler
Subject: Re: Thank you (difficult PIN code combinatorics)

Hi Michael,

Doctor Douglas pointed out to me that there is a classic sequence that
solves precisely this problem. It is known as the de Bruijn sequence. See

    http://en.wikipedia.org/wiki/De_Bruijn_sequence 

In your case (4 and 10), look at this expansion:

    http://www.hakank.org/comb/debruijn_k_10_n_4.html 

Let me know if you have any more questions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/