# Safe Combination Math Challenge



## blgentry (May 23, 2008)

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.


----------



## Stefan (May 23, 2008)

blgentry said:


> I know it's of no practical value


What? Only a few paragraphs earlier you yourself mentioned one!


----------



## malcolm (May 24, 2008)

3 digits:
The sequences we are not allowed are 111111, 222222,333333, sequences made just of 1 and 2, 2,3 or 1,3.
The number of ways to choose a sequence with just 1,2 is 2^6, likewise for 2,3 and 1,3. So the total for 3 digits is 3^6 - 3 - 3*(2^6) = 534. But we have included with 1,2 sequence 111111 and 222222 and so on, so we must subtract 6 because we have already counted these. so the answer for 3 is 528.

4 digits: This time we are not allowed 111111, 222222,333333, 444444 or sequences, totaling 4C1.
a)And 1,2,3 1,2,4 1,3,4 2,3,4 The number of these is 4C3 = 4.
In a the number of ways of making a sequence is 2^6, and in b) it is 3^6.
So our answer for 4 is 4^6 - 4C1*1^6 - 4C3 * 3^6 = 1176. Now we must subtract 12 because we have counted the single digit sequences more than once in part a). Then, we have counted all the sequences with just 1,2 etc twice each. There are 64 combinatons of each one, so we must subtract 4C6*64 from our answer, giving 204.

5 digits:
There are 5! ways of arranging 5 digits, and we have 6 places to put the last digit. However, given any sequence, eg 112345 there are two ways to make it, either having the required digit first, or the surplus one first. So we must use (5!*6)*5/2 = 1800.

This gives me a total of 1+62+528+204+1800+720 = *2595*. Although I probably made a mistake somewhere.


*Trying other ways, unsuccessfully.*
Got the following, but can't work out what I need to subtract for counting numbers twice.
5 digits is likewise 5^6 - 5C1*1^6 - 5C4*4^6 =

3 digits: 
a)Let them be 1,2,3. Then all 3 must be used, and there are 3! ways of arranging them.
b)Now, 3 more digits of 1,2,3 with no restrictions must be placed in the gaps between these numbers. Now, let us express the combination in 1s and 0s, the 1s are the digits we placed in a). So we have a sequence of 6 1s and 0s, with 3 1s and 3 0s, giving us 6C3 combinations = 20 possible sequences. When we replace the 0s with the 1s, 2s, and 3s, We have 3 choices for the first, 3 for the second and 3 for the third, so 3^3=27. 
So there are 6*20*27 combinations for 3 digits, totaling 3240.
Got lost there, because I have counted some twice.. Can anyone figure out what to do from there?


----------



## Stefan (May 24, 2008)

1, 62, 540, 1560, 1800, 720


----------



## malcolm (May 24, 2008)

How did you get 3 and 4 Stefan? My 3 is close, but my 4 is way off.


----------



## Lucas Garron (May 24, 2008)

A quick simulation agrees with Stefan (also note that sum[stefan[n]*[10 choose n], n, 1, 6] = 10^6). Of course, right after this, I did what any sensible mathematician would do, and cheated.
It seems that Stirling numbers of the second kind are haunting me. 
(Funny thing is, I never see them coming when I should.)

So yes, that's _m!*S(n, m)_ (which I hope is now obvious enough from the definition of S(n,m)).

EDIT: That's m!*Sum[((-1)^(1+x)*(m^(n-1)-(m-x)^(n-1)))/((m-x-1)!*(x!)),{x, 1, m-1}], according to results from my last encounter with these numbers. I don't think it gets anymore closed-form than that, if you're not willing to use something equivalent to a Stirling-function in your expression.

EDIT 2: Stefan reminded me in a post down there: I should probably mention that n = string length, m = number of distinct digits.


----------



## badmephisto (May 24, 2008)

Lucas you totally ruined it. anyway, (as Stefan probably figured out) its not hard to imagine a 5 liner that generates the solution to the problem. The real trick was coming up with the formula, which I am not going to try anymore because I saw the solution... 

Funny how such simple problems in math sometimes have such complex solutions


----------



## blgentry (May 24, 2008)

StefanPochmann said:


> blgentry said:
> 
> 
> > I know it's of no practical value
> ...



Are you referring to the closed form solution that I was seeking as being "practical" ? If so, I guess a mathematician would have to say that. 

Otherwise, I must have missed what you saw in my posting.

Brian.


----------



## blgentry (May 24, 2008)

Thanks for all the replies!  In no particular order:

Malcom: I tried reasoning along the lines that you did, but I got mired down in the details and couldn't come up with reasonable answers. Plus I was searching for a closed form solution, as opposed to simple numbers, so as it got more and more complicated I convinced myself that I was going down the wrong path, as I expected the solution to have some elegance to it.

Stefan: If you wrote a computer program to solve the 6 cases, I'm impressed. I've thought of doing it myself, but I really wanted a symbolic closed form solution, as opposed to being interested in the numbers themselves. So you get some points for having done that so quickly and seemingly correctly. If you wrote a closed form solution you get major points, except you didn't share it. Share and full points will be awarded. 

