A $3 \times 3$ grid $G$ is filled with every number from the set $\{2,3,5,6,7,11,14,15,30\}$. Now a new $3 \times 3$ grid $H$ is formed, such that $H_{ij}$ is the number of neighbors of $G_{ij}$ that have a common factor with $G_{ij}$ (greater than $1$). Two cells are neighbors if they are adjacent horizontally, vertically or diagonally. Given the grid $H$ shown below, can you derive the contents of grid $G$?
There is one solution for $G$, which is as follows
3 5 30 6 2 14 7 11 15
Notice first that
Sharing a common factor is a symmetric relationship so let us join two adjacent cells by a red line if and only if they share a common factor. Then, we quickly get the following
Now
The number in the middle is adjacent to all other numbers so it must be an element of the group which shares a common factor with exactly three other elements in the group. This only happens for 2 (with 6,14 and 30) and 3 (with 6, 15 and 30) so the middle number is either 2 or 3. The three numbers which share a factor with the middle number must be in the top right, right middle and left middle cells, as shown in the diagram above.
First, suppose the middle cell contains the number 3. The number above it must share a common factor with exactly one of 6,15 and 30. However, none of the remaining numbers satisfy this. Hence the middle cell must be 2.
Now, notice the number in the cell above the centre must share a common factor with exactly one of 6,14 and 30. Hence it must be either 5 (case (i)) or 7 (case (ii)).
(i) If the number in the top middle is 5 then 30 must be to its right. The middle row thus contains 2, 6 and 14 in some order. The bottom middle must be a number which contains no factor in common with 2,6 or 14 (which must be 11, since 5 has already been used). One of the bottom corners must share no common factor with 2,6 or 11 (which must be 7) and the other bottom corner shares no common factor with 2,14 or 11 (which can either be 3 or 15). Then the top left corner must also be either 3 or 15, but cannot be 15 since this shares a common factor with 5 and, from the diagram, they are not joined by a red line. Hence the top left corner must be 3 and this forces the middle left to be 6 giving us the following solution.
3 5 30 6 2 14 7 11 15
Suppose instead
(ii) The top middle is 7. Then, the top right is 14 and the middle row must contain 2,6 and 30 in some order. Again the bottom middle shares no common factor with 2,6 or 30 (so must be 11). One of the bottom corners shares no common factor with 2,11 or 30. However, all of the remaining numbers share a common factor with 30 so this will not work.
