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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.