FC2ブログ

La.系ぶろぐ

個人的いろいろメモ。シャープペンのメモにちょっぴりゲ○ツの悪口が混じってるただのチラ裏。

4点問題の続き

あんまり進展ないのですが、前回問題だった点の数について。

まあ、点の増え方が多すぎて大変だよね~って話になるのですが、
じゃあ、これってどれくらいの勢いで増えるのでしょうか?

これって、2点から1直線を作る、2直線から1点を作る、の繰り返しになるのですが、
実は、これだけを考える場合、同じ作用として扱うことが出来ます。
要するに、既存のn点(線)から2つ選んで、線(点)を作る、って事です。
幾何学基礎論的には、結合の公理だけで考える感じですね。

ここまで単純化すると、ただの組み合わせで、初期値が4点ですから、
生成する線:C(4,2)=6
生成する点:C(6,2)=15
生成する線:C(15,2)=105
生成する点:C(105,2)=5460
……すごい数ですね、やってられんわ!って感じです。
が、しかし、これ、前回書いた数と違いますよね?

実は、何も考えずに組み合わせを取ると重複が出てきます。
というのも、例えば点A,BとC,Dから直線l,mを作って、その交点をEとした場合、
BEから作られる直線をnとして、l,nの交点をFとする、って感じに数えてしまうからです。
よく見れば解るとおり、E=Fになるわけです。

まあ、これは座標とか考える前に、結合の公理だけでも問題になる場所で、
要するに、例えば直線lは点A,B、そしてEを含むので、Eを含む直線nとの交点は既知の点になる、
と判定して排除する必要があるわけです。

そんな感じでちょっとプログラム組んで計算すると、良い感じになるか……というと、
実際は、4点から生成する線、点(の合計)を書いていくと、
6→7→9→13→33→295→37266
となっていきます。
(ちなみに、この、自分が含む点(線)を記録する処理も、点と線で対称的に扱えます)
判定は結構速いのですが(とはいえ、37266の次を計算するのはちょっと……;)
実は、これも、線が33本生成されるところから座標判定と齟齬が出ます。

なぜか、というと……実はまだ(ちょっと要素数が多くて;)追い切れていないのですが、
上の判定だとはじき切れていない、一致してしまう点や線が出ているようなのです。
まー、これがどうして出てくるか、って話になってくるのですが、そもそも……

上の、「含まれる要素を排除した組み合わせの数」が計算で出せるのかとか、
判定無しに(集合に含まれるかどうかの判定って地味に重そうなので)数え上げは出来ないのか、
というのが目下の課題になりますね……

スポンサーサイト

PageTop

コメント


管理者にだけ表示を許可する