Lucas: Even though you "cheated", you get full points for having written out the closed form solution. MY GOD is it ugly, but it's symbolic and works for all cases (though I haven't verified that and do not plan to.) 

I don't understand your notation completely though. The last part says:

,{x,-1+m}]

Is that supposed to mean "sum this using x as the variable using the values (-1) through m." ? Or am I missing what x is used for?

I also have zero clue how you figured this out. It's similar to the "explicit formula" given on that wikipedia page. I guess you figured out what symbols to plug into that formula to come up with your solution. Obviously I'm no mathematician.

Thanks again. This was really fun reading everyone's responses. 

Brian.


----------



## Lucas Garron (May 25, 2008)

blgentry said:


> ,{x,-1+m}]


Uh, that means "for values of m [beginning with 1] up to m-1." Lemme fix that in the original post.



blgentry said:


> It's similar to the "explicit formula" given on that wikipedia page. I guess you figured out what symbols to plug into that formula to come up with your solution.


Indeed. I was having trouble generating the general formula recursively, so I figured it out from Wikipedia. I was trying to sum some infinite expressions -oddly enough, this didn't help enough for full simplification, though I could prove alternately that the solution was quite simple. 
(See my solution to problem 9 of the MathCamp 2008 quiz.)

I really recommend considering _m!*S(n, m)_ the closed form, though


----------



## Stefan (May 25, 2008)

badmephisto said:


> anyway, (as Stefan probably figured out) its not hard to imagine a 5 liner that generates the solution to the problem.



I used one one-liner per case, here's case 4:
perl -e "for(1..999999){$x+=/[1-4]{6}/&&/1/&&/2/&&/3/&&/4/}print $x"



blgentry said:


> Are you referring to the closed form solution that I was seeking as being "practical" ? If so, I guess a mathematician would have to say that. Otherwise, I must have missed what you saw in my posting.



No, I mean practical if you want to decide whether you should try breaking your left neighbour's code or your right neighbour's.



Lucas Garron said:


> I did what any sensible mathematician would do, and cheated.



That's what I then did, too. Actually I copied my numbers from there.



blgentry said:


> 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 .



Notice the integer sequences website provides the answers as a two-dimensional triangle. Makes sense, as your parameter N is useless, the answer only depends on S (and M).


----------



## blgentry (May 25, 2008)

StefanPochmann said:


> I used one one-liner per case, here's case 4:
> perl -e "for(1..999999){$x+=/[1-4]{6}/&&/1/&&/2/&&/3/&&/4/}print $x"



I've been programming in Perl for quite some time, but admittedly, most of my code is short and I never got into the extremely terse forms that Perl allows. The line above is simply baffling. First I didn't know that the for loop could magically act like a foreach loop if you didn't give it the standard 3 arguments.

Second, I have no clue what your repetitive add operation (+=) is doing. Yes I get that it is adding the RHS to the contents of $x on each loop iteration. I don't get what the RHS is. It looks like multiple regular expressions, but I don't think it is. ...and what's with the {6} ? I thought that syntax was for accessing the contents of hash variables. Anyway, if you feel like explaining it, I'd like to read it.



> blgentry said:
> 
> 
> > Are you referring to the closed form solution that I was seeking as being "practical" ? If so, I guess a mathematician would have to say that. Otherwise, I must have missed what you saw in my posting.
> ...



 I should have mentioned that these keypads lock you out for increasing time penalties after a number of wrong attempts to open them. I think the first penalty is like 5 minutes and the second one is something like a hour. After a number of these lockouts, the keypad will eventually shut down completely, requiring the assistance of a professional. So knowing these numbers doesn't help with that.

However, it *does* tell you that using 5 digits in your passphrase (necessarily repeating one digit) has the most combinations and that's good to know.

Brian.


----------



## Johannes91 (May 26, 2008)

blgentry said:


> First I didn't know that the for loop could magically act like a foreach loop if you didn't give it the standard 3 arguments.


Well, for and foreach are just synonyms.



blgentry said:


> I don't get what the RHS is. It looks like multiple regular expressions, but I don't think it is.


Yes, it's several regexes and'ed together. It's true (1) if all regexes match, and false (0) if any of them fails. This is equivalent:
$x++ if /[1-4]{6}/&&/1/&&/2/&&/3/&&/4/



blgentry said:


> ...and what's with the {6} ? I thought that syntax was for accessing the contents of hash variables.


It means "repeat the previous token six times" in this context.

Here's another way to do it, btw:
perl -le 'print~~grep/[1-4]{6}/&&/1/&&/2/&&/3/&&/4/,1..9x6'


----------



## blgentry (May 26, 2008)

Johannes91 said:


> blgentry said:
> 
> 
> > First I didn't know that the for loop could magically act like a foreach loop if you didn't give it the standard 3 arguments.
> ...



Oh. Ok then.



