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.

problem of swapping rows and columns

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.


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Swapping Rows and Columns


Solution

|Up| |Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 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.

problem of swapping rows and columns

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:

  1. one can lift any numbers of bags and shake them rigorously, or
  2. one can swap any two labels.

Clearly, the contents of the bags remain invariant under both operations.

Related material
Read more...

  • Chessboard
  • Solitaire on a Circle
  • Peg Solitaire
  • Ford's touching circles
  • Euclid's Game
  • Sam Loyd's fifteen
  • Escape of the Clones
  • |Up| |Contact| |Front page| |Contents| |Algebra| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62331032

    Search by google: