• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Safe Combination Math Challenge

blgentry

Member
Joined
Apr 10, 2008
Messages
263
Location
Miami, Florida
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.
 

malcolm

Member
Joined
Nov 18, 2007
Messages
165
Location
New Zealand
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?
 
Last edited:

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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. :p
(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.
 
Last edited:

badmephisto

Member
Joined
Aug 29, 2007
Messages
836
YouTube
Visit Channel
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

Member
Joined
Apr 10, 2008
Messages
263
Location
Miami, Florida
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

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
,{x,-1+m}]
Uh, that means "for values of m [beginning with 1] up to m-1." Lemme fix that in the original post.

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. :p
(See my solution to problem 9 of the MathCamp 2008 quiz.)

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

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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"

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.

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

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

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

Member
Joined
Apr 10, 2008
Messages
263
Location
Miami, Florida
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.

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.

:) 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

Member
Joined
Mar 28, 2006
Messages
1,341
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.

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/

...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'
 
Last edited:

blgentry

Member
Joined
Apr 10, 2008
Messages
263
Location
Miami, Florida
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.

Oh. Ok then.

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/

Ah ha #1.

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

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.
 

Johannes91

Member
Joined
Mar 28, 2006
Messages
1,341
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"
Ah, thanks.

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

brunson

Member
Joined
Feb 17, 2008
Messages
1,119
Location
Westminster, CO
WCA
2008BRUN01
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 -).

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

Perl looks like line noise.
You haven't seen J, have you?
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:
+/f@&~(f:(1e6>+/-2#){x,+/-2#x}/1)!2

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