Consider a $$2 \times 3$$ rectangle made of $$6$$ unit squares. In how many ways can we fill up the six cells using the numbers $$1, 2, 3, 4, 5, 6,$$ one in each cell, such that any two numbers in adjacent cells (that is, in cells that share a common side) are coprime to each other?

Label the rectangle

$$ \begin{array}{ccc} A & B & C\\ D & E & F \end{array} $$

The seven adjacencies are
$$A\!-\!B,\;B\!-\!C,\;D\!-\!E,\;E\!-\!F,\;A\!-\!D,\;B\!-\!E,\;C\!-\!F.$$

Coprimality fails only for the pairs
• any two even numbers ( $$2,4,6$$ ) (gcd$$\ge2$$ )
• the pair $$3$$ and $$6$$ (gcd$$=3$$ ).

Therefore

1. No two even numbers may be adjacent.
2. The numbers $$3$$ and $$6$$ may not be adjacent.

Step 1 : choose the three cells for the even numbers

The grid is bipartite: colour the six cells black (A,C,E) and white (B,D,F). Edges exist only between opposite colours, so a set of cells with no edges inside it must consist wholly of one colour. Hence the only independent triples are

$$\{A,C,E\}\quad\text{and}\quad\{B,D,F\}.$$

Thus there are exactly $$2$$ ways to place the three even numbers $$2,4,6$$ so that they are pairwise non-adjacent.

Step 2 : locate the number 6

Case I Evens on the black cells $$\{A,C,E\}$$
• If $$6$$ is put at $$A$$, its neighbours are $$B,D$$, so $$3$$ must avoid $$B,D$$ and must occupy $$F$$.
• If $$6$$ is put at $$C$$, its neighbours are $$B,F$$, so $$3$$ must occupy $$D$$.
• If $$6$$ is put at $$E$$, its neighbours are $$B,D,F$$; then $$3$$ would be adjacent to $$6$$ wherever it is placed—impossible.
Hence $$6$$ can be placed in $$2$$ of these $$3$$ cells.

Case II Evens on the white cells $$\{B,D,F\}$$ (the argument is symmetric)
• $$6$$ cannot be at $$B$$ (adjacent to $$A,C,E$$).
• $$6$$ may be at $$D$$ (forces $$3$$ to $$C$$) or at $$F$$ (forces $$3$$ to $$A$$).
Again $$6$$ has $$2$$ admissible positions.

Step 3 : count the fillings for each admissible position of 6

After fixing the cell containing $$6$$ and the forced position of $$3$$ :

• The remaining two even numbers $$2,4$$ may be arranged in the two remaining even cells in $$2!$$ ways.
• The remaining two odd numbers $$1,5$$ may be arranged in the two remaining odd cells in $$2!$$ ways.

Thus each admissible placement of $$6$$ yields $$2!\times 2! = 4$$ fillings.

Step 4 : total count

Each colour-pattern (black or white for the evens) allows $$2$$ positions for $$6$$, and each such position gives $$4$$ fillings:

$$2\;(\text{colour patterns}) \times 2\;(\text{positions of }6) \times 4 = 16.$$

Hence the required number of ways is $$16$$.

Answer: 16