Recently I came accross the following puzzle:
Where ,,,, are distinct digits, and where ,≠0, what 5 digit integer satisfies the condition below?
$$\text{ABCDE} \times 4 = \text{EDCBA}$$
I now know that puzzles of this form are called "cryptarithmetic" puzzles, or "cryptarithms."
The two methods I've seen people use to solve these puzzles are:
- Brute force computer search, and
- Induction-based logic, e.g., example answer.
I've been wondering if there is a different way to find solutions, using simultaneous equations.
My first attempt was to set up a matrix system for the numbers in their base 10 representation. I tried the following equation, with the intention of rearranging and solving for the unknowns:
$$ 4 \times \begin{bmatrix} 10^4 & & & & \\ & 10^3 & & & \\ & & 10^2 & & \\ & & & 10^1 & \\ & & & & 10^0 \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} = \begin{bmatrix} & & & & 10^4 \\ & & & 10^3 & \\ & & 10^2 & & \\ & 10^1 & & & \\ 10^0 & & & & \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} $$
However I quickly realized that this wouldn't work, because multiplying certain digits by 4 result in a two digit number, meaning that each of the different digit equations cannot be treated separately.
I came to the conclusion that I would have to account for carrying remainders over to the equation that represented the next power of 10. I came up with an idea of how to do this with modulo arithmetic:
\begin{align*} A &= (4 \cdot E ) \mod 10 \\ B &= (4 \cdot D + x_1 ) \mod 10 \\ C &= (4 \cdot C + x_2 ) \mod 10 \\ D &= (4 \cdot B + x_3 ) \mod 10 \\ E &= (4 \cdot A + x_4 ) \mod 10 \end{align*}
... where $x_1,\dots x_4$ are the following divisors:
\begin{align*} x_1 &= \lfloor(4 \cdot E)/10 \rfloor \\ x_2 &= \lfloor(4 \cdot E + x_1)/10 \rfloor \\ x_3 &= \lfloor(4 \cdot E + x_2)/10 \rfloor \\ x_4 &= \lfloor(4 \cdot E + x_3)/10 \rfloor \end{align*}
This is starting to feel like a manageable approach, but I'm unsure how to progress with solving this system of equations. If I know the values $x_1,\dots x_4$ a priori, I can quite easily solve the modulo system of equations with standard techniques. (I've checked this in Mathematica and I found the correct solution.) However it's not clear how to modify the system of equations to also solve for the values $x_1,\dots x_4$. Any thoughts?