Christmas Cryptarithm: "HERES+MERRY+XMAS=READER"

I got this puzzle from some others:

\begin{array}{c c c c c c}&\mathrm H&\mathrm E&\mathrm R&\mathrm E&\mathrm S\\&\mathrm M&\mathrm E&\mathrm R&\mathrm R&\mathrm Y\\+&&\mathrm X&\mathrm M&\mathrm A&\mathrm S\\\hline\mathrm R&\mathrm E&\mathrm A&\mathrm D&\mathrm E&\mathrm R\end{array}

Find the letters such that every letter is a distinct digit, and that there are no leading $0$'s.

We only managed to solve this by breaking it down to some cases and then simply brute forcing it. Is there any way to do this without brute force though?

Answer:

$\mathrm{(A, D, E, H, M, R, S, X, Y)} = (8, 0, 4, 6, 7, 1, 3, 9, 5)$

Code: Try it online

Breakdown of what we managed to get:

We started by noting $\mathrm R$ was either $1$ or $2$.

From the rightmost column, $\mathrm{Y = (R - 2S) \% 10}$.

From the next column, $\mathrm{A = 10 - R - \lfloor 2S+Y \rfloor}$, where the last bit is from a carry digit.

From the next column, $\mathrm{D = (M + 2R + 1) \% 10}$. The $1$ comes from a guaranteed carry digit from the previous column.

From the next column, $\mathrm{X = (A - 2E - \lfloor (M+2R+1)/10 \rfloor) \% 10}$, which also uses a carry.

And from the leftmost column, $\mathrm{H = 10 + E - M - \lfloor (2E+x)/10 \rfloor}$.

Enumerating all such possible values for $\mathrm{R,S,M,E}$, and checking each one, results in the above answer.

Solution 1:

$$2S+Y=1+10\alpha$$ $$A+R+\alpha=10$$ $$M+2R+1=D+10\gamma$$ $$2E+X+\gamma=A+10\epsilon$$ $$H+M+\epsilon=10R+E$$ $\alpha,\gamma,\epsilon \le 2$ and, since $R\ne 0$, $R$ must be $1$. From $2S+Y=1+10\alpha$ we have $\alpha=2$ and therefore $A=7$ or $\alpha=1$ and therefore $A=8$. We will deal with these possibilities separately.

If $(A,R)=(7,1)$ and $(S,Y)=(9,3),(8,5)\text { or }(6,9).$

$$(1) M+3=D+10\gamma$$ $$(2) 2E+X+\gamma=7+10\epsilon$$ $$(3) H+M+\epsilon=10+E$$

The case $\epsilon=\gamma=0$

From (2) we have $(E,X)=(2,3).$ From (3)-(1) we have $\{D,H\}=\{6,9\}.$ Then $M=D-3= \text{3 or 6}$, a contradiction.

The case $\epsilon=0,\gamma=1$

From $M=D+7$, we have $(D,M)=(2,9).$ Then $X$ cannot be $0$ and so $2E+X=6$ gives $(E,X)=(0,6).$ Then $H=1+E=1$, a contradiction.

If $\epsilon\ne 0$

Adding equations (2) and (3), $E+H+M+X+\gamma=17+9\epsilon\ge 26$. However, $E+H+M+X\le 9+6+5+4=24$ and $\gamma\le1$ so this is impossible.

If $(A,R)=(8,1)$ and $(S,Y)=(4,3),(3,5)\text { or }(2,7).$

$$(1) M+3=D+10\gamma$$ $$(2) 2E+X+\gamma=8+10\epsilon$$ $$(3) H+M+\epsilon=10+E$$

The case $\epsilon=\gamma=0$

From (2) we have $(E,X)=(4,0)\text { or }(2,4).$ From (3)-(1) we have $E=2,\{D,H\}=\{6,9\}.$ Then$(S,Y)=(3,5)$ and $M=D-3= \text{3 or 6}$, a contradiction.

The case $\epsilon=0,\gamma=1$

From $M=D+7$, we have $(D,M)=(0,7) \text { or } (2,9).$ Then $(S,Y)=(4,3)\text{ or } (3,5).$ Then $0$ and $3$ are already assigned and so $2E+X=7$ gives $(E,X)=(0,7).$ Then $H+M=10$ and $H=1$ or $3$, a contradiction.

If $\epsilon\ne 0$

Adding equations (2) and (3), $E+H+M+X+\gamma=18+9\epsilon$. Therefore $\epsilon=1$.

Since $8$ is already assigned either $$\{E,H,M,X\}=\{9,7,6,5\},\gamma=0 \text { or } \{E,H,M,X\}=\{9,7,6,4\},\gamma=1. $$ In the first case, $2E+X=18$ and $X$ is even, then $X=6$ and $E=X$, a contradiction.

In the second case, $2E+X=17$ and $X$ is odd, then

$X=9,E=4,M=D+7$. Therefore $D=0,H=6,M=7.$ Finally, the only possibility for $S$ and $Y$ is $S=3,Y=5$.

Solution 2:

We started by noting $\mathrm R$ was either $1$ or $2$.

