Here’s a fun little problem: Find three three-digit numbers that use each non-zero numeral once and add up to 999. Follow-up: How many such sets of numbers exist?
If you want, take a moment to work on the problem on your own. Then continue reading.
Finding a solution
For the first question, any set of numbers that satisfies the conditions solves the problem. Most mathematics problems presented in this fashion have unique solutions, but this one does not; indeed, the follow-up indicates that there are multiple such solutions (although it is certainly possible, a priori, there is only one or even no solutions).
So here’s how I constructed the original answer.
I reasoned that we couldn’t have a number higher than 6 in the leftmost column, because 6 + 1 + 2 = 9; anything higher than 6 and the sum would be greater than 1000. Therefore, we had to put the 7, 8, and 9 in the other two columns. Since the other two columns would then each add up to more than 9, that in turn meant that we couldn’t have a number higher than 5 in the leftmost column, since 1 + 2 + 5 + (1) = 9.
I put the 9 in the rightmost column. This meant the other two numbers needed to add to 10. The possibilities are 8 + 2, 7 + 3, and 6 + 4. 8 + 2 creates a potential problem in the leftmost column (it would then have to be 1 + 3 + 4 + (1)), so I chose 6 + 4.
The 8 therefore needed to be in the center column. This meant (again) that the other two numbers needed to add to 10, and that they had to be 7 + 3 (because 8 + 2 would force 4 in the leftmost column, but we’ve already used 4). Had I chosen 7 + 3 for the rightmost column (instead of 6 + 4), I would have had to choose 6 + 4 for the center column, which would also yield a valid solution.
So column by column, we have two possibilities:
- (1, 2, 5)(8, 7, 3)(9, 6, 4)
- (1, 2, 5)(8, 6, 4)(9, 7, 3)
To build a solution, choose a number from the first set, a number from the second set, and a number from the third set; this is your first three-digit number. Repeat for the second number, then use the leftovers for the third number.
Sample solutions:
- 176 + 284 + 539
- 567 + 283 + 149
Finding all solutions
For the follow-up, we have two questions: How many combinations of numbers can we build from the two sets above, and are there any solutions not represented by the two sets above?
Let’s take the first question.
For me, a unique solution is a set of three-digit numbers, regardless of the order of the three-digit numbers (for instance, 567 + 283 + 149 and 567 + 149 + 283 are the same solution). Given that, you can choose any number for the first digit; there are six possibilities for matching those with the second digit (3 for the first choice, 2 for the second choice), and six possibilities again for the third digit. There are two possibilities for choosing from in the first place, so the total combinations are 6 · 6 · 2 = 72. If you want to count the same three-digit numbers in different orders as different solutions, there are 72 · 6 or 432.
Now let’s take the second question. I had made certain assumptions in the original construction. Are all those assumptions necessary?
Assumption 1: 6, 7, 8, and 9 must be in the two rightmost columns. This is a requirement. Let us say the leftmost column is 1 + 2 + 6. Then the center column cannot be anything less than 3 + 4 + 5, which is 12, which causes a 1 to come over to the hundreds column. Therefore the leftmost column cannot sum to anything more than 8. These sets add to 8: (1, 2, 5), (1, 3, 4).
Now, can the leftmost column equal 7? After all, 9 + 8 + 7 = 24, so it’s possible to carry (regroup) a 2 up a place. However, we’d need a column to equal at least 27 in order to get a 9 at the bottom of the column (27 + 2 = 29), and the most a column with three distinct numerals could equal is 24. Therefore, the leftmost column must equal exactly 8.
Assumption 2: 9 is in the rightmost column. Let us look at it another way. We know that the rightmost column must equal 9, 19, or 29. It cannot equal 29 (because it cannot be more than 24). Can it equal 9? If the leftmost column is (1, 2, 5), then the rightmost column must be at least (3, 4, 6), which adds to 13. If the leftmost column is (1, 3, 4), then the rightmost column must be at least (2, 5, 6), which again adds to 13. So it cannot equal 9. Therefore, it must equal 19.
What are the possible sets of three unique digits that add to 19? (2, 8, 9), (3, 7, 9), (4, 6, 9), (4, 7, 8), (5, 6, 8). Three of these contain 9, and two do not.
We have already seen what happens when we pick (3, 7, 9) or (4, 6, 9). These lead to (1, 2, 5) in the leftmost column, and then to (4, 6, 8) or (3, 7, 9) respectively in the center column.
Let us pick (2, 8, 9). This means the leftmost column is (1, 3, 4), and so the center column is (5, 6, 7). The sums of columns from right to left are 19, 18, and 8, so this creates another solution set.
Let us pick (4, 7, 8). This means the leftmost column is (1, 2, 5), and so the center column is (3, 6, 9). This is also acceptable.
Finally, let us pick (5, 6, 8). This means the leftmost column is (1, 3, 4), and so the center column is (2, 7, 9). Again, this is acceptable.
So we have five possible column-by-column configurations:
- (1, 2, 5)(8, 7, 3)(9, 6, 4)
- (1, 2, 5)(8, 6, 4)(9, 7, 3)
- (1, 2, 5)(9, 6, 3)(8, 7, 4)
- (1, 3, 4)(7, 6, 5)(9, 8, 2)
- (1, 3, 4)(9, 7, 2)(8, 6, 5)
This is now an exhaustive list: Any solution must satisfy one of these five configurations.
There are 36 · 5 = 180 combinations, and 180 · 6 = 1080 permutations. That may seem like a lot, but keep in mind there are 9! = 362880 permutations of the nine non-zero digits in a 3×3 grid (or 60480 unique sets of three-digit numbers where all non-zero digits are represented).
Now let’s try base 9
Because we’re working in base 10, we’ve been excluding 0 from the party. Can we come up with a base 9 solution that uses all the digits available?
This time, we need each column to equal 8. 0 is not available for the leftmost column, because numbers can’t start with a 0.
The immediate options for the leftmost column are (1, 2, 4), (1, 2, 5), and (1, 3, 4). The first of these adds up to 7 and so assumes that the center column will provide a 1. The other two assume that the center column will not provide a 1, which is a possibility because 0 is available to the center column.
The rightmost column must add to 8 or 189, that is, 17. Let us consider all the possibilities here.
We can get 8 thus: (0, 1, 7), (0, 2, 6), (0, 3, 5), (1, 2, 5), (1, 3, 4). However, the leftmost column has a 1, so we can rule those options out. That leaves (0, 2, 6) and (0, 3, 5).
We can get 17 thus: (2, 7, 8), (3, 6, 8), (4, 5, 8), (4, 6, 7).
We have a total of six possibilities for the rightmost column. Taking each in turn, let’s see what we’re left with for the center column.
(0, 2, 6): (1, 3, 4) for the left, (5, 7, 8) for the center. However, this sum is not acceptable.
(0, 3, 5): (1, 2, 4) for the left, (6, 7, 8) for the center. Again, not acceptable.
(2, 7, 8): (1, 3, 4) for the left, (0, 5, 6) for the center. Again, not acceptable.
(3, 6, 8): Try (1, 2, 4) for the left, (0, 5, 7) for the center. This is not looking promising.
(3, 6, 8): Now try (1, 2, 5) for the left, (0, 4, 7) for the center. Again, no.
(4, 5, 8): This eliminates all possibilities for the left.
(4, 6, 7): (1, 2, 5) for the left, (0, 3, 8) for the center. We have eliminated all possible scenarios.
So while there are some solutions using 1..9 to build three three-digit numbers in base 10, there are no solutions using 0..8 is base 9.