I got this interesting puzzle by email. A safe has a code lock that unlocks if you input the correct four digits, in any order. The lock has a keypad the digits 0, 1, 2, …, 9.
For example, suppose the unlock code is 1000. The safe will open for any order you input the digits:
Or consider the unlock code 1234. Then the safe will open for any permutation of the same digits (1243, 1342, etc.).
How many different unlock codes are there? (Two unlock codes are different if they do not contain exactly the same digits.)
Watch the video for a solution.
Or keep reading.
Answer To The Unordered Code Lock Safe
I will present the long way to solve this problem and then I will show a clever approach that solves the problem nearly instantly!
Method 1: count all possible permutations
In an ordered code lock, there are 10 possible digits for each of the 4 possible entries, making for a total of 10(10)(10)(10) = 10,000 codes.
In this unordered code lock, codes that involve the same four digits are equivalent, so we have to avoid double-counting codes.
One approach is to directly count the codes. The 4 digit code can have 1 unique digit, 2 unique digits, 3 unique digits, or 4 unique digits.
For 1 unique digit, there are 10 possible codes (0000, 1111, …, 9999). In other words, there are 10 choose 1 = 10 ways to pick the digit which is repeated all four times.
For 2 unique digits, it is a bit more complicated to count. There are 10 choose 2 = 10(9)/2 = 45 ways to select 2 digits. Now we have to consider how they can be ordered. If the two digits are marked a and b, then either one digit is repeated three times (aaab or abbb), or each digit appears two times (aabb). Thus, there are are 3 patterns for each of the 45 ways to select two digits. There are 45(3) = 135 codes to check involving 2 unique digits.
For 3 unique digits, there are 10 choose 3 = 10(9)(8)/[3(2)] = 120 ways to select 3 digits. Now we have to consider how they can be ordered. If the three digits are marked a, b, and c, then one of the digits is repeated, so there are three possible code patterns (abca, abcb, or abcc). Thus, there are 120(3) = 360 codes to check involving 3 unique digits.
For 4 unique digits, there are 10 choose 4 = 10(9)(8)(7)/[4(3)(2)] = 210 ways to select 4 digits. Since each digit has to appear exactly once, there is only one possible code pattern abcd. Thus, there are 210 codes to check involving 4 unique digits.
The total number of codes is found by adding up each of the possibilities:
10 – 1 unique digit
135 – 2 unique digits
360 – 3 unique digits
210 – 4 unique digits
715 – total codes to check
This is a direct method to count the total number of codes. But notice there are many calculations to make, and if you make a mistake in any step then your final answer will be wrong. So it is useful to solve this problem in another way that involves fewer calculations.
Method 2: solve an equation for the number of non-negative solutions!
Let’s write xi to be the number of times that digit i appears in the code. Each digit has to be a non-negative number between 0 and 4. Furthermore, a valid code involves 4 digits, so the sum of all of the variables must be 4. We have the equation:
x0 + x1 + … + x9 = 4
The number of valid codes is equal to the number of non-negative solutions to this equation.
This sounds like a hard problem, but there is an elegant combinatorial proof method! I described it in a video puzzle about distributing coins to individuals.
The idea is this: the equation has 10 variables that need to sum to 4. We can visualize this as having 4 identical stars that are divided into 10 groups. The 10 groups can be created by using 9 bars to divide the stars. The first group is to the left of the first bar, then each subsequent group is in between two bars, and then the final group is to the right of the last bar. Here is one example of a star and bar division.
The first three groups are 0, the next group has 1 star, then the next group has 2 stars, then there is another group with no stars, then another star, and then the final three groups have no stars. This corresponds to the equation:
0 + 0 + 0 + 1 + 2 + 0 + 1 + 0 + 0 + 0 = 4
We could also use this solution to translate to the unlock code 3446, as there is one instance of the digit 3, two instances of the digit 4, and one instance of the digit 6.
How many solutions are there to the stars and bars problem? We have a total of 13 items (4 stars and 9 bars) that need to be arranged in some order. We have 13 spots, and once we place the 9 bars, the remaining spots have to go to the 4 stars. So we have 13 choose 9 = 13(12)(11)(10)/[4(3)(2)(1)] = 715 ways.
This gives us the number of non-negative integer solutions, and therefore this is also the number of unlock codes. It’s the same answer obtained in just one calculation!
More generally, in such an equation, if there are r variables that sum to n, the total number of non-negative integers solutions is (n + r – 1) choose (r – 1). You can derive this formula by counting how to arrange n + r – 1 items consisting of n stars and r – 1 bars.
We get to the answer of 715 without all the steps of counting out unique digits and code patterns!
Proof of number of non-negative solutions
To see why the formula works generally, imagine we have n objects and we want to distribute them to r people. If we write xi for the number of objects person i gets, then we want to solve for the number of non-negative integer solutions to the equation:
x1 + x2 + … + xr = n
We can count the solutions by thinking combinatorially. Let us draw the n objects as “stars”:
*******…*** (n stars)
To distribute the items to r people, we can place r – 1 bars in between the stars. Then, the number of stars person k gets is the number of stars between the bars k – 1 and k, except the the number of stars for person 1 is to the left of the first bar and the stars for person r is to the right of the r – 1 bar. The r – 1 bars create a total of r divisions. If two bars are directly next to each other, then that person gets 0 stars.
||*|**|****…*|** (n stars, divided by r – 1 bars)
How many divisions are possible? There are a total of n + r – 1 positions for a star or a bar, and we can place the bars in r – 1 different positions. Thus the number of divisions is (n + r – 1) choose (r – 1). This solution then corresponds to the number of non-negative integer solutions to an equation with r variables that sum to n.
Can You Solve The Code Lock Puzzle? Sunday Puzzle