Placing the $21$ two-digit primes into a grid, such that primes in adjacent squares have either the same tens digit or ones digit

Question

This is USAMTS round 3, problem 1 of the 2020-2021 Academic Year.

Place the 21 2-digit prime numbers in the white squares of the grid on the right so that each two-digit prime is used exactly once. Two white squares sharing a side must contain two numbers with either the same tens digit or ones digit. A given digit in a white square must equal at least one of the two digits of that square's prime number.

They didn't provide a detailed explanation of how they got the (unique) solution on their website, so I was wondering if someone could explain how to come up with the solution?

I tried using casework, but there seems to be too many possibilities to consider. Number the white squares from 1 to 21 from left to right and top to bottom and let $c_i$ be the number in square i. Clearly, it seems easier to consider squares containing 2, 4, or 5, but even then I've not sure how to make reasonable deductions.

For ease of reference, define the following sets $$\begin{align} P_1 &:= \{13,11,17,19,31,41,61,71\} \\ P_2 &:= \{23,29\} \\ P_3 &:= \{31,37,23,13,43,53,73,83\}\\ P_4 &:= \{41,43,47\} \\ P_5 &:= \{53,59\} \\ P_6 &:= \{61,67\} \\ P_7 &:= \{73,37,79,71,17,47,67,97\} \\ P_8 &:= \{83,89\} \\ P_9 &:= \{19,29,59,79,89,97\} \end{align}$$

Obviously, $c_1,c_3 \in P_3, c_4 \in P_2, c_{12}\in p_5, c_{19},c_{20}\in P_1, c_{18}\in P_4.$

For instance, squares 5 and 8 both contain the digit 9 in the units digit if $c_4=29$ since $c_3 = 23$, which immediately implies that $c_4\neq 29$.

So $c_4 = 23$.

$c_3$ cannot equal $29.$ So $c_3$ is either $13,43,53,73,73,$ or 83. Suppose $c_8$ ends in a 3. Then $c_3$ and $c_8$ have distinct tens digits and the same units digit. Thus if $c_7$ does not end in a 3, it must share the tens digit of $c_8$ and $c_3$, a contradiction. Hence $c_7$ ends in a 3. $c_{11}$ cannot share the 3 with $c_7$ and $c_7$ doesn't contain a 9 as its tens digit.

If $c_5=53,$ then one of $c_9$ or $c_{16}$ ends in 3.

If $c_{18} = 43,$ then $c_{19} = 41$ or $13$. If $c_{18} = 47,$ then $c_{19} = 41$ or $17$.

So basically, I've only been able to deduce with certainty that $c_4 = 23$ and it seems hard to find the possibilities for other numbers.

Answer 1

You already got $c_4=23$.

We use the following facts.

Fact 1 : The number of our primes of the form $\circ 3$ is $6$.

Fact 2 : The number of our primes of the form $\circ 9$ is $5$.

Fact 3 : The number of our primes of the form $\circ 1$ is $5$.

Fact 4 : The number of our primes of the form $\circ 7$ is $5$.

Fact 5 : The number of our primes of the form $1\circ $ is $4$.

• $c_{12}=59$.
  (Suppose that $c_{12}=53$.
  If $c_9=59$, then either $c_5$ or $c_8$ has to be $53$, which is a contradiction. So, $c_9$ is of the form $\circ 3$.
  Then, $c_3,c_4,c_5,c_7,c_8,c_9,c_{12}$ are of the form $\circ 3$. From fact 1, this is impossible.)

• $c_9=A9$.
  (Suppose that $c_9=53$. Then, since $c_{16}$ is of the form $\circ 9$, $c_{21}$ is of the form $\circ 3$. So, $c_3,c_4,c_5,c_7,c_8,c_9,c_{21}$ are of the form $\circ 3$. From fact 1, this is impossible.)

• $c_{21}=B3$.
  (If $c_{16}=53$, then $c_{21}$ is of the form $\circ 3$.
  If $c_{16}$ is of the form $\circ 9$, then $c_{21}$ is of the form $\circ 3$.)

• $c_3=C3$.

• $c_{11}=D9$.
  (If $c_5=29$, then since $c_7,c_8$ are of the form $\circ 3$, $c_{11}$ is of the form $\circ 9$.
  If $c_8=29$, then since $c_7$ is of the form $\circ 9$, $c_{11}$ is of the form $\circ 9$.)

