2006 BAMO p1 rearranging n^2 chairs in a nxn square classroom
Source:
August 27, 2019
combinatorial geometrycombinatorics
Problem Statement
All the chairs in a classroom are arranged in a square array (in other words, columns and rows), and every chair is occupied by a student. The teacher decides to rearrange the students according to the following two rules:
(a) Every student must move to a new chair.
(b) A student can only move to an adjacent chair in the same row or to an adjacent chair in the same
column. In other words, each student can move only one chair horizontally or vertically.
(Note that the rules above allow two students in adjacent chairs to exchange places.)
Show that this procedure can be done if is even, and cannot be done if is odd.