An unusual combination lock problem

Suppose there's a 4-digit combination padlock and you're asked to open it.

But this lock has an unique defect in a way that the four digits need not be in the correct order for it to open. For example, if the right key is 0-1-2-3, combinations such as 3-2-1-0, 2-0-1-3 or any other orderings of 0, 1, 2, 3 are sufficient to crack it open.

1. How many tries does it take to open this lock with brute force?
2. What is the best strategy to ensure the least number of tries?

(edit) Yes, let's assume repetition of digits is allowed.

• What have you tried? If this problem seems daunting, you can try the simpler version of 3 (or even 2) digits. – Alex Zorn Feb 24 '13 at 19:16
• Out of 10 digits, you have to chose 4; $C_{4}^{10}$ – hjpotter92 Feb 24 '13 at 19:17
• Are you allowed to repeat digits? Is 3-3-3-3 a valid combination, for instance? – alex.jordan Feb 24 '13 at 19:30

There are $10$ digits total to choose from, and you must choose $4$ of them to make a given combination, though they need not be distinct, as far as I can tell. (In fact, if they were required to be distinct, then there may not be a best strategy for guessing, so I assume that they need not be distinct.) Hence, there are $10^4$ possible combinations.

Note that if you try out a combination with $4$ distinct digits, and it turns out to fail, then you've actually ruled out $24$ different possible combinations. Failed combinations with $3$ distinct digits will rule out $12$ different possible combinations. Failed combinations with $2$ distinct digits and both digits repeated will rule out $6$ different possible combinations. Failed combinations with $2$ distinct digits and only one of the digits repeated will rule out $4$ distinct combinations. Failed combinations with a single digit repeated $4$ times only rule themselves out. (To see how I came up with these numbers, check out this page.)

Since the order doesn't matter when we're trying to open the lock, then we may as well try only combinations where the numbers are in non-decreasing order--that is, the first digit is the smallest, and each subsequent digit is at least as big as the one before it. There are clearly $10$ such combinations with a single digit repeated $4$ times. There are $90$ such combinations with $2$ distinct digits and only one digit repeated ($45$ ways to pick the digits, and $2$ ways to choose which of them is repeated). There are $45$ such combinations with $2$ distinct digits and both digits repeated. There are $360$ such combinations with $3$ distinct digits ($120$ ways to pick the digits, $3$ ways to pick the one that repeats). Thus, there are $$1\cdot 10+4\cdot 90+6\cdot 45+12\cdot 360=4960$$ combinations with at least one repeat, leaving $5040$ combinations with no repeats, and so there are $$\frac{5040}{24}=210$$ combinations in non-decreasing order with no repeats.

In total, there are thus $10+90+45+360+210=715$ non-decreasing combinations that we need to try, and we can be sure to get it open by the end of that list.

As for strategy, let's suppose that each of the $10000$ possible combinations is equally likely to be correct. (As mentioned below, this is far from a given, but it gives us a place to start.) Then we have \begin{align}\text{P(four distinct digits)} &= \frac{24\cdot 210}{10000}=50.4\%\\\text{P(three distinct digits)} &= \frac{12\cdot 360}{10000}=43.2\%\\\text{P(two distinct digits, both repeated)} &= \frac{6\cdot 45}{10000}=2.7\%\\\text{P(two distinct digits, only one repeated)} &= \frac{4\cdot 90}{10000}=3.6\%\\\text{P(single digit repeated four times)} &= \frac{1\cdot 10}{10000}=0.1\%.\end{align} Guessing a non-decreasing combination with 4 distinct digits is effectively worth $24$ guesses, and so on. Our expected value for a given kind of combinations--that is, how efficient a given nondecreasing combination will be as a guess--would then be \begin{align}\text{E(four distinct digits)} &= 24\cdot50.4\% = 12.096\\\text{E(three distinct digits)} &= 12\cdot43.2\% = 5.184\\\text{E(two distinct digits, both repeated)} &= 6\cdot2.7\% = 0.162\\\text{E(two distinct digits, only one repeated)} &= 4\cdot3.6\% = 0.144\\\text{E(single digit repeated four times)} &= 1\cdot0.1\% = 00.001.\end{align} I'd argue, then, that the best strategy is to work through the non-decreasing combinations with $4$ distinct digits first, then those with only $3$, and so on in decreasing order of expected value. Ultimately, that conclusion relies on the assumption I made, and the "best" strategy (if any) may well vary, depending on the distribution of the possible combinations, as Greg points out. Still, the principle is the same, regardless: try "combination types" with the highest expected elimination value first, then continue in decreasing order.

• This is the most educational and thorough answer. Thank you! – Robert C Feb 24 '13 at 21:24
• Let's emphasize the assumption "suppose that each of the 10000 possible combinations is equally likely to be correct". If the setter of the combination is clever, they might well prefer to set combinations with repeated digits, exactly to thwart this strategy. In general, the strategy depends upon the hypothesized distribution of possible combinations. – Greg Martin Feb 24 '13 at 22:08
• @Greg: Excellent point. I should have brought attention to that rather important assumption. – Cameron Buie Feb 24 '13 at 22:38
• This is a good detailed investigation of this scenario. However I would suggest to OP that you learn about binomial coefficient "choose functions" in order to tackle a huge library of other combinatorial problems very quickly. After learning about these things, it is immediately clear that the answer is $\binom{13}{4}$ (with repeated digits allowed) or $\binom{10}{4}$ (with no repeated digits allowed). – alex.jordan Feb 24 '13 at 23:03

If repetition of digits is not allowed, then @anorton's answer does it. If repeated digits are allowed, then imagine 9 bars: $$|||||||||$$ Between successive bars you have areas that represent a digit: $$0|1|2|3|4|5|6|7|8|9$$ You need to put the four digits from the combination into these 10 areas. For example, 0-1-2-3 can be represented as: $$*|*|*|*||||||$$ and 1-2-2-9 as: $$|*|**|||||||*$$ Any arrangement of 9 bars and 4 stars provides you with a unique combination (since order is ignored). Thus with 13 things to set as either a star or a bar, and the requirement that four of them must be stars, there are $\binom{13}{4}=715$ possibilities.

Essentially, this is asking how many combinations are there of 4 numbers in range 0-9. This is equivalent to:

$$\binom{\text{count of possible inputs}}{\text{number in each group}}=\binom{10}{4} = 210$$

Thus, a maximum of 210 attempts are all that are necessary.

I'll leave the optimal strategy to someone else... :)

• no, that’s only if all the numbers are different, but what if the combination is 2,2,2,2 you don't have four 2's in you scenario. – Jorge Fernández Hidalgo Feb 24 '13 at 19:35

well the number of tries it takes can be counted using stars and bars (Counting marbles). You have to divide 4 digits into 10 different piles.

Imagine the three digits are stars. - - - -.

Then you will need 9 bars to divide them into 10 areas. for the first line you have 5 choices. if all of the other 8 lines are in the same spot we need to add 8 "imaginary places" to allow repeats. These places are only used when we repeat. Therefore it is $\binom{13}{9}$. Because we need to pick 9 bars out of 13 possible places. The answer is $$715$$.

Now onto the strategy: You should choose the combinations with all distinct numbers first. then the combinations with two equal ones, then with three and lastly four.

• Why exactly $\binom{10}{13}$? Shouldn't it be $\binom{10}{4}$? – apnorton Feb 24 '13 at 19:22