Digit Reversal

Even in fifth grade one finds questions that please the MathNerds...

Find a five digit number ABCDE such that 4 \cdot (ABCDE) = EDCBA. The digits must be distinct, and A must not be 0.

Need a hint? Click here.

Click here for the complete solution.

Hint 1

This kind of problem (called a cryptarithm) is solved by trial and error. Because there are 90 000 five-digit numbers, we could just try them all, but that would take a long time unless we hired a computer to help. The challenge in this kind of problem is to think up clever ways to cut down the number of trials. What are some properties of the numbers ABCDE and EDCBA that you can figure out from the equation?

Hint 2

We know from the equation that EDCBA is a multiple of 4, so it is even, and A must be even. We also know that ABCDE has 5 digits but cannot be an extremely large 5-digit number because 4 times it is still a 5-digit number; for example, it could not be as big as 90 000 because 4 times that is 360 000, a 6-digit number. Use these ideas to limit the possible values for A and E.

Hint 3

We know A is even, so it is one of 0, 2, 4, 6, or 8. It can't be 0, because then ABCDE would not be a 5-digit number (it would only be 4 digits). It can't be 4, 6, or 8, because then 4 \cdot (ABCDE) would be too large (it would be at least 4 \cdot 40\,000 = 160\,000, not a 5-digit number). So it must be that A is 2. The multiplication immediately tells us that E is 4 \cdot 2, possibly with a carry, so it is 8 or 9. It can't be 9 because 4 \cdot 9 = 36, and 4 \cdot (ABCDE) would end in 6, not in 2. So we have made a lot of progress! We want to solve

Use these same ideas to cut down the possibilities for B and D to a single number each. Use the fact that we are multiplying by 4, and the fact that ABCDE cannot be very large.

The Rest of the Solution

B must be 0, 1, or 2, because anything larger would cause the product 4 \cdot (2BCD8) to be too large (it could not have 8 as the leading digit). We also know from the product that B results from 4 times something, plus a carry of 3 from the 4 \cdot 8 , so B is odd and so can only be 1. Then 4 \cdot D plus the carry of 3 gives a number ending in 1, and by trying each single-digit number for D you see that it must be 2 or 7. It cannot be 2 because we've already used 2, so it must be 7. Now we are nearly done! We just have to solve

and we can finish using the same ideas. We have that 4 \cdot 78 is 312, so 4 \cdot C plus a carry of 3 is equal to a number ending in C. By trying all possible 1-digit values we find that C is 9. The final answer is 4 \cdot (21978) = 87912.

Solve Part of the Problem

Pólya's book How to Solve It recommends in many conditions that if you don't know how to solve the problem, try to solve part of it. We have done that here: We don't know how to find the whole five-digit number, but we were able to find one of the digits and continue from there. There's more about this approach in the book's section on "Puzzles".

Another Approach

Because of the special form of this problem we were able to work out the digits one at a time without doing any trial and error on the whole 5-digit number. Solvers of cryptarithms are often not this lucky and they do have to search some range of numbers to find the solution. Here are some ways this might have been done on this problem.

We always want to cut down the range of the search as much as possible before we start the brute-force search. As before we can tell from the equation that A is even, and that it is 2 because otherwise the product would be too large. This means instead of searching all 90 000 5-digit numbers we only have to search the 10 000 that start with 2. We can further reduce the number of possibilities using the ideas of casting out 9s and casting out 11s. Looking at the equation modulo 9, we see that 4 times the sum of the digits is equal the sum of the digits, so 3 times the sum of the digits is 0 (modulo 9), and therefore 3 divides the sum of the digits and therefore 3 divides ABCDE. Looking at the equation modulo 11, we get

so 3(A - B + C - D + E) \equiv 0 \pmod{11}, so the original number ABCDE is also a multiple of 11. Now we have cut the problem down to testing 5-digit numbers that start with 2 and are a multiple of 33; there are about 300 of these (compared to the 90 000 that we started with) and you can write down and test these in a few minutes.

Challenge: Use these ideas to investigate the (apparently) simpler equation 2 \cdot ABCD = DABC.

Challenge: The solution to the 5-digit problem, 21978, has many other factors besides 3 and 11; its prime factorization is 21978 = 2^1 \, 3^3 \, 11^1 \, 37^1, and one especially interesting factorization is 21978 = 22 \cdot 999 which is reminiscent of casting out 9s. Is there any way to infer some of these factors directly from the equation, or is the appearance of these factors just a coincidence?

Is Trial and Error Really a "Method"?

Yes, although as an intellectual field it belongs more to Computer Science than to Mathematics. The field of Artificial Intelligence in particular is concerned mainly with systematic ways of performing trial and error. For example, chess-playing programs and machines perform a very rapid search of the consequences (for the next few moves) of each possible move from the current position, and use the results to decide the best next move. A brute-force search of all possibilities would take too long, so these devices use many heuristics to decide which paths are worth looking at.

References

• Wikipedia has an article on cryptarithms.
• George Pólya, How To Solve It, Princeton University Press, 1957, "Puzzles", pp. 160-162.
• Peter Norvig, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Morgan Kaufmann, 1992. Very readable; covers most AI techniques in depth.
• The Cryptarithmetic Puzzle Solver only does addition problems, but it can also do our problem because we can write it as ABCDE + ABCDE + ABCDE + ABCDE = EDCBA (try it!).