Swapping Rows and Columns
The following problem was offered at the LXI Moscow Mathematical Olympiad for grade 8 (which is likely to be equivalent to the US grade 10):
Numbers 1, 2, 3, ..., 9 are written in a 3×3 array. The only permitted operations are to swap any two rows and or any two columns. Prove that it is impossible to attain the pattern on the right starting with the pattern on the left.
The applet below helps you experiment with the problem. To select a column or a row click on the appropriate arrow. Then click on another arrow. Continue.
|Up| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
Solution
Numbers 1, 2, 3, ..., 9 are written in a 3×3 array. The only permitted operations are to swap any two rows and or any two columns. Prove that it is impossible to attain the pattern on the right starting with the pattern on the left.
Let's assign to each column an index: 1, 2, 3, and instead of swapping the columns let's swap their indices. This is just to emphasize the fact that the operation of swapping columns does not change any of the columns. Unlike the column operation, swapping rows seems to cause columns changes. The important observation is that these changes are very limited: the order of numbers in a column may change where as the numbers themselves never do. In other words, the first column that, at the beginning, contains numbers 1, 4, 7, will contain these same numbers (perhaps in a different order) after any number of the row or column swaps.
The problem, although pretty simple, serves a good introduction into the notion of set. Having the numbers arranged in an array - a regular formation - may easily mislead into thinking that the order of the elements is important. Since the order of the elements is being changed on every step, trying to track the order of the elements is confusing. However, while the swaps can change the order of the elements, the contents of any row or column remain untouched. If the rows and columns are looked at as sets rather than sequences of numbers then it is almost immediate that the swaps do not change the contents of the columns and rows. I.e., the contents of rows and columns remain invariant under all permitted operations.
With this understanding, we may formulate an apparently more general problem: their are three bags: one containing numbers 1, 4, 7, the other numbers 2, 5, 8, and the third numbers 3, 6, 9. The bags are labeled 1, 2, 3. Two operations are allowed:
- one can lift any numbers of bags and shake them rigorously, or
- one can swap any two labels.
Clearly, the contents of the bags remain invariant under both operations.
Related material
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|Up| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71536847