# Safe with $12 \times 10^6$ combinations? How is it possible?

I'm thinking of buying a gunsafe and need help confirming or disproving a manufacturers claim. They claim a safe with four buttons has 12,000,000 possible combinations. The rules for the safe are: 3 to 6 entries must be made. Each entry can be either 1,2,3 or 4 buttons. I would greatly appreciate assistance with this problem.

You can press one of four buttons individually in sequence or multiple buttons simultaneously(which would one entry so you would need four multi-button entries) or a combination of the two. Repetitions are allowed.

Examples: a-b-c-d or ab-bc-cd-da or abc-bcd-cda-dab or abcd-abc-ab-a etc.

P.S. I am a layman so please simplify the explanation if possible.

-
If you want us to get to the bottom of this, you're going to have to post a link to the owner's manual. –  TonyK Aug 29 '14 at 11:29
@TonyK here's the link. gunvault.com/skin/frontend/gunvault/gunvault/pdf/… –  Matt G. Aug 29 '14 at 11:32
It looks like this safe does not have an 'end of sequence' button. As such a person who wants to try a few codes of length 6, will automatically attempt a number of codes of shorter length. In any case, for reasonable safety I would recommend you to pick a code of at least length 5. Below that a patient person can crack it manually. –  Dennis Jaheruddin Aug 29 '14 at 12:39

Update to add: Now we have the owner's manual, instead of Matt G's vague recollections of it, we can solve this. A keycode consists of three to six entries; an entry is a non-empty subset of $\{1,2,3,4\}$ (you have to press all the keys in the subset simultaneously).

So there are 15 possible entries, repeated 3-6 times, for $15^3+15^4+15^5+15^6 = 12,204,000$ possible combinations.

Obsolete:

So a combination might be, for instance, DBA-ADBC-BBC-AD ? If so, the manufacturers have understated their case by a factor of more than 1,000: there are $(4+16+64+256)^4 = 13,363,360,000$ possible combinations.

Or do the buttons in an entry have to be pressed simultaneously? Then there are $15^4 = 50,625$ possible combinations.

Or are repeated buttons not allowed in an entry? Then there are $(4+4\cdot 3+4\cdot 3\cdot 2 + 4\cdot 3\cdot 2\cdot 1)^4 = 16,777,216$ possible combinations.

I can't seem to get to $12,000,000$ whatever I try.

-
Note that if you want some extra security, and give yourself a 5- or 6-entry code, you still get 12,150,000 combinations! That is, the 3- and 4-entry codes make up 0.004% of all possible combinations. (I knew that exponents grew quickly, but WOW.) –  columbus8myhw Aug 29 '14 at 21:39

Suppose a two button entry means pressing two different buttons one after the other, so that the order matters. Then the possibilities for each entry are:

one button: 4

two buttons: 12 (4 ways of choosing first button, 3 ways of choosing second)

three buttons: 24 (4 x 3 x 2)

four buttons: 24 (4 x 3 x 2 x 1).

So 64 possibilities for each entry, so 64 x 64 x 64 x 64 = 16,777,216 for the complete combination.

-
Order doesn't matter. abc is the same as bca. There are actually 4 one-button combos, 6 two-button combos, 4 three-button combos, and 1 four-button combo, for a total of 15 possible entries. –  John Kugelman Aug 29 '14 at 13:04
@JohnKugelman: this answer was posted before the OP clarified the question. The interpretation chosen is certainly a possible one based on the original question. –  Willie Wong Aug 29 '14 at 13:10

An entry consists of pressing anywhere between 1 and 4 of the 4 buttons simultaneously. Thus there are 15 possible entries (either list them out yourself, or observe that there are $2^4 = 16$ subsets of the set with 4 elements, but we're excluding the empty set since there's no entry consisting of pressing no buttons).

Each combination consists of between 3 and 6 consecutive entries. So there are:

$$15^3 + 15^4 + 15^5 + 15^6 = 12204000$$

possible combinations, that is 12.2 million.

Note that someone trying to brute-force the safe combination may or may not need to try all combinations in order to be sure of success, according to whether there's a separate "open" button that must be pressed to end the combination when entering it to open the safe. If there is then they need to try everything. If the safe just opens once the correct entry sequence has been typed then I might be able to enter a-a-a-a-a-a and I've tried 4 possible combinations simultaneously. Namely a-a-a, a-a-a-a, etc. You may or may not need to take this into account in any security assessment that you do based on the number of combinations.

-
Thank you, Steve. I will consider your advice. –  Matt G. Aug 29 '14 at 11:56

I agree with Steve's answer. The power set of the set {1,2,3,4} consists of 2^4 elements. The power set is the set of all subsets of {1,2,3,4}. I.e, power set = { empty set, {1}, {2}, {3}, {4}, {1,2},...}. We throw out the empty sent to get 2^4-1=15 possible ways to press the buttons one time.... Then, there are 15^3 combinations with 3 consecutive entries. There are 15^4 combinations with 4 entries. Etc.

-