Suppose a classroom has 25 students seated in desks in a square 5 × 5 array.

722 Views Asked by At

The teacher wants to alter the seating by having every student move to an adjacent seat (just ahead, just behind, on the left, or on the right). Show that such a move is impossible.

I just want to make sure that I understand what this question is asking.

This question is (in subtle terms) asking you to construct a hamilton circuit and then asking you to show that it's impossible correct?

1

There are 1 best solutions below

1
On

Paint the desks black and white as if it was a chessboard. There will be $13$ black and $12$ white desks. After a move, if it existed, every student would move from a black desk to a white desk and vice versa. This cannot happen as it would suddenly require $13$ white desks.