あみだくじ。

質問

大学１年です。次のパズル問題を考えていたのですが・・・。

【問題】ｎ本の縦線を引き、左から順番に１，２、・・・ｎと番号をつける。さらにゴール地点にも左から順番に１～ｎと番号つけたとき、適当なｍ本の横棒を引くことで、全ての番号についてスタート地点とゴール地点を一致させることができるが、このときｍが偶数であることを示せ。

　直感的に明らかですが、背後に線形代数の置換が・・・？線形代数を少し学んでいるので、いくらか背景にも突っ込んで回答いただければ幸いです。

回答No.3

Mell-Lily

この問題は、群論の

　『任意の置換は、互換の積として表すことができる』
　『任意の置換を、互換の積として表したとき、用いた互換の個数の偶奇は、一定である』

などの定理と関係があります。

回答No.2

keyguy

１≦ｉ＜ｊ≦ｎであるｉ番とｊ番を入れ替えるには
ｉ番目とｊ番目の間に他の線を飛び越えて線を引けば良い。
このような横線の引き方はあみだくじを一般化したものであるがこれで証明できればその特殊な場合のあみだくじでも証明できたことになる。
上から順に横線に対応する行列を
ｘ［１］，ｘ［２］，ｘ［３］，・・・，ｘ［ｍ］
とすると最後に元に戻るから
Ｉ＝ｘ［ｍ］・ｘ［ｍ－１］・・・ｘ［１］が成立する。
所で｜ｘ［ｋ］｜＝－１だから両辺の行列式を求めて
１＝（－１）＾ｍが成立する。
よってｍは偶数である。

大学理系前期を終了しているのであれば線形代数は終わっていますね。

回答No.1

waseda2003

横棒を（１本）引くことは，互換を行なったことになります。
例えば，１番の縦線と２番の縦線に横棒を引くと，１番の道筋が２番に，２番の道筋が１番に入れ替わることになるからです。

したがって，上の問題は
「ｍ個の互換の合成が恒等置換であるとき，ｍが偶数であることを示せ」
と言い換えられることになり，恒等置換は偶置換なので明らかです。

むしろ，「適当なｍ本（ｍ≧1）の横棒を引くことで、全ての番号についてスタート地点とゴール地点を一致させることができるか？」とした方が，問題としては面白いと思います。