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

  • 1
    $\begingroup$ I really don't think we should be telling you how to do this. I will give the following small hint: you don't need to do much more than you already have in order to find a solution. $\endgroup$ – Gareth McCaughan Oct 26 '17 at 12:58
  • $\begingroup$ Well ... actually, the solution you'll get by following the shortest path from where you've got to so far won't explicitly use the pigeonhole principle. But it might give you some useful ideas for how to do it with the PHP. $\endgroup$ – Gareth McCaughan Oct 26 '17 at 13:01
  • 2
    $\begingroup$ Hint: color the grid like a checkerboard! How do the colors relate to the movements of the people? $\endgroup$ – Mike Earnest Oct 26 '17 at 14:05


No, it's not possible. imagine the 11x11 grid as a large b/w checkered board. when you move, you move from one colour to its opposite. In order for it to be possible for every single occupant to move to an adjacent room, then, there must be a black square for every white square. But 11x11 is an odd number, meaning that there is one square which does not have a match.

| improve this answer | |

No, it's not possible. To mutually exchange places there must be an even amount of moves. Since each person can move only once, with an uneven amount of people there will always be an odd amount of moves. In which case, the last move will never have a counter-move. enter image description here

| improve this answer | |
  • $\begingroup$ I do not think it is appropriate to post complete solutions to homework questions. $\endgroup$ – Gareth McCaughan Oct 26 '17 at 13:40
  • $\begingroup$ (Though this solution has the advantage, from this perspective, of not actually using the pigeonhole principle as the student was required to do.) $\endgroup$ – Gareth McCaughan Oct 26 '17 at 13:40
  • $\begingroup$ ... Also, your answer appears to assume that the only option is to have lots of pairs swapping places. But that is not the only possibility; consider e.g. a 2x2 square where each person moves one place clockwise. $\endgroup$ – Gareth McCaughan Oct 26 '17 at 13:43
  • $\begingroup$ @GarethMcCaughan No, it's not my assumption at all. Since the OP was so strongly focused on loops, I have intended to show that in the simplest case there is no loop. The theory of "loops" is not sufficient to account for all cases... $\endgroup$ – mechanicious Oct 26 '17 at 13:48
  • $\begingroup$ You can account for all cases in terms of loops; see e.g. JonMark Perry's answer. $\endgroup$ – Gareth McCaughan Oct 26 '17 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.