I found this problem in Bay area mathematical olympiad 2006.The solution hardly needs any mathematics(the way I solved), classic example of pure thought.
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.[S]
Subscribe to:
Post Comments (Atom)
3 comments:
Hmm. The transformation could involve a combination of closed loops and disjointed pairs. Because of the unit horizontal/vertical movement constraint, the former is limited to involve even number of nodes and the latter is obviously even. This means n^2, which is odd for odd n will have a loner left in the end. QED?
correct.
Not necessarily a loner will be left.
I see that simply the problem speaks about a different permutation with even number constraint.
have a look at pg 137 of http://www.openmathtext.org/lecture_notes/new_linearalgebra.pdf
Post a Comment