こんにちは。福田泰裕です。
みなさんは、あみだくじをやったことがありますか？
クラスの委員決めや席替えのときにやったことがあると思います。
そのあみだくじをやっていて、
あみだくじは、なんで行き先がダブらないんだろう…？
と考えたことはありませんか？
今回は、あみだくじの行き先が重複しないことを証明していきます。
最後まで読んでいただけると嬉しいです。
目次
あみだくじの行き先が重複しないことの証明
あみだくじの行き先が重複しないことを証明していきます。
問題をハッキリさせる
まず、この問題をハッキリさせておきましょう。
縦棒が \(n\) 本のあみだくじがあり、上段には左から順に \(x_1,x_2,…,x_n\) 、下段には左から順に \(y_1,y_2,…,y_n\) が書かれている。（ただし、\(n \geq 2\) ）
ここから \(m\) 本の横棒を引いて、あみだくじを完成させる。 （ただし、\(m \geq 0\) ）
このとき、\(0\) 以上のすべての整数 \(m\) について、対応が重複しないことを示せ。
図を描くと、こんなイメージです。
数学的帰納法を用いて証明する
この証明には、数学的帰納法を使います。
( i ) \(m=0\) のとき、
\(x_1\) と \(y_1\) 、\(x_2\) と \(y_2\) 、\(x_3\) と \(y_3\) 、…… \(x_n\) と\(y_n\) が対応しているので、重複しない。
よって、\(m=0\) のとき成り立つ。
\(m=0\) のとき、横棒がありません。
すべての項目がストレートに対応しているので、重複するわけがありませんね。
( ii ) \(m=k\) のとき、重複していないと仮定する。
\(m=k+1\) のとき、
\(k+1\) 本目の横棒に対応する2つが入れ替わるだけなので、重複しない。
よって、\(m=k+1\) のときも成り立つ。
( i ) ( ii ) から、\(0\) 以上のすべての整数 \(m\) について重複しないので、成り立つ。
\(m=k\) のとき、重複していないと仮定すると…
これで重複していない状態です。
ここに \(m+1\) 本目の横棒を加えると…
その \(m+1\) 本目に対応する2つが入れ替わるだけで重複はなく、全体にも影響はありません。
0本で重複しないので、1本でも重複しない。
1本で重複しないので、2本でも重複しない。
2本で重複しないので、3本でも重複しない。
‥‥‥
と繰り返していけば、横棒を何本引いても重複しないことになります。
これで証明は終わりです。
まとめ：あみだくじは横棒を1本引いたら2つが入れ替わるだけ
いかがでしたでしょうか。
今回は、数学的帰納法を用いて証明しました。
しかしこれだと小学生や中学生は理解できないでしょう。
誰でも理解できるように簡単に言うと、
あみだくじは横棒を1本引くと、その対応する2つの項目が入れ替わるだけ
ということです。
入れ替わるだけだから、重複するはずがありません。
それを難しく書くと、数学的帰納法になるのです。
あみだくじは学校では公平性があると思われているためによく用いられます。
しかし、実はあみだくじは思い通りに操作する禁断の方法があります。
その禁断の方法はこちらの記事をご覧ください👇
最後まで読んでいただき、ありがとうございました！
質問やご意見、ご感想などがあればコメント欄にお願いします
コメント