はじめに
コジマです。
あみだくじってご存知ですよね。
こんなの
（イラストACさんいつもお世話になってます）
あれって出発点に対して行き先が見事に被らないですよね？
どうやっても被りません。
これを数学的に証明したいと思います。
必要な知識
大学で習う数学の以下の知識を必要とします。
大学で習うといってもそんなに難しいことはしません。
高校数学までやってきただけの人でも理解は難しくないと思います。
前準備
集合Xと集合Yを対応づけます。
その対応づけのルールを写像と言ったりするのですが、
ここでは対応づけるんだ。とだけ思っていてください。
対応づけのルールとして、
集合Xの要素1つに対して集合Yの要素1つが対応します。
特定の条件を満たす対応づけ（写像）に対して
単射、全射、全単射という言葉があるのでそれをまず紹介します。
単射
単射とは、
集合Xの各要素に対応する集合Yの要素が重複していないこと
を言います。
イメージ図は以下の通り。
このように、x_1はy_1に、x_2はy_2に、x_3はy_3に対応していて、重複していません。
このことを単射と言います。
単射の例
集合Xを1〜10までの整数の集合、集合Yを1〜20までの整数の集合とします。
対応づけルールを「YはXの要素を2倍したもの」とします。
このとき、集合Yの各偶数が重複なく対応するため、単射となります。
全射
全射とは、
集合Xと集合Yを対応づけした時、集合Yの全ての要素を含むこと
を言います。
イメージ図は以下の通り。
集合Yの要素、y_1,y_2全てを集合Xの対応づけで網羅できています。
このことを全射といいます。
全射の例
集合Xを1〜10までの整数の集合、集合Yを0、1、2とします。
対応づけルールを「YはXの要素を3で割った余り」とします。
このとき、集合Xの1、4、7、10は集合Yの1に対応するなど、重複はしますが、
集合Yの要素はもれなく集合Xの要素と対応を持っているため全射となります。
全単射
全単射とは、
全射かつ単射のことをいいます。
つまり、漏れなく1：1対応していることです。
イメージ図は以下の通り。
全単射の例
集合Xを1〜10までの整数の集合、集合Yを1〜10までの整数の集合とします。
対応づけルールを「YはXの要素を1倍(そのまま)したもの」とします。
例に手抜き感ありますがw
全単射ってこういうことかと分かりやすいかなと思います。
証明をする
あみだくじの行き先は重複することがない。
ポイント
このように言い換えることが出来る。
↓
「全単射である。」
つまり、
集合Xと集合Yは全単射である。
といえる。
方針
縦棒の本数n(n≧2の整数)、横棒の本数m(m≧0の整数)とする。
このとき、nは任意としてよい。
横棒の本数mに対して数学的帰納法を使用して証明します。
では、証明していきます。
直感的に言うと、「横棒を引いた数だけ行き先の交換が繰り返される」からそう考えると当たり前ですね。
数学的に考えるとこのように示すことができます。
余談
あみだくじは全単射であることなどを用いて、あみだくじは「群」であることを示すことができます。
群とは集合Gに対して以下の演算を可能にするものです。
- 閉じている（集合Xの演算結果は集合Y内に帰着）
- 結合法則成り立つ（(a*b)*c=a*(b*c)）
- 単位元がある(a*e=e*a=aとなるeがある)
- 逆元がある(a*b=b*a=eとなるbがある)
正確には乗法群と言います。
ここでは証明しませんが、気になる人は後述する参考URL先のpdfを見てみてください。
また、集合の要素の並び替えを考えたものを置換群と言います。
あみだくじの出発点の並び替え結果を行き先と考えれば
あみだくじは置換群ということができます。
この考えがなんとなくでも頭にあると、あみだくじの全単射が担保されるのも感覚的に分かりやすくなると思います。
さいごに
単射、全射、全単射に関しては感覚的な分かりやすさのため厳密な説明は省きました。
あみだくじを調べた時にいい感じの資料があったので
こちらを参考にしました。
あみだくじの数学
日常当たり前に感じていたことも数学だと厳密に示すことができるんだよ。
といういい一例かと思っています。
この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)を
フォローしてくれたらうれしいです！
以上、コジマでした。
