パズル万華鏡

面白いパズルの紹介と解説をします。

あみだくじ問題の解

 あみだくじ問題の解答例を示します。

 

問題の解

 数学的帰納法で示す。

(A)横線が1本の場合、明らか。

(B)横線がk本以下の場合、題意が満たされるとする。
   k+1本の横線があるとき、適当に1本取り出し、2つの部分あみだくじ
  (XとY)に分割する。

f:id:isemba:20170816144225j:plain

   部分あみだくじXでは横線がk本以下なので仮定から題意が満たされる。
   赤い横線がある部分でも題意が満たされる。
   部分あみだくじYでも横線がk本以下なので仮定から題意が満たされる。
   結局、k+1本の横線ある場合も題意が満たされる。

(A),(B)より、題意が成り立つことが示された。

f:id:isemba:20170816144254j:plain