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.