blgentry
Member
This is a little problem I first conceived nearly two years ago. I've shown it to a number of smart people and no one has been able to solve it. I don't have a solution either, just the problem.
It has to do with safes (vaults) that have digital keypads. Sargent and Greenleaf is a major manufacturer of the locks for low to medium security safes, like what you'd find at someone's house. The manual for one of their digital keypads says something along the lines of: "If you open the lock many times per day, the keypad will eventually show wear, allowing an attacker to guess your lock combination."
So I got to thinking, if the attacker knew the exact digits used in the combination, how many different ones would he have to try to get the right one? This particular model of lock *requires* a six (6) digit passphrase (or combination, or secret, I dislike using the word combination because it has a meaning in mathematics. For the rest of this I will refer to it as the secret or the passphrase).
Please assume that the attacker is 100% sure of the digits used, but doesn't know what order to use them in or which ones to repeat. Maybe he used ultraviolet ink or something, but he is *sure*. Again, remember that the passphrase must be exactly six digits long and comes from a keypad with numbers 0 through 9.
Let's do the easy cases:
1. There are 6 digits in the pass phrase. The solution is easy: Each digit must be used once and all six must be used. The answer is 6! (six factorial).
2. There is only one digit. So that digit must be used 6 times, and the answer is, there is only one possibility for the passphrase.
3. There are two digits in the passphrase. Now things get interesting. I analyze this case by saying, "What passphrases are not valid?" In this case, you know you have to use both digits at least once. So the only passphrases that are not allowed are the ones that use only one of the digits and use it six times. Like if the digits were 2 and 5, you couldn't use 222222 or 555555 .
So the answer is 2^6 - 2 .
From here the cases for 3, 4, and 5 digits are beyond my ability to analyze. I have tried making a closed form solution, but all of my attempts have failed, as have the attempts of my friends, at least two of whom have degrees in math.
I would like to think that there is a closed form solution to this problem, and that furthermore, there is a closed form solution to the arbitrary problem:
Find the number of combinations of a set of digits N, taken M at a time, repeating digits as necessary to form a string of length S. So in our case above: N = 10, S = 6, and we are interested in cases where M = 1, 2, 3, 4, 5, and 6 .
I'm curious to see if this interests anyone else. I know it's of no practical value, but it still bothers me from time to time that I can't figure it out.
Brian.
It has to do with safes (vaults) that have digital keypads. Sargent and Greenleaf is a major manufacturer of the locks for low to medium security safes, like what you'd find at someone's house. The manual for one of their digital keypads says something along the lines of: "If you open the lock many times per day, the keypad will eventually show wear, allowing an attacker to guess your lock combination."
So I got to thinking, if the attacker knew the exact digits used in the combination, how many different ones would he have to try to get the right one? This particular model of lock *requires* a six (6) digit passphrase (or combination, or secret, I dislike using the word combination because it has a meaning in mathematics. For the rest of this I will refer to it as the secret or the passphrase).
Please assume that the attacker is 100% sure of the digits used, but doesn't know what order to use them in or which ones to repeat. Maybe he used ultraviolet ink or something, but he is *sure*. Again, remember that the passphrase must be exactly six digits long and comes from a keypad with numbers 0 through 9.
Let's do the easy cases:
1. There are 6 digits in the pass phrase. The solution is easy: Each digit must be used once and all six must be used. The answer is 6! (six factorial).
2. There is only one digit. So that digit must be used 6 times, and the answer is, there is only one possibility for the passphrase.
3. There are two digits in the passphrase. Now things get interesting. I analyze this case by saying, "What passphrases are not valid?" In this case, you know you have to use both digits at least once. So the only passphrases that are not allowed are the ones that use only one of the digits and use it six times. Like if the digits were 2 and 5, you couldn't use 222222 or 555555 .
So the answer is 2^6 - 2 .
From here the cases for 3, 4, and 5 digits are beyond my ability to analyze. I have tried making a closed form solution, but all of my attempts have failed, as have the attempts of my friends, at least two of whom have degrees in math.
I would like to think that there is a closed form solution to this problem, and that furthermore, there is a closed form solution to the arbitrary problem:
Find the number of combinations of a set of digits N, taken M at a time, repeating digits as necessary to form a string of length S. So in our case above: N = 10, S = 6, and we are interested in cases where M = 1, 2, 3, 4, 5, and 6 .
I'm curious to see if this interests anyone else. I know it's of no practical value, but it still bothers me from time to time that I can't figure it out.
Brian.