There is no way $R$ can be $2$: $H$ and $M$ can at most be $8$ and $9$, and so the sum of $HERES$ and $MERRY$ is below $190000$, and with $XMAS$ below $10000$, the total sum is below $200000$. So $R$ has to be $1$

But other than that, I don't see anything quick.

Solution 3:

An improved approach

From right to left, let the carries be $\alpha,\beta,\gamma,\delta,\epsilon$. Note that no carry can be greater than $2$ and that $\beta$ and $\epsilon$ are no greater than $1$.

$R$ is non-zero and so $R=\epsilon=1$. The first two equations from the right are then \begin{align}2S+Y&=1+10\alpha\\A+1+\alpha&=10\beta\end{align} Noting that $Y$ is odd and greater than $1$, we have the following possibilities.

$\alpha=1,\beta=1,A=8,R=1$and $(S,Y)=(4,3),(3,5)\text { or }(2,7) $

$\alpha=2,\beta=1,A=7,R=1$ and $(S,Y)=(9,3),(8,5)\text { or }(6,9) $

The remaining equations are \begin{align} M+3&=D+10\gamma,&\gamma\le 1 \tag1 \\ 2E+X+\gamma&=A+10\delta \tag2 \\ H+M+\delta&=10+E \tag3 \end{align} The case $\delta=0$

Consider equation $(2)$. If $E=0$, then $X\ne A$ and so $\gamma=1$. Then $D$ is neither $0$ nor $1$ and so, from $(1)$, $M=9$. Then, from $(3)$, $H=1$, a contradiction. Now $X\ne0$ and so $E$ and $X$ are both at least $2$.

If $A=7$, the only solution of $(2)$ is then $\gamma=0,E=2,X=3$. Then the only possibility for equation $(3)$ is $\{H,M\}=\{4,8\}$ and then $D=M+3=7$ or $11$, a contradiction.

If $A=8$, then $\{S,Y\}$ contains either $2$ or $3$ and so $\{E,X\}\ne \{2,3\}$. The only solution of $(2)$ then gives $\gamma=0,E=2,X=4, R=3,S=5$. Then there is no permissible solution of equation $(3)$.

The case $\delta\ne0$

Adding $(2)$ and $(3)$ gives $$E+H+M+X+\gamma=A+10+9\delta\ge A+19.$$ If $\alpha=2$, then $7$ and either $8$ or $9$ are already allocated and so $E+H+M+X\le 9+6+5+4=24$, a contradiction. Therefore $\alpha=1,A=8$ and either $$\{E,H,M,X\}=\{9,7,6,5\},\gamma=0 \text { or } \{E,H,M,X\}=\{9,7,6,4\},\gamma=1. $$ In the first case, $2E+X=18$ and $X$ is even, then $X=6$ and $E=X$, a contradiction.

In the second case, $2E+X=17$ and $X$ is odd, then $X=9,E=4,M=D+7$. Therefore $D=0,H=6,M=7.$ Finally, the only possibility for $S$ and $Y$ is $S=3,Y=5$.

$(A, D, E, H, M, R, S, X, Y) = (8, 0, 4, 6, 7, 1, 3, 9, 5)$

Solution 4:

Using Bram28's work, we have $R = 1$.

Now consider,

where the representation base is $b = 10$ and we have the $b^k$ columns.

Since you don't want to solve this by brute force, you can probe the puzzle problem and eventually gravitate to a hypothesis about it:

(*) The carry on each column $b^k$ ( $\;k \in \{0,1,2,3,4\}\;$ ) sum is equal to $1$.

It is a leap of faith that column $b^2$ will have a carry of $1$, but 'everything goes right and nothing breaks' as you 'play' with that puzzle scenario.

Taking (*) as true we modify the puzzle to

where $Z = X + 1$ and all column additions are now modulo $10$ and the carries are accounted for.

We proceed with the prayer that we don't have to abandon our hypothesis, listing things that can be claimed as true (under the hypothesis) and sketching some arguments.

1). Examining COL $b^4$ we see that neither $H$ nor $M$ can be equal to $9$.
$\quad >$ If say, $H = 9$, then $M = E$.

2). Examining COL $b^2$ we see $M = 7$ or $M = 9$.
$\quad >$ With $M \ge 7$ we exclude $M = 8$ since $D \ne R$.

3). We conclude that $M = 7$ and $D = 0$.

4). Examining COL $b^1$ we see that $A = 8$.

5). Examining COL $b^3$ we see that $E \ne 2$ and $E \ne 3$.
$\quad >$ By (*), $E + E + X + 1 = 18$, but $X \lt 10$.

6). Examining COL $b^3$ we see that $E \ne 5$.
$\quad >$ $X \ne M = 7$.

7). Examining COL $b^3$ we see that $E \ne 6$.
$\quad >$ Not possible for $E = X = 6$.

8). Examining COL $b^4$ we see that $E \ne 9$.
$\quad >$ By (*) $H + 7 + 1 = 19$ implying that $H = 11$.

9). We conclude that $E = 4$.

We can now update the puzzle picture.

The only digits that still remain open to assignment are $2$, $3$ and $5$.

10). Examining COL $b^0$ we see that $S = 3$ and $Y = 5$.

CHECK