• $C\not=1$.
  (Suppose that $C=1$. Then, $B\not=1$ because of $c_{21}=B3$. Also, we have $c_{20}=B1,c_{19}=E1,c_{18}=41$.
  If $c_5=29$, then we have $c_8=A3,c_7=D3$, so $B=7$ because $c_{20}=B1,c_{21}=B3,c_3=13,c_{18}=41$. Also, $A=8$ because $c_8=A3,c_9=A9,c_3=13,c_4=23,c_{12}=59,c_{21}=73$. However, there is no such $D$ because $c_7=D3,c_{11}=D9,c_3=13,c_4=23,c_{12}=59,c_{21}=73,c_8=83$. So, $c_8=29$.
  
  We have $c_5=A3$ because $c_4=23,c_8=29,c_9=A9$. Also, $c_7=19$ because $c_8=29,c_{11}=D9,c_3=C3$. $$ \begin{array}{c|c|c|c|c} & & 13 & 23 & A3\\\hline & \times & 19 & 29 & A9\\\hline & \times & D9 & \times & 59 \\\hline & & &\times & \\\hline & 41 & E1 & B1 & B3\end{array} $$ So, $B=7$ because $c_{20}=B1,c_{21}=B3,c_3=13,c_4=23,c_{18}=41$. Also, $A=8$ because $c_5=A3,c_9=A9,c_3=13,c_4=23,c_{12}=59,c_{21}=73$. We have $D=7$ because $c_{11}=D9,c_7=19,c_9=29,c_{12}=59,c_9=89$. It follows from fact 2 that $c_{15}=c_{20}=71$. This is a contradiction.)

• $c_2=C1$ and $c_{1}=31$.
  (If $c_5=29$ and $c_2=13$, then $c_1,c_2,c_3,c_4,c_7,c_8,c_{21}$ are of the form $\circ 3$. From fact 1, this is impossible.
  If $c_8=29$ and $c_2=13$, then $c_7,c_8,c_9,c_{11},c_{12}$ are of the form $\circ 9$. From fact 2, we have $c_{16}=53$, so $c_1,c_2,c_3,c_4,c_5,c_{16},c_{21}$ are of the form $\circ 3$. From fact 1, this is impossible.)

• $B\not=1$.
  (Suppose that $B=1$.
  If $c_5=29$, then $c_{8}=A3,c_7=D3$. $$ \begin{array}{c|c|c|c|c} 31 & C1 & C3 & 23 & 29\\\hline & \times & D3 & A3 & A9\\\hline & \times & D9 & \times & 59 \\\hline & & & \times & \\\hline & & & & 13\end{array} $$ We have $A=7,8$ because $c_8=A3,c_9=A9,c_{21}=13,c_4=23,c_{12}=59$. Also, $D=7,8$ because $c_7=D3,c_{11}=D9,c_{21}=13,c_{4}=23,c_{12}=59$. So, $C=4$ because $c_2=C1,c_3=C3,c_{21}=13,A3$ or $D3=73$.
  
  If $c_{15}=19$, then $c_{19}=1G,c_{18}=4G$. $$ \begin{array}{c|c|c|c|c} 31 & C1 & C3 & 23 & 29\\\hline & \times & D3 & A3 & A9\\\hline & \times & D9 & \times & 59 \\\hline & & 19 & \times & \\\hline & 4G & 1G & & 13\end{array} $$ So, $c_{14}=c_{19}=1G$. This is a contradiction. So, $c_{15}=71$ (this is because $p=19,71$ are the only possible primes satisfying $c_{15}=p$). Then, $c_1,c_2,c_{14},c_{15},c_{18},c_{19}$ are of the form $\circ 1$. From fact 3, this is impossible.
  If $c_8=29$, then $c_5=A3,c_7=C9$. $$ \begin{array}{c|c|c|c|c} 31 & C1 & C3 & 23 & A3\\\hline & \times & C9 & 29 & A9\\\hline & \times & D9 & \times & 59 \\\hline & & & \times & \\\hline & & & & 13\end{array} $$ So, $C=7$ because $c_2=C1,c_3=C3,c_7=C9,c_{21}=13$. Also, $A=8$ because $c_5=A3,c_9=A9,c_{21}=13,c_4=23,c_{12}=59,c_3=73$. We have $D=1$ because $c_{11}=D9,c_8=29,c_{12}=59,c_7=79,c_9=89$. It follows from fact 2 that $c_{11},c_{15},c_{19},c_{20},c_{21}$ are of the form $1\circ$. From fact 5, this is impossible.)

