Cryptogram - Problem Solving

$$\large{\begin{array}{ccccccc} && & \color{#20A900}G & \color{#20A900}R & \color{#20A900}E & \color{#20A900}E&\color{#20A900}N\\ && \color{#ff7e00}O& \color{#ff7e00}R & \color{#ff7e00}A &\color{#ff7e00} N & \color{#ff7e00}G&\color{#ff7e00}E\\ + && & & & \color{#D61F06}R & \color{#D61F06}E&\color{#D61F06}D\\ \hline && \color{#ffbf00}Y&\color{#ffbf00}E &\color{#ffbf00} L& \color{#ffbf00}L &\color{#ffbf00}O&\color{#ffbf00}W\\ \hline \end{array}}$$

A cryptogram is a mathematical puzzle, where various symbols are used to represent digits, and a given system has to be true. In the previous page, we have discussed various techniques when tackling a cryptogram. However, it is not immediately clear how to solve cryptogram that involves various techniques. For example, for the cryptogram above, for the uninitiated, we could start by considering the case $Y=2, O=1,G=5,R=6,E=1,N=3$. It would be unwise to begin with the trial and error approach because there is close to $9!=362880$ ways to begin with it. Thus it is definitely not an ideal way to approach it by hand. Hence, it will be beneficial to know which technique is best applicable.

In this wiki, we will work through various examples, and extensively apply this table to identify the conditions and techniques to use.

We should note that all cryptograms that have the subtractions can be converted to a strictly addition problem. For example, $X-Y=Z$ can be converted to $Y+Z=X$.

$$\large{\begin{array}{ccccccc} && & & L& I &S&P\\ -&& & & & L & L&P\\ \hline && & & & P & L&I\\ \hline \end{array}}$$

For the above cryptogram, solve for the unknown letters and find the possible value(s) of the 5-digit number $\overline{SPILL}$.

---

We first convert this cryptogram to an addition problem.

$$\large{\begin{array}{ccccccc} && & & & L & L&P\\ +&& & & & P & L&I\\ \hline && & & L& I &S&P\\ \hline \end{array}}$$

Since this is a simple addition problem, it might be beneficial to apply Converting cryptogram to equation, Rearrangement of column and/or Carry over. However, because there are so many unknowns from the start, we will not accomplish much. Since there are $P$'s on both sides in the first column, it's best to start to apply (3) Carry over:

For the first column, we have the last digit of $P +I$ as $P$, so $I$ must equal 0.

Since we are taking the sum of two 3 digit numbers, the carry over for the third column is non-zero and must equal 1, implying $L = 1$. This simplifies the cryptogram to:

$$\large{\begin{array}{ccccccc} && & & & 1 &1&P\\ +&& & & & P & 1&0\\ \hline && & & 1& 0 &S&P\\ \hline \end{array}}$$

After the value of $L$ is known, we can rearrange the letters/digits in their respective columnns such that there are at most 2 symbols in each column. Thus we apply (2) Rearrangement of columns:

$$\large{\begin{array}{ccccccc} && & & & 1 &1&0\\ +&& & & & P & 1&P\\ \hline && & & 1& 0 &S&P\\ \hline \end{array}}$$

Because all the values in the first column is known, and there is no carry over. We can eliminate the first column. Therefore we apply (3) Carry over:

$$\large{\begin{array}{cccccc} & & & & 1 &1\\ +& & & & P & 1\\ \hline & & & 1& 0 &S\\ \hline \end{array}}$$

Since there are a few symbols left, we can apply (1) Converting cryptogram to equation:

Solving for $S$ gives $S=1+1=2$. Finally, we can convert the cryptogram to an equation: $11 + \overline{P1} = 102 \Rightarrow \overline{P1} = 102 - 11 = 91 \Rightarrow P = 9$.

Hence, $\overline{SPILL} = 29011. \ _\square$

$$\large{\begin{array}{ccccccc} && & K & Y & O & T&O\\ +&& & O & S & A & K&A\\ \hline && & T & O& K &Y&O\\ \hline \end{array}}$$

For the above cryptarithm, solve for the unknown letters and find the possible value(s) of the 5-digit number $\overline{TOAST}$.

---

Since there are many unknown letters to consider, it is very likely to consider trial and error as a possible approach. However we should always reduce the number of possible cases to check. Thus we should begin with applying (8) Trial and error then follow up with (3) Carry over:

From the first column, we have $O + A \equiv O \pmod{10} \Rightarrow A = 0$ only. Now, because $A=0$, the third column $O + A \equiv K \pmod{10}$ implies that there was a carry in the second column and thus $O + 1 = K$ and $10\leq T+K<20$.

From the fourth column, there may or may not be carry over, so $c_4 = 0 \text{ or }1$. Also, the fifth column gives

$$\begin{aligned} K + O + c_4 = T \Rightarrow (O+1)+ O +c_4 &= T \\ \Rightarrow 2O + 1 + c_4& = T. \qquad (\ast) \end{aligned}$$

Since from OSAKA we know that the leading digit is not 0, i.e $O\ne 0,$ from $(\ast)$ we have $1\leq 2O + 1 +c_4 < 10 \Rightarrow 1\leq O \leq 4$ only. Then since $O + 1 = K$ from above, $2 \leq K \leq 5$.

Notice how we have reduced the possibility of $1\leq K\leq9$ to $2\leq K \leq5$! So we are left to check less cases. Again, we apply (8) Trial and error & (3) Carry over for the values of $K$:

Let's start with the extreme values first (the largest and smallest), that is, for $K =2$ or $K=5$. We start with them first because they usually tend to tighten the bounds and quickly force out a solution or contradiction. However, keep in mind that this method does not always guarantee results.

$\large {\boldsymbol{\text{(I) Suppose K = 2}}}$:

Then $O=1$. Because we know from that there is a carry from the second column, then $T+K \geq 10 \Rightarrow T = 8,9$. But from $(\ast)$ we have $2O + 1 + c_4 \leq 4 < T,$ which is impossible. So $K = 2$ is not a possible solution. Notice that we don't need to solve the entire cryptogram to determine that $K\ne 2$.

$\large {\boldsymbol{\text{(II) Suppose K = 5}}}$:

Then $O = 4$, then from $(\ast)$, we have $2O + 1 +c_4 < 10 \Rightarrow c_4 = 0, T = 9$. With $T=9, K = 5$, from the second column, we have $T+K \equiv Y \pmod{10} \Rightarrow Y = 4$. But $O$ and $Y$ must be distinct. This means that $K = 5$ is also impossible.

Finally, we are left to check for $K = 3$ or $K=4$ only. Amazing isn't it? After bounding the possible values of the values above, we just need to check for two cases!

$\large {\boldsymbol{\text{(III) Suppose K = 3}}}$:

Then $O = 2$, and from $(\ast)$, we have $T = 5 \text{ or } 6$ only. But since we know that the second column has a carry, then $T + K \geq 10$ can't be satisfied. So $K \ne 3$.

So we are left with $K=4$. But of course, we should check whether each of these letters are distinct. With $K=4$, $O = 3$, then $T = 7 \text{ or } 8$.

So far, we have confirmed that $K = 4, O = 3, A = 0$. What's left to solve is the values of $T,Y$ and $S$. Once more, we apply (8) Trial and error & (3) Carry over for the values of $K$:

Suppose $T = 8$, then $Y = T+K \bmod{10} = 2$. Also, from $(\ast)$, we have $c_4 = 1$. This means that from the fourth column, $Y+S - O > 10 \Rightarrow 2 + S-3 > 10,$ which means that $S$ is at least a two digit integer, which is impossible. So $T= 7$ only.

Now to solve for $Y$ and $S$, from the second column, $T+K \equiv Y \pmod{10} \Rightarrow Y = 1$. Since we know from $(\ast)$ that $c_4= 0$, then there is no carry over in the fourth column, that is $Y+S= 0 \Rightarrow S = 2$.

Putting them all together shows that $41373 + 32040 = 73413$ is indeed true.

Hence, $\overline{TOAST} = 73027. \ _\square$

From the examples shown above, we can note that the two techniques: Carry Over and Trial and error are often used together. This is because Carry Over gives us an additional insight to the restriction to the unknowns and Trial and error is used to pinpoint the exact values of these unknowns.

$$\large{\begin{array}{ccccccc} && & & 1 & 8 & 3&5\\ \times && & & 7 & 2 & 4&6\\ \hline A&B& 2&9& 6 & 4 &1&0\\ \hline \end{array}}$$

The above shows an incomplete long multiplication. We can obviously multiply out both numbers to find the unknown non-zero single digit integers $A$ and $B.$ However, that can be a tedious task. Without performing the long multiplication, but instead using the techniques we have learned above, show that $A = 1$ and $B = 3$.

---

Because there are only a few symbols to consider, it is a viable approach to apply (1) Converting cryptogram to equation:

We can represent this product as $P \times Q = R$ for $P = 1835, Q = 7246$ and $R$ as the 8-digit number.

Because $R = P \times Q < 2000 \times 8000 = 16000000$ with a leading digit of the leftmost column to be 1, this forces $A$ to be less than or equals to $1$ only. Thus $A = 1$.

Because we can gain the insights for modulo a certain value, apply (4) Divisibility Rules:

It's simplest to consider the divisibility of 9 as we are only taking the sum of its digits. We have $P \times Q \equiv R \pmod 9$, with $P \equiv 1 + 8 + 3 + 5 \equiv -1$ and $Q\equiv 7+2+4+6\equiv 1$. Thus $R \equiv 1 \times -1 \equiv 8$, which means that when the sum of the digits of $R$ is divided by 9, it yields a remainder of 8. So $$A+B+2+9+6+4+1+0 \equiv 8 \pmod9 \Rightarrow B= 3 \text{ only}. \ _\square$$

$$\large{\begin{array}{ccccccc} && & & & A & B&C\\ \times && & & & & B&C\\ \hline && & D & E& E &B&C\\ \hline \end{array}}$$

For the above cryptogram, each letter represents a distinct single digit non-negative integer, with $A,B$ and $D$ being non-zero. Find the value of $D$.

---

Since this is a multiplication between two numbers, factoring of terms and Chinese Remainder Theorem are possible viable approaches . However, since the last two digits of these three numbers are the same, we can Apply (7) Chinese Remainder Theorem:

By considering the last two digits, $\overline{ABC} \equiv \overline{BC}\equiv \overline{DEEBC} \equiv \overline{BC} \pmod{100}$.

So we have $x^2 -x \equiv 0 \pmod {100}$. Like the earlier example, we have $x \equiv 25, 76 \pmod{100}$.

This means that $\overline{BC} = 25, 76$ only.

So what's left to check? Well, it's just the possible values of $A$. Because knowing value of $A$ can solve the entire long multiplication, the most sensible approach is to apply (8) Trial and error:

Suppose $\overline{BC} = 25$. We apply trial and error for the possible values of $A$, which are $1,2,\ldots,9$. By inspection, none of them yields a product in the form of $\overline{DEE25}$.

Thus $\overline{BC}= 76$. Using the same approach in the earlier paragraph, we get $176 \times76=13376$. Hence $D = 1. \ _\square$

$$\large{\begin{array}{ccccccc} && & &A & B & C&C\\ \times && & & C & D & A&A\\ \hline && & &A & B & C&C\\ && &A & B & C&C & \\ && D &E & C& B& & \\ &C& F &E &E& & & \\ \hline &D& B& G & H& I&F&C\\ \hline \end{array}}$$

For the letters used in the cryptogram above, find the value of $\overline{CHIEF}$.

---

Since we have additions of 4 rows of multiplications, we can obtain the additional information by applying (1) Converting the cryptogram to equations:

From the very top, the third row shows that

$$\overline{ABCC} \times A = \overline{ABCC} \Rightarrow A = 1 .$$

And the fifth row shows that

$$\overline{ABCC} \times D = \overline{1BCC} \times D = \overline{DECB} .$$

By considering the last digit of the last equation, we have

$$C\times D \equiv B \pmod{10}. \qquad \ (\ast)$$

If we reconstruct the last cryptogram again with the knowledge of $A=1$, we have

$$\large{\begin{array}{ccccccc} && & &1& B & C&C\\ \times && & & C & D & 1&1\\ \hline && & &1 & B & \color{#EC7300}C&C\\ && &1 & B & C&\color{#EC7300}C & \\ && D &E & C& B& & \\ &C& F &E &E& & & \\ \hline &D& B& G & H& I&\color{#EC7300}F&C\\ \hline \end{array}}$$

As highlighted above, the brown colored symbols show an addition. Since there is only at most 2 unknowns in the column, we can apply (1) Converting the cryptogram to equations:

$$2C \equiv F \pmod {10}. \qquad (\ast \ast)$$

Refer to the $5^{\text{th}}$ and $6^{\text{th}}$ rows highlighted in blue below. Because there is a sum of two numbers $\overline{DECB00}$ and $\overline{CFEE000}$ to produce the number $\overline{DBGHIFC} ,$ we can apply (3) Carry over:

$$\large{\begin{array}{ccccccc} && & &1& B & C&C\\ \times && & & C & D & 1&1\\ \hline && & &1 & B & C&C\\ && &1 & B & C&C & \\ && \color{#3D99F6}D &\color{#3D99F6}E & \color{#3D99F6}C& \color{#3D99F6}B& & \\ &\color{#3D99F6}C& \color{#3D99F6} F &\color{#3D99F6}E &\color{#3D99F6}E& & & \\ \hline &\color{#3D99F6}D&\color{#3D99F6} B& \color{#3D99F6}G & \color{#3D99F6}H& \color{#3D99F6}I&\color{#3D99F6}F&\color{#3D99F6}C\\ \hline \end{array}}$$

Looking at the leftmost column, we see that the carry over $c_6$ must be equal to 1 because $C\ne D$. Thus $C + 1 = D. \qquad (\ast \ast \ast)$

Because $\overline{ABCC} \times \overline{CDAA}$ is a 7-digit number, we start by bounding the equation. That is, apply (1) Converting cryptogram to an equation:

Since $2000\times 5000$ is an 8-digit number, then $C < 5$. With $C\ne A$, then $C = 2,3$ or $4$ only. Hence connecting $(\ast), (\ast \ast)$ and $(\ast \ast \ast)$ gives

$$(C,D,F,B) = (2,3,4,6), (3,4,6,2),(4,5,8,0).$$

Now we are left with 3 cases to check only! Thus we apply (8) Trial and error. By inspection, we have

$$C=3 ,D=4, F=6, B=2.$$

Completing the entire cryptogram yields the values of $E,G,H,I$ as $9,0,5,7,$ respectively. Thus, $\overline{CHIEF} = 35796. \ _\square$

From the examples shown above, we can note that the two techniques: Divisibility Rules and Modular Arithmetic are often used together. This is because Divisibility Rules is used in conjunction with Modular Arithmetic as the former is a further generalization of the latter.