Is it possible to insert numbers $1, \ldots, 16$ into a table $4 \times 4$ (each cell should have a different number) so that every two adjacent cells (i.e. cells sharing a common side) have numbers $a$ and $b$ satisfying (a) $|a-b| \geq 6$ (b) $|a-b| \geq 7$
Problem
Source:
Tags: combinatorics
ThE-dArK-lOrD
23.07.2016 23:06
(a) Yes, it's possible: $$ \begin{matrix} 9&1&10&2\\ 3&11&4&12\\ 13&5&14&6\\ 7&15&8&16 \end{matrix}$$
ThE-dArK-lOrD
23.07.2016 23:17
(b) No. Note that we have $7$ must adjacent to a number from $\{ 14,15,16\}$. $8$ must adjacent to number from $\{ 1,15,16\}$. $9$ must adjacent to number from $\{ 1,2,16\}$. $10$ must adjacent to number from $\{ 1,2,3\}$. This means $7,8,9,10$ must fill in four corners of the table But the set of numbers that may adjacent to that four numbers is $\{ 1,2,3,14,15,16\}$ contains only six numbers. This is contradiction since there are $8$ numbers adjacent to one of four corners of table.
Keith50
03.08.2021 07:50
ThE-dArK-lOrD wrote: (b) This means $7,8,9,10$ must fill in four corners of the table Sorry for bumping this, but why must the four numbers fill in the four corners of the table? They can be on the squares which are adjacent to three other squares.