数学U　数列

数学的帰納法　あみだくじ

あみだくじ
問題
あみだくじの上部（入り口）にアルファベットをでたらめに並べる． 下部（出口）にＡＢＣ順に並ぶように，横線（橋）を書き入れなさい． 
         Ｍ　Ａ　Ｔ　Ｈ　Ｅ　Ｍ　Ａ　Ｔ　Ｉ　Ｃ　Ｓ
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
解答は無数にあるが， 入り口のアルファベットがどんな風に並んでいても， 同様にすれば必ずできるという方法を考えよ．

解答１
アルファベットが１１個もあるから難しい． Ｍ，ＭＡ，ＭＡＴ，ＭＡＴＨ，… と１つずつ増やして考えていく． 
         Ｍ　Ａ　Ｔ　Ｈ　Ｅ　Ｍ　Ａ　Ｔ　Ｉ　Ｃ　Ｓ
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ｍ　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┣━┫　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ｍ　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ｍ　Ｔ　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         ┃　┣━┫　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ｈ　Ｍ　Ｔ　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┣━┫　┃　┃　┃　┃　┃　┃
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         ┃　┣━┫　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ｅ　Ｈ　Ｍ　Ｔ　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         Ａ　Ｅ　Ｈ　Ｍ　Ｍ　Ｔ　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┣━┫　┃　┃　┃　┃
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         ┃　┃　┃　┣━┫　┃　┃　┃　┃　┃　┃
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         ┃　┣━┫　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｅ　Ｈ　Ｍ　Ｍ　Ｔ　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｅ　Ｈ　Ｍ　Ｍ　Ｔ　Ｔ　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┣━┫　┃　┃
         ┃　┃　┃　┃　┃　┃　┣━┫　┃　┃　┃
         ┃　┃　┃　┃　┃　┣━┫　┃　┃　┃　┃
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｔ　Ｔ　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┣━┫　┃
         ┃　┃　┃　┃　┃　┃　┃　┣━┫　┃　┃
         ┃　┃　┃　┃　┃　┃　┣━┫　┃　┃　┃
         ┃　┃　┃　┃　┃　┣━┫　┃　┃　┃　┃
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         ┃　┃　┃　┣━┫　┃　┃　┃　┃　┃　┃
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｔ　Ｔ　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┣━┫
         ┃　┃　┃　┃　┃　┃　┃　┃　┣━┫　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
解答２
アルファベットが１１個もあるから難しい． １つ減らしたい． それにはＡＢＣ順で最も遅い文字を右端に移すようにすればよい． それを繰り返す． 
         Ｍ　Ａ　Ｔ　Ｈ　Ｅ　Ｍ　Ａ　Ｔ　Ｉ　Ｃ　Ｓ
         ┃　┃　┃　┃　┃　┃　┃　┣━┫　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┣━┫　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┣━┫
         Ｍ　Ａ　Ｔ　Ｈ　Ｅ　Ｍ　Ａ　Ｉ　Ｃ　Ｓ　Ｔ
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┣━┫　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┣━┫　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┣━┫　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┣━┫　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┣━┫　┃
         Ｍ　Ａ　Ｈ　Ｅ　Ｍ　Ａ　Ｉ　Ｃ　Ｓ　Ｔ　Ｔ
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ｍ　Ａ　Ｈ　Ｅ　Ｍ　Ａ　Ｉ　Ｃ　Ｓ　Ｔ　Ｔ
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┣━┫　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┣━┫　┃　┃　┃
         Ｍ　Ａ　Ｈ　Ｅ　Ａ　Ｉ　Ｃ　Ｍ　Ｓ　Ｔ　Ｔ
         ┣━┫　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┣━┫　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┣━┫　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┣━┫　┃　┃　┃　┃
         Ａ　Ｈ　Ｅ　Ａ　Ｉ　Ｃ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
         ┃　┃　┃　┃　┣━┫　┃　┃　┃　┃　┃
         Ａ　Ｈ　Ｅ　Ａ　Ｃ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
         ┃　┣━┫　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┣━┫　┃　┃　┃　┃　┃　┃
         Ａ　Ｅ　Ａ　Ｃ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
         ┃　┣━┫　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┣━┫　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
