CombinatoricsDifficulty 7.1National Olympiad, round 2Prove itUnited States
Problem:
All the chairs in a classroom are arranged in a square n×n array (in other words, n columns and n 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 n is even, and cannot be done if n is odd.
Solution
Solution:
If n is even, there are many ways to do this. One is simply to exchange adjacent students in each row: the student in an odd-numbered chair k exchanges places with the student in chair k+1. In other words, exchange students in chairs 1 and 2, those in chairs 3 and 4, and so on. Since there are an even number of students in each row, every student in every row will move and the teacher's two conditions can be satisfied.
If n is odd, imagine that the chairs are colored alternately black and white as on a chessboard with a black chair in one corner (and hence all four corner chairs are black). It is easy to see that (n2+1)/2 of the chairs are colored black and (n2−1)/2 are white, so there is one more black than white chair. Any valid rearrangement must move each student to a chair of the opposite color. The conditions cannot be satisfied since there is one more black chair than white chair, so some student seated in a black chair will have nowhere to go.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.