> blgentry said:
> 
> 
> > I don't get what the RHS is. It looks like multiple regular expressions, but I don't think it is.
> ...



Ah ha #1.



> blgentry said:
> 
> 
> > ...and what's with the {6} ? I thought that syntax was for accessing the contents of hash variables.
> ...



Ah ha #2

For "ah ha #3" I had to go read the beginning of the perlre reference page. What isn't being said here, is that the loop value is being set to $_ on each pass and the regexes are being matched against it implicitly. Perhaps this is "duh obvious" to a very experienced Perl programmer. It certainly wasn't for me. 

I would have written this as:

for ($pattern=1; $pattern <= 999999; $pattern++) {
if ($pattern =~ /[1-4][1-4][1-4][1-4][1-4][1-4] && $pattern =~ /1/ && $pattern =~ /2/ && $pattern =~ /3/ && $pattern =~ /4/) $count++;
}
print $count;

...which is why Perl people tell me that I don't understand Perl. They're probably right. 

Thank you for taking the time to explain this to me Johannes. Stefan's way is certainly more compact, though I find mine more readable. BTW the technique is a brilliant use of regexes. I'm not sure I would have thought of doing it that way.

Brian.


----------



## Stefan (May 26, 2008)

Johannes91 said:


> perl -le 'print~~grep/[1-4]{6}/&&/1/&&/2/&&/3/&&/4/,1..9x6'


You missed the obvious, though:
perl -e "print~~grep/[1-4]{6}/&/1/&/2/&/3/&/4/,1..9x6"


----------



## brunson (May 26, 2008)

Perl looks like line noise.


----------



## Johannes91 (May 26, 2008)

StefanPochmann said:


> Johannes91 said:
> 
> 
> > perl -le 'print~~grep/[1-4]{6}/&&/1/&&/2/&&/3/&&/4/,1..9x6'
> ...


Ah, thanks.



brunson said:


> Perl looks like line noise.


I think it's reasonable that you can't understand a language you don't know (and that's not similar to some other language you know). But saying that Perl looks like _line noise_ to you sounds very weird; I would've thought that you can understand at least something (keywords, numbers, common operators like + and -).


----------



## Stefan (May 27, 2008)

brunson said:


> Perl looks like line noise.


You haven't seen J, have you?


----------



## brunson (May 27, 2008)

Johannes91 said:


> brunson said:
> 
> 
> > Perl looks like line noise.
> ...



 If you're sixteen, then I started programming in Perl before you were born. I used it extensively for about 12 years in my various capacities as a Unix System administrator and web developer. The comment was tongue in cheek, but since you press the point, I think the syntax is adhoc, arbitrary and convoluted. In my opinion, compactness of syntax is not a benefit of a language if it comes at the cost of readability. I've always thought that the system of adding features to the language was completely capricious and likened it to fixing a car with bubblegum and duct tape. People call it "the vise-grips of programming", well my dad always said, "there's a right tool for every job, and it is *seldom* vise-grips". I stopped programming in Perl about 6 years ago when I found that I was twice as productive in Python after a mere three months of using it.

You've done some *really* impressive stuff on your website which I've always assumed was written in server side Perl, your cross solver is one of my favorite bookmarks and I use it a lot.  With 25 years of programming experience to my credit I know that people can write good code, no matter how crappy the language. I shudder to think the things you will accomplish when you graduate from such a perversion of a scripting tool to a well designed OO language. 



StefanPochmann said:


> brunson said:
> 
> 
> > Perl looks like line noise.
> ...


I'm familiar with a lot of obscure languages, but I don't think I've ever heard of J. Unless it was the strange language I saw on the project Euler page. The guy that used it seemed to be able to produce the most fantastic results with 8 characters of code. ;-)

That was it. It took me a while, but his answers are in the forums. Things like:

Add all the natural numbers below one thousand that are multiples of 3 or 5. 

Solution:
+/~.(3*i.334),5*i.200


Or:

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution:
+/[email protected]&~(f1e6>+/-2#){x,+/-2#x}/1)!2

That is seriously cryptic. (Edit: Even without the BB converting stuff to smilies.)


----------



## Swordsman Kirby (May 28, 2008)

brunson said:


> If you're sixteen, then I started programming in Perl before you were born.


Heheheheheh.


> Add all the natural numbers below one thousand that are multiples of 3 or 5.
> 
> Solution:
> +/~.(3*i.334),5*i.200



It took me much longer on a TI-84 calculator... on run-time, as well.


----------



## cmhardw (May 28, 2008)

[thread hijack]

I'm doing the project Euler problems just with a TI-89 calculator. I can make simple programs on the TI calculators to help, but I'm mostly just doing the more number-theory-esque questions that require less programming in general.

For the first question you don't even need a calculator or a program at all. There is actually a very concise closed form formula for adding up all the number from 1 to n, even when you only want certain multiples out of those numbers.

I don't want to give it away too much, but the first problem is relatively easy if you use more math than programming.

[/thread hijack]

Chris


----------