本題である数学的帰納法からは外れるが，あみだくじについて考察する．
橋の数
上の２つのあみだくじは共に２５本の橋が書いてある． それぞれの橋を通る２つのアルファベットを見ると， どれも橋を通る前（上）に逆順だったものが橋を通った後（下）で正順になっている． すなわち，無駄な橋がない． ゆえに，これより少ない橋の数ではＡＢＣ順にできない． 橋の最少数は，入り口のアルファベットの並びの中で逆順になっているペアの個数である．
同じアルファベットが含まれている場合は， そのペアを交換する無駄な橋を何本でも追加することができる．
同じアルファベットが含まれていない場合， 最少数より多い橋が書いてあるとすると，正順のペアを逆順にする橋があり，それをまた戻す橋がある． したがって，橋の数は最少数より偶数本多い（最少数と奇偶が一致する）．

段の数
上の２つのあみだくじは，同じ段に橋を２本以上書いてないので，縦に長くなっている． 同じ段に橋を２本以上書くことによって段数を減らすことができる． 両者を書き直してみると，同じ形にできることがわかる．
しかも，それは完全に逆順に並びかえるあみだくじの一部の橋を除去してできる形である． 
         Ｍ　Ａ　Ｔ　Ｈ　Ｅ　Ｍ　Ａ　Ｔ　Ｉ　Ｃ　Ｓ
         ┠　┨　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┠　┨　┃　┃　┃　┃　┃　┃　┃　┃
         ┠　┨　┠　┨　┃　┃　┃　┃　┃　┃　┃
         ┃　┠　┨　┠　┨　┃　┃　┃　┃　┃　┃
         ┠　┨　┣━┫　┠　┨　┃　┃　┃　┃　┃
         ┃　┠　┨　┣━┫　┠　┨　┃　┃　┃　┃
         ┣━┫　┠　┨　┣━┫　┠　┨　┃　┃　┃
         ┃　┣━┫　┠　┨　┣━┫　┣━┫　┃　┃
         ┠　┨　┣━┫　┣━┫　┣━┫　┣━┫　┃
         ┃　┠　┨　┣━┫　┣━┫　┣━┫　┣━┫
         ┠　┨　┠　┨　┣━┫　┣━┫　┣━┫　┃
         ┃　┣━┫　┠　┨　┣━┫　┠　┨　┃　┃
         ┠　┨　┣━┫　┣━┫　┠　┨　┃　┃　┃
         ┃　┣━┫　┣━┫　┠　┨　┃　┃　┃　┃
         ┠　┨　┣━┫　┠　┨　┃　┃　┃　┃　┃
         ┃　┠　┨　┠　┨　┃　┃　┃　┃　┃　┃
         ┠　┨　┠　┨　┃　┃　┃　┃　┃　┃　┃
         ┃　┠　┨　┃　┃　┃　┃　┃　┃　┃　┃
         ┠　┨　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
このことから，完全に逆順に並びかえるあみだくじで段数が最少のものを元にすると， 段数の少ないあみだくじが書けると考えられる． 実際，次のあみだくじが得られる． 
         Ｍ　Ａ　Ｔ　Ｈ　Ｅ　Ｍ　Ａ　Ｔ　Ｉ　Ｃ　Ｓ
         ┣━┫　┣━┫　┠　┨　┠　┨　┣━┫　┃
         ┃　┣━┫　┣━┫　┣━┫　┣━┫　┠　┨
         ┠　┨　┣━┫　┣━┫　┣━┫　┣━┫　┃
         ┃　┣━┫　┣━┫　┣━┫　┣━┫　┣━┫
         ┠　┨　┣━┫　┣━┫　┣━┫　┠　┨　┃
         ┃　┣━┫　┣━┫　┣━┫　┣━┫　┠　┨
         ┠　┨　┣━┫　┠　┨　┠　┨　┣━┫　┃
         ┃　┠　┨　┠　┨　┠　┨　┠　┨　┠　┨
         ┠　┨　┠　┨　┠　┨　┠　┨　┠　┨　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
