真面目なブログ記事です。
↑これ訂正なんですけど、私真面目なことしか書いた覚えがなかったです。
最近Queen問題というものを知りました。
これはチェスの盤に8個のクイーンを重ならないように置けるか?という問題です。
クイーンは任意の縦横斜め方向に好きなだけ動ける、というやつです。将棋で言うなら角と飛車がくっついたような感じ。
重ならないように、とはクイーンの行動出来る軌道上に他のクイーンが存在しない、という状態です。
説明が超下手です。wikipediaのエイト・クイーン問題に画像が載っているのでそっち見てください。ごめんなさい。
で、チェス盤の大きさは8×8なのですが、これを一般のn×nにしてみたn-Queen問題というのがあります。
で、一般にnが大きくなるほど解の数が増えて組み合わせ爆発が起こるらしく、解の数を知りたい、というのが主な問題で、これはどちらかというとプログラムとかアルゴリズムの問題だそうです。
しかし、私はプログラムが書けないしアルゴリズムも深さ優先探索と幅優先探索しか知りません。
でもまぁ無限組み合わせ論オタクなのでω-Queen問題を考えてみました。
要は盤面がの時を考えよう、という話です。
で、解の存在が(ZFC上で)示せた(と思う)のでちょっと紹介してみようと。
話の流れとしてはω-Queenの定義→証明に使う補題→存在性証明という感じです。
1.ω-Queen問題の解
そもそも何が解なんですか、という話で。
だいたいω個の重ならないクイーンなんていくらでも置けるわけです。各nに対して十分大きいa_nを取ってとすれば良いので。
でもなんかこれだとスカスカです。というのもn-Queen問題の解は任意の行に対してただ1つのクイーンが置かれていて、さらに任意の列に対しても同様です。
まぁn個重ならないように置けばそりゃそうなんですけど、
なので、「任意の行に対して1つのクイーン、任意の列に対して1つのクイーンがあって、さらに斜めで重ならないような配置」を解だと思うことにします。
で、がω-Queen問題の解であるとは、
まず
を満たしていて、
かつ斜めで重ならない。
即ち任意のに対して
ならば
となります。
あまりにもアレなので最初の条件を書きなおすと任意のに対して唯1つのが存在してなのでは関数です。
よってこれはでを満たす全単射そのものです。
このような全単射をω-Queen問題の解と定義することにします。
2.半順序の稠密部分集合とRasiowa-Sikorskiの補題
定義が終わったので次は存在を示したいんですけど、それに使う補題の紹介をします。
最初、具体的に定義しようとするもなんか色々と勘違いしていて「ぶっちゃけこんな関数ねーだろ!!!!でも強制法でくっつけられるんじゃね?」とやってみたらこの証明が出来ましたという感じなので、強制法を知ってる人はあーわかるわかる程度に見てください。
定理で使うRasiowa-Sikorskiの補題は次の主張を言います:
定理(Rasiowa-Sikorski)
任意のc.c.c.を持つ半順序と稠密集合の可算族に対して-filterでなるものが存在する。
これだけだと大変にアレなので 各用語の説明です。
を半順序とします。
-
が反鎖(antichain)であるとは、任意のに対してなるが存在しないことをいう。
-
がc.c.c.を持つとは、任意の反鎖が可算であることをいう。
-
が稠密集合(dense subset)であるとは、任意のに対しが存在してなることをいう。
- がfilterであるとは任意のに対してなるが存在してかつ任意のに対してなることをいう。
filterは上方向について閉じた有向集合って言った方がわかりやすいかもしれません。まぁ同じなので良いです。
3.解の存在の証明
ここで示すのは次です:
を満たす全単射が存在する。
証明:
またに対してとするとは半順序です。
は有限半関数全体の集合に含まれます。また、有限半関数全体の集合は可算なのでもちろんc.c.c.を持ちます。
また,とするとこれは稠密集合になります。これは有限性を使うと示せます。
は可算な稠密集合の族なのでRasiowa-Sikorskiの補題より全部と交わるfilterが取れます。
ここで、に対しでなるものが存在します。
であることに気をつけるとが関数であることが示せます。
関数でないとするとに対してなるが存在します。即ちは関数ではないことがわかります。
一方での元は全て関数なので矛盾です。
さらにはなる関数になります。
というのも、任意のに対してが存在するのでなのでです。
これは全射になります。
これもまたが存在することよりあるが存在してであることより言えます。
さらにの定義より単射です。
というのも、任意のを取るとが存在してなのでです。
よって、となり単射性が示せました。
も全く同様にして示せます。
よって条件を満たす全単射が見つかりました。□
結論としての点にクイーンを配置するとどのクイーンも縦横斜め移動し放題、任意の行にも任意の列にもクイーンが1ついてハッピーハッピーです。
で、こういう定式化をすると解が見つかるよ、という話でやっぱり気になるのは非可算の場合なんですけど、その場合どう定義したら良いかわからないですね。
なんかcoloringとかの性質で特徴付けできそうな気はするんですけどね。
まぁωの場合がわかったと思うので取り敢えず良いです。どこか間違えてたら教えてください。