1

Admittedly this is a problem I encountered from school but I cannot think of a proper proof solution. I thought about the logic that in order to cover all squares, there must be closed loops of movements. So in the easiest case, where there are only 2 squares, person in square A goes to square B and person in square B goes to square A. This means that for grids with even number rooms, it is possible. But how can I prove that for odd number rooms, there is no way to create closed loops of movements to cover all squares.

The question comes with the constraint that I have to use Pigeonhole Principle to solve but I am open to ideas.

enter image description here

davidchoo12
  • 123

1 Answers1

3

Hints:

  • Colour the rooms alternately black and white like a chessboard starting with black in a corner

  • How many people are in black rooms and how many in white rooms?

  • They each move to an adjacent room, so after the move how many people are in black rooms and how many in white rooms?

  • Is this possibly consistent with each room having one person after the move?

Henry
  • 157,058