跨線橋（隣同士でない離れた線を結ぶ橋）を許すと橋の数を少なくできる．
たとえば，出口の左から順に揃えるようにする．
下の例は，同じアルファベットの順序を保つようにしたものである． 
         Ｍ　Ａ　Ｔ　Ｈ　Ｅ　Ｍ　Ａ　Ｔ　Ｉ　Ｃ　Ｓ
         ┣━┫　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┣━┃━┃━┃━┃━┫　┃　┃　┃　┃
         ┃　┃　┣━┃━┃━┃━┃━┃━┃━┫　┃
         ┃　┃　┃　┣━┫　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┣━┃━┃━┫　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┣━┫　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┣━┃━┫
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         ┃　┃　┃　┃　┃　┃　┃　┃　┃　┃　┃
         Ａ　Ａ　Ｃ　Ｅ　Ｈ　Ｉ　Ｍ　Ｍ　Ｓ　Ｔ　Ｔ
ｋ本の線を跨ぐ跨線橋は(２ｋ＋１)本の普通の橋で書き換えることができるので， 普通の橋だけのあみだくじの場合と橋の数の奇偶は一致する．

スライドパズルへの応用
１〜15の番号が書いてある15枚の小さい正方形のコマを， ４×４の枠の中にでたらめに入れると空所が１つできる． 空所に隣のコマをスライドさせる操作を繰り返して， 番号順に揃えるパズルがある．
７13２９
10１５15
６　８11
12４３14
⇒
１２３４
５６７８
９101112
131415　
これは，次のあみだくじを条件付きで完成させることと同じである． 
    ７　13　２　９　15　５　１　10　６　□　８　11　14　３　４　12
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    １　２　３　４　８　７　６　５　９　10　11　12　□　15　14　13
条件
  1. 跨線橋が使えるが，全部ではない． 使えるのは，左から１本目と８本目，２本目と７本目などで， 太線と細線を結ぶ橋（の一部）だけである．
    （普通の橋はすべて使える．それは太線と細線を結ぶ．）
  2. どの橋も□と番号を交換するものでなければならない． 番号と番号を交換する橋はない．

この条件を満たすあみだくじは，次の性質をもつ．
　橋が奇数本　⇔　□が細線から太線または太線から細線に移る
　橋が偶数本　⇔　□が細線から細線または太線から太線に移る

上の例を条件のないあみだくじで完成する． 
    ７　13　２　９　15　５　１　10　６　□　８　11　14　３　４　12
    ┣━│━┃━│━┃━│━┫　│　┃　│　┃　│　┃　│　┃　│
    ┃　┝━┫　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┣━│━┃━│━┃━│━┃━│━┃━│━┃━┥　┃　│
    ┃　│　┃　┝━┃━│━┃━│━┃━│━┃━│━┃━│━┫　│
    ┃　│　┃　│　┣━│━┃━│━┃━│━┫　│　┃　│　┃　│
    ┃　│　┃　│　┃　┝━┫　│　┃　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┣━│━┫　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　┝━┫　│　┃　│　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┣━│━┃━│━┃━│━┫　│
    ┃　│　┃　│　┃　│　┃　│　┃　┝━┃━│━┃━│━┫　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┣━┥　┃　│　┃　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　┝━┃━│━┃━┥
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┣━│━┫　│
    ┃　│　┃　│　┃　│　┃　│　┃　│　┃　│　┃　┝━┃━┥
    １　２　３　４　８　７　６　５　９　10　11　12　□　15　14　13
橋の数は偶数本である． 前に述べたように，あみだくじは何通りも書くことができるが，橋の数の奇偶は一致している． したがって，これを奇数本の橋で完成することは不可能である． ゆえに，□を細線から太線に移すことはできない．
このスライドパズルはできないことがわかる．

しかし，横並びの番号順にできないときは，縦並びの番号順にできる．
７13２９
10１５15
６　８11
12４３14
⇒
13９５１
1410６２
1511７３
　12８４