Subtracting the Reversal 

Is Clarence dead? the order was reversed. 
Shakespeare 

Does there exist a decimal number with three distinct digits such that, if we reverse the digits and subtract from the original number, the result consists of the same three digits (in some order)? This is nice puzzle because it has a unique solution that can be found with just a little careful reasoning by anyone familiar with basic arithmetic. In a more abstract sense it’s a problem in linear algebra with constraints, and it has some interesting generalizations to different bases and to numbers with more than three digits. 

First let’s review the original problem, for threedigit decimal numbers. We seek three distinct integers a,b,c in the range 0 to 9 such that “abc” – “cba” equals some number with the same three digits. According to the usual method for subtraction, we would write this in the form: 

_{} 

The result must be positive, so a must be greater than c. This implies that when we begin our subtraction in the righthand column, c is less than a, so we will need to borrow from the middle b, reducing b by 1 and increasing c by 10. Hence the righthand digit of the result is c+10a. But now the center digit of the upper number is b1, which is less than b, so we must borrow from the lefthand a, reducing a by 1 and increasing b1 by 10. Hence the middle digit of the result is b1+10b, which equals 9. Also, the lefthand digit of the result is a1c. We know one of the digits is 9, and this can’t be c because c is less than a. Therefore, we have only two possibilities: either a = 9 or else b = 9. In the first case, with a = 9, the three digits of the result are (from left to right) 8c, 9, and c+1. Obviously c cannot equal c+1, so we must have b = c+1 and c = 8c. The latter equation implies c = 4, so the former equation gives b = 5. This leads to the conclusion that 954 is our original number, and we can verify this by subtracting the digitreversed number 459, giving the result 495. 

Furthermore, and we can show that this is the only answer by examining the other possibility, i.e., checking to see what happens if we had set b = 9 instead of a = 9. In that case either a = a1c and c = c+10a, or else c = a1c and a = c+10a. The first alternative is ruled out because it implies a = 10 and c = 1, both of which are outside the allowable range 09 for decimal digits. The second alternative is ruled out because it implies a = 19/3 and c = 8/3, which are within the allowable range but not integers. (We do not allow fractional digits.) Therefore, b cannot equal 9, so the only solution is the one we already found with a = 9. 

So far we have assumed the numbers were all written in the base 10, i.e., decimal notation, but we could also consider the problem for any arbitrary base B. In that case the same reasoning as above leads to the conclusion that the three digits (now required to be in the range 0 to B1) resulting from the subtraction are (from left to right) a1c, B1, and c+Ba. These must be some permutation of the digits a,b,c. In matrix form we can express these conditions as 

_{} 

where P is a permutation matrix. The six possible permutation matrices of order 3 are listed below, with the subscripts on P denoting the permutation. 

_{} 

Letting M denote the leading coefficient matrix in the preceding equation, X the column vector with the values a,b,c, and V the column vector with the values 1, 1B, B, the matrix equation can be written as MX + V = PX, and the solution for any given P is 

_{} 

Inserting each permutation matrix in turn into this equation, we get the following results 

_{} 

The asterisks for permutations acb and bac signify the equation is singular, and it’s easy to show there are no acceptable solutions in those cases. Also, the solutions for permutations abc and bca are unacceptable, because they contain values that are outside the range 0 to B1 and/or that are fractional. Therefore, the only possible solutions are those corresponding to cab and cba. The former are acceptable solutions if and only if the base B is even, whereas the latter are acceptable solutions if and only if B2 is divisible by 3 (which guarantees that 2B1 is also divisible by 3). Thus for any given base B there may be zero, one, or two solutions, depending on whether B is divisible by 2 and whether B2 is divisible by 3. 

In the original problem we had B = 10, so the cab solution was acceptable because 10 is divisible by 2, but the cba solution was not acceptable because 102 is not divisible by 3. (Recall that our solution for abc = 954 led to 495, which is indeed the cab permutation.) On the other hand, with the base B = 14 we have two solutions, because 14 is divisible by 2, and 142 is divisible by 3. The cab solution is 13,7,6, and the cba solution is 9,13,4. 

Now, what if we ask the same question about fourdigit numbers? In other words, we seek a number with four distinct digits “abcd” such that if we reverse the digits and subtract from the original number we get a number with the same four digits (in some order). In the base 10 a simple search shows that there are exactly six such numbers, shown below. 

_{} 

Notice that these solutions correspond to the permutations adcb, dacb, adbc, cadb, bdac, and bcda respectively. Numerically checking with other bases, we find that for every base greater than 5 there are always at least four solutions, and sometimes six, eight, or ten. The smallest base with ten solutions is B = 9. We will prove below that there are never more than ten solutions for any given base. 

Just as we did for threedigit numbers, we can solve the system of equations with constraints to give explicit expressions for the solutions for any given base. With fourdigit numbers there is more than one possible pattern of borrows in the subtraction. It is always necessary to borrow for the first digit (for the same reason as in the threedigit case), and there is obviously never a borrow for the fourth digit, but for each of the two digits in between we can either borrow or not borrow, so this gives four possible cases to consider. Two of these can easily be shown to give unacceptable results, so we are left with just two possible patterns of borrowing. These two patterns lead to the two systems of equations 

_{} 

