「夫子憮然曰、鳥獣不可與同羣。吾非斯人之徒與、而誰與。
「論語」微子、第十八、六

2012/06/05

行列マジック(解答)

昨日の 「行列マジック」 パズルの解答。
数学には「よくよく考えてみると当たり前なんだけれども、やっぱり不思議」 ということがあるもので、これはその典型例。つまり明らかだけれど、トリヴィアルではない。 2 行 2 列から試すのが筋で、しばらくすると(多分、4 x 4 あたりで)悟りが開けるのだが、 一般的な証明にチャレンジしてみよう。しかも、 数学記号を使わないと却って分かり難いところを、あえて、普通の言葉で説明してみる。 よーく考えると、「アーハー!」体験できること間違いなし。

すでに各行の中では大きい順に並び換え終わったとしよう。 どれでもいいのだが、一つの行について考える。 3 番目の行としておこうか。 さらにその行のどこでもいいから、二つの場所に注目する。 5 番目と 8 番目としておこう(5 番目の数の方が大きい)。 ここで、第 5 列、8 列それぞれの中で、大きい順に並び換えたあとでも、 この二箇所にある数の大小関係が変わらないことを示せばよい。 列の中で並び換えると、この二つの場所には各列で 3 番目に大きい数が入る。 列で並び変える前は、5 列目の数それぞれは同じ行の 8 列目の数より大きかった。 すると、第 8 列の数の中で、3 行目 5 番目の数 X より大きい可能性があるのは、高々 3 - 1 = 2 つしかない。 なぜなら、他の数は全て、X より小さいか(列で並び換える前に X と同じ行にあった)、 X より小さい数より小さい(X より小さい数と同じ行にあった)。 一方、現在 8 列目 3 行目にある数は 8 列目の中で大きさで 3 番目なのだから、 X より小さい。証明終わり。

説明するとややこしいが、分かってしまうと、どうにも明らかである。でも不思議。 もちろん、この性質は正方行列に限らず、 全く一般のどんなサイズの行列でも、どんな成分でも(順序づけ可能なら)、成り立つ。 衝撃的な性質の割にあまり知られていないが、古典的な定理である。 D.Knuth の "The Art of Programming" によれば、「Boerner の定理」らしい。