あみだくじ問題の解答例を示します。
問題の解
数学的帰納法で示す。
(A)横線が1本の場合、明らか。
(B)横線がk本以下の場合、題意が満たされるとする。
k+1本の横線があるとき、適当に1本取り出し、2つの部分あみだくじ
(XとY)に分割する。
部分あみだくじXでは横線がk本以下なので仮定から題意が満たされる。
赤い横線がある部分でも題意が満たされる。
部分あみだくじYでも横線がk本以下なので仮定から題意が満たされる。
結局、k+1本の横線ある場合も題意が満たされる。
(A),(B)より、題意が成り立つことが示された。