Monday, January 05, 2009

Security Codes

I was entering the four-digit security code to our house, and I realized that it doesn't end with an ENTER (E) key to accept it. The problem with that is you can keep pressing numbers until the right combination is found. Since most keypads use all ten digits (0-9), the total number of combinations should be $10^n$. However, it is the ENTER key that makes it so difficult.

Let D equal the number of digits for the security code. Let K equal the number of digits on the keypad.

For a binary keypad (0, 1) and a three-digit code, our set consists of (000E, 001E, 010E, 011E, 100E, 101E, 110E, 111E). Thus, we have at most $2^3 \times (3+1)$ possible keys to enter, where the plus one is for the ENTER key. Generally speaking, we'd have $K^D \times (D+1)$ possible keys to enter.

Without the ENTER key, we could keep pressing the keypad until all combinations have formed. The minimum number of keys required would be $K^D + D$.

So for a binary keypad, we'd have:





DStringKeys (wo/ E)Keys (w/ E)
10124
200110512
300011101001032
400001111001011010001980
500000111110001001010111011001101000036192

Thus, one only needs to know the string concatenations to be able to guess the right combination if no ENTER or code-stopper key is required.

Update: See De Bruijn Sequence and ProjectEuler #265 for a related problem.

No comments: