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 three-digit 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 right-hand 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 right-hand digit of the result is c+10-a. But now the center digit of the upper number is b-1, which is less than b, so we must borrow from the left-hand a, reducing a by 1 and increasing b-1 by 10. Hence the middle digit of the result is b-1+10-b, which equals 9. Also, the left-hand digit of the result is a-1-c. 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) 8-c, 9, and c+1. Obviously c cannot equal c+1, so we must have b = c+1 and c = 8-c. 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 digit-reversed 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 = a-1-c and c = c+10-a, or else c = a-1-c and a = c+10-a. The first alternative is ruled out because it implies a = 10 and c = -1, both of which are outside the allowable range 0-9 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 B-1) resulting from the subtraction are (from left to right) a-1-c, B-1, and c+B-a. 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, 1-B, -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 B-1 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 B-2 is divisible by 3 (which guarantees that 2B-1 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 B-2 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 10-2 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 14-2 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 four-digit 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 three-digit numbers, we can solve the system of equations with constraints to give explicit expressions for the solutions for any given base. With four-digit 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 three-digit 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 B-1. 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 B-4 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 four-group of permutations

 

 

These permutations comprise the Klein four-group, 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 four-group permutations to the digits of one solution, each digit sums to B-1 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 2B-3, 2B, B+3, B-6, all divided by 3, and the digits of the dcab solution are 2B-6, 2B+3, B, B-3, 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 B-1. 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 five-digit 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 IR, 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” bj as (in the case of six-digit numbers for example)

 

 

Each borrow index bj equals either 0 or 1, depending on whether the subtraction in the jth place entails a borrow. For N-digit numbers we have up to N-1 possible borrows, represented by the indices b0 to bN-2. However, we must always borrow in the least significant place, so b0 necessarily equals 1. Thus we have N-2 undetermined indices, which implies that there are 2N-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 |IRP| = 0, there may be one or more solutions. For example, consider a five-digit 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 = 1-B. 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 |IRP| = 0, may be under-determined 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 four-digit 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 four-digit numbers in any base, whereas there is no limit to the number of acceptable solutions for five-digit numbers as B increases. The same applies to six-digit 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 (IQP)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.

 

Return to MathPages Main Menu