where P here denotes any permutation matrix on four elements. There are 4! = 24 permutation matrices, and for each of these we must solve the equations for each of the two vectors on the right hand side, so there are 48 distinct cases. Most of these do not give acceptable solutions, either because they contain digits outside the allowable range, or because the digits are not all distinct. The twelve permutations that give possibly acceptable solutions are listed below. 

_{} 

For any integer base (greater than 5) the four solutions corresponding to the permutations bcda, adbc, adcb, and dacb are always acceptable, since the values are explicitly distinct integers in the range 0 to B1. On the other hand, the four solutions corresponding to the permutations dcba, cdba, dcab, and cdab are acceptable if and only if B is divisible by 3. Similarly the two Borrow Type 1 solutions corresponding to permutations bdac and cadb are acceptable if and only if B is divisible by 5. The remaining two solutions for those permutations, which are Borrow Type 2, are acceptable if and only if B4 is divisible by 5. This explains why there are no more than ten solutions for any base, because the condition of acceptability for the two cases of bdac (and likewise for the two cases of cadb) are mutually exclusive. 

Incidentally, the twelve acceptable solutions seem to form natural complementary pairs related to the fourgroup of permutations 

_{} 

These permutations comprise the Klein fourgroup, which has the multiplication table shown below. 

_{} 

The permutations corresponding to the twelve acceptable solutions come in pairs that are related by one of these permutations, i.e., either a reversal, a transposition, or a swapping. Moreover, the solution digits for these pairs are complementary in the sense that if we apply one of the fourgroup permutations to the digits of one solution, each digit sums to B1 with the corresponding digit of the other solution. 

For example, two of the acceptable solutions correspond to the permutations cdba and dcab, which are related to each other by the T permutation (i.e., transposing 1,2 and 3,4). The digits of the cdba solution are 2B3, 2B, B+3, B6, all divided by 3, and the digits of the dcab solution are 2B6, 2B+3, B, B3, also all divided by 3. If we apply the S (swap) permutation to the latter digits, and then form the sums of the corresponding digits of these two solutions, we get 

_{} 

Thus, dividing by 3, we see that each sum is B1. The same applies to each of the other pairs of acceptable solutions. In the table below we list the solution pairings, and the permutation that relates them, and the permutation that applies to the solution digits to align the complementary sums. 

_{} 

The asterisks indicate that the two solutions have the same set of digits (as well as being complementary). 

We could go on to consider numbers with more then four digits. For example, among the fivedigit numbers in the base ten we have the 16 solutions 

32760 38970 39780 49680 54270 58923 60273 60732 
69480 69723 70254 73260 76941 79380 89604 96732 

The same formal technique can be applied to any number of digits, although the number of distinct borrow patterns increases, as does the number of permutations of the digits of the subtraction result. Notice that the coefficient matrix, which we called M, can be written as I – R, so the solution for any given permutation P and borrow pattern vector V can be written as 

_{} 

where V can be written explicitly in terms of the “borrow indices” b_{j} as (in the case of sixdigit numbers for example) 

_{} 

Each borrow index b_{j} equals either 0 or 1, depending on whether the subtraction in the jth place entails a borrow. For Ndigit numbers we have up to N1 possible borrows, represented by the indices b_{0} to b_{N}_{2}. However, we must always borrow in the least significant place, so b_{0} necessarily equals 1. Thus we have N2 undetermined indices, which implies that there are 2^{N}^{2} possible borrow pattern vectors to consider, although usually some of these can be ruled out immediately. Likewise there are N! possible permutation matrices on N digits, but many of those can be ruled out as well. 

Even if I – R – P = 0, there may be one or more solutions. For example, consider a fivedigit solution (in the base B) corresponding to the permutation eabdc with the borrow vector b = {00111}. This implies that the solution digits X satisfy 

_{} 

The determinant of the coefficient matrix is zero, because the third and fourth rows are identical, both signifying b = 1B. If we bring d over to the right side, we can eliminate the fourth row and fourth column, to give the reduced conditions 

_{} 

The solution is 

_{} 

With B = 11 we can examine the odd values of d, and we find that d = 1 or 5 give the two acceptable solutions of this form in distinct digits {8 10 7 1 4} and {4 10 9 5 2}. Likewise with B = 23 we find eight acceptable solutions of this form, with d = 1, 3, 5, 9, 11, 13, 15, or 17. (The cases d = 7, 19, and 21 are excluded because they lead to numbers with duplicate digits.) This shows that, with N = 5, the number of acceptable solutions increases without limit as B increases. The basic reason is that the “singular” cases, i.e., the permutations such that I – R – P = 0, may be underdetermined and lead to families of solutions, all of the same form, and the number of these is proportional to B (when there is one degree of indeterminateness). This is in contrast to the fourdigit numbers (N = 4), where none of the coefficients matrices is singular, so we have a definite number of possible solutions, independent of B. As we proved above, there can be no more than 10 acceptable solution with fourdigit numbers in any base, whereas there is no limit to the number of acceptable solutions for fivedigit numbers as B increases. The same applies to sixdigit numbers. 

Incidentally, throughout this discussion we have stipulated that the number subtracted from the original number is given by simply reversing the digits, and hence is represented by the reversal permutation R, but we could just as well stipulate any other permutation Q, and solve the equation (I – Q – P)X = V. Also, since Q and P appear symmetrically, we could swap them, without affecting the borrow vector, consistent with the fact that the pattern of borrows when computing x – y = z is the same as when computing x – z = y. 
