3. Andrew wants to write the letters of the word KANGAROO in the cells of a $2 \times 4$ grid such that each cell contains exactly one letter. He can write the first letter in any cell he chooses but each subsequent letter can only be written in a cell with at least one common vertex with the cell in which the previous letter was written. Which of the following arrangements of letters could he not produce in this way?
Solution
D

To produce the arrangement of diagram D, Andrew would first need to write the letters K, A, N and $\mathrm{G}$ in the top four cells as shown. He would then need to write $\mathrm{A}$ in a vacant cell next to the G. Therefore he could not write $\mathrm{O}$ and $\mathrm{O}$ in the third row. Hence arrangement $\mathrm{D}$ could not be produced in the way described.
(It is left as an exercise for readers to show that all the other arrangements can be produced in the way described.)