7
$\begingroup$

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$?

top row is 1, 1, 3; middle row is 2, 3, 2; bottom row is 0, 0, 0

$\endgroup$
4
  • $\begingroup$ Is this puzzle too hard? I can make an easier version... $\endgroup$ – Dmitry Kamenetsky Apr 9 at 9:42
  • 2
    $\begingroup$ No, not too hard. $\endgroup$ – hexomino Apr 9 at 9:43
  • $\begingroup$ ok good. Waiting for solutions then $\endgroup$ – Dmitry Kamenetsky Apr 9 at 9:43
  • $\begingroup$ About the puzzle creation. I wrote a program that goes through all 9! permutations of the numbers and makes sure that there is just a single G for the current H. It took me some time to find a suitable set of starting values, because many others that I tried had multiple G for every combination. I almost gave up on the puzzle, before stumbling upon this set of numbers. $\endgroup$ – Dmitry Kamenetsky Apr 10 at 8:50
6
$\begingroup$

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 enter image description here

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.

$\endgroup$
2
  • 1
    $\begingroup$ We took the same steps and reasoning! $\endgroup$ – justhalf Apr 9 at 10:00
  • 1
    $\begingroup$ @justhalf Great minds! $\endgroup$ – hexomino Apr 9 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.