Nine people want to greet everyone else. They can change places, but there is a rule about whom they may greet.
The Greeting Grid
Riddle statement
Nine people stand in the nine cells of a 3 × 3 grid, one person per cell. Each person greets everyone in a cell that shares a side with theirs. Diagonal neighbours do not count.
They then rearrange themselves however they like and repeat the greetings. They do this once more, for a third and final round.
Can they arrange the three rounds so that every pair of people has greeted each other at least once?
Show solution
Solution
No: at least one pair will never greet each other.
Colour the grid black and white like a checkerboard. Cells that share a side always have different colours.
Record a three-letter history for each person: B or W according to the colour of their cell in each round. There are only 2³ = 8 possible histories, but there are nine people. Two people must have the same history.
Those two occupy cells of the same colour in all three rounds. They can never share a side, so they never greet each other.
Counting alone is deceptive here. Nine people form 9 × 8 ÷ 2 = 36 pairs, and the grid has 12 neighbouring pairs per round. Three rounds provide exactly 36 greetings, but there is no way to distribute them among all 36 pairs.
The useful record is not each person’s exact route through the grid: it is just their sequence of colours. That smaller record makes an unavoidable repetition visible.