• $c_8=29$.
  (Suppose that $c_5=29$. We have $c_8=A3,c_7=D3$.
  If $c_{20}=13$, then it follows from fact 1 that $c_{16}=B9$. $$ \begin{array}{c|c|c|c|c} 31 & C1 & C3 & 23 & 29\\\hline & \times & D3 & A3 & A9\\\hline & \times & D9 & \times & 59 \\\hline & & & \times & B9 \\\hline & & & 13 & B3\end{array} $$ We have $A=7,8$ (because $c_8=A3,c_9=A9,c_{20}=13,c_4=23,c_{12}=59$), $B=7,8$ (because $c_{21}=B3,A_{16}=B9,c_{20}=13,c_4=23,c_{12}=59$), $D=7,8$ (because $c_7=D3,c_{11}=D9,c_{20}=13,c_4=23,c_{12}=59$). This is impossible. So, $c_{20}=B1$.
  If $c_{16}=B9$, then we have $$ \begin{array}{c|c|c|c|c} 31 & C1 & C3 & 23 & 29\\\hline & \times & D3 & A3 & A9\\\hline & \times & D9 & \times & 59 \\\hline & & & \times & B9 \\\hline & & & B1 & B3\end{array} $$ So, we have $A=1,7,8$ (because $c_8=A3,c_9=A9,c_4=23,c_{12}=59$), $B=1,7$ (because $c_{20}=B1,c_{21}=B3,c_{16}=B9,c_4=23,c_{12}=59$), $C=1,4,7$ (because $c_2=C1,c_3=C3$), $D=1,7,8$ (because $c_7=D3,c_{11}=D9,c_4=23,c_{12}=59$). Since $\{A,B,D\}=\{1,7,8\}$, we have $C=4$. Since $c_{19}=\circ 1$, we have $c_{18}=c_{2}=41$. This is a contradiction. So, $c_{16}=53$.
  We have $c_{18}=41$. $$ \begin{array}{c|c|c|c|c} 31 & C1 & C3 & 23 & 29\\\hline & \times & D3 & A3 & A9\\\hline & \times & D9 & \times & 59 \\\hline & & & \times & 53 \\\hline & 41 & \circ 1 & B1 & B3\end{array} $$So, $A=1,7,8$ (because $c_8=A3,c_9=A9,c_4=23,c_{12}=59$), $B=1,7$ (because $c_{20}=B1,c_{21}=B3,c_{18}=41$), $C=1,7$ (because $c_2=C1,c_3=C3,c_{18}=41$), $D=1,7,8$ (because $c_7=D3,c_{11}=D9,c_4=23,c_{12}=59$). We have $\{B,C\}=\{1,7\}$, so $A=8$. However, this is impossible since there is no such $D$.)

• $c_5=A3,c_7=C9,c_{10}=97,c_6=37,c_{16}=53$.
  (From fact 2, we have $c_{10}=97$ and $c_{16}=53$.)

• $c_{20}=13$.
  (Suppose that $c_{20}=B1$. Then, we have $c_{19}=E1,c_{18}=41$.
  If $D\not=1$, then it follows from fact 2 that $c_{15}=D1$. Then, $c_1,c_2,c_{15},c_{18},c_{19},c_{20}$ are of the form $\circ 1$. From fact 3, this is impossible. So, $D=1$.
  We have $$ \begin{array}{c|c|c|c|c} 31 & C1 & C3 & 23 & A3\\\hline 37 & \times & C9 & 29 & A9\\\hline 97 & \times & 19 & \times & 59 \\\hline & & & \times & 53 \\\hline & 41 & E1 & B1 & B3\end{array} $$ So, $C=7,A=8,B=1,E=6$, but there is no prime $p$ such that $c_{15}=p$.)

• $c_{19}=11$.
  (We have $c_{19}=1E$ and $c_{18}=4E$.
  Suppose that $E=7$. Then, $c_6,c_{10},c_{13},c_{14},c_{15},c_{17},c_{18},c_{19}$ are of the form $\circ 7$. From fact 4, this is impossible.)

• $c_{18}=41,C=7,A=8,B=4,D=1,c_{14}=47$.
  (Suppose that $c_{17}=47$. Then, $c_1,c_2,c_{14},c_{15},c_{18},c_{19}$ are of the form $\circ 1$. From fact 3, this is impossible.)

• $c_{15}=17,c_{13}=67,c_{17}=61$.

Therefore, the only solution is

$$ \begin{array}{c|c|c|c|c} 31 & 71 & 73 & 23 & 83\\\hline 37 & & 79 & 29 & 89\\\hline 97 & & 19 & & 59 \\\hline 67 & 47 & 17 & & 53 \\\hline 61 & 41 & 11 & 13 & 43\end{array} $$