ある立体の問題。

ｎ（≧１）個の＜点＞とｍ（≧０）本の＜線＞からなる立体があるとします。
この立体は次のルールに従うとします。
１）任意の＜点＞は１本以上Ｎ本以下の線で別の＜点＞と接続している。
２）任意の＜線＞はある２つの＜点＞の間を接続する唯一の＜線＞である。
３）ｎ＝１の時は、１）に従わなくてよい。
この立体に対して、次の操作ができるとします。
Ａ）１個の＜点＞と１本の＜線＞を追加する。
Ｂ）１本の＜線＞を追加する。
ただし操作後の立体は最初の１）～２）のルールに従わなければなりません。

この条件のもと、
１個の＜点＞のみからなる立体から始めて、ｘ回以下の操作で次の操作が出来なく
なる確率
Ｐ（Ｎ，ｘ）は求められるでしょうか？
（Ｎで場合分けして構いません）
ちなみにＮ＝１の時はＰ（１，ｘ）＝１です。

No.8 回答者： stomachman 回答日時： 2001/01/10 22:41

まだよく分からないまま、ですけど....

　仮に、「操作をなるべく長く続けたい」という立場で考えることにします。A, Bを決める「誰か」の意図や確率の話はここでは度外視（後で考えれば良いでしょう）。
Aによって、点1個と辺１個ができる。Bによって、辺１個ができる。
ですからBが可能なためには、少なくとも２個の点において、点の持つ辺の個数（これを点の「価」と呼びましょうか）がN未満でなくちゃいけない。
Aが可能なためには、少なくとも１個の点の価がN未満でなくちゃいけない。
ところで、M個の点があるとき、最大[MN/2]本 ([]はガウスの記号）の辺が存在できる。M個の点を置くにはAが(M-1)回適用されている。従って、最大[MN/2] - (M-1)個のBが在って良い。全部で[MN/2] 個の操作（AまたはB）が並んだ列において、途中(つまり列の先頭m個の操作の列。ここにm<M)も常にBの数が[mN/2] - (m-1)以下であればこれが常に可能なのかどうか、という線で調べよう。
N=1ではBの数は[M/2]-M+1ですから、M=1のとき0, M>1なら負になって不可能。（前の回答で、実際そうなることは示しました）
N=2ではBの数は1ですから、最後にBが来ておしまい。Bがとどめを刺す。（これも実際に構成可能であることを示しました。）
N=3ではBの数は[3M/2]-M+1ですから、Mが偶数のときM/2+1、Mが奇数のときM/2+1/2です。途中はAの数の半分と同数以下のBがあって良い。最後はBでとどめです。
N=4ではBの数は[4M/2]-M+1ですから、Bの数はM+1。途中はAと同数のBが在ってよく、最後はBでとどめです。

これって多分Nが幾つでもOK？Aがくればまっすぐ延ばす。Bが来たら、価がN以下の点二つを適当に繋ぐ。自分自身に繋ぐ羽目にならないようにだけ気を付けるのは、多分いつでも可能だと思います。どの点も均等に価が増えるように（つまりどの２点についても価の違いが1以内になるように）していればいいんですよ。でも問題がまだよく分かってないので、厳密な証明までやる気にはなれませんが。

No.7 回答者： stomachman 回答日時： 2001/01/10 11:19

もうちょっと具体的に質問。

N=1の場合。
最初の1回にAが来たときだけ操作でき、そこで終わりです。
N=2の場合。
最初の2回にBが入っていると終わり。2回Aが続いた時点では、
(1) Aが続く限り幾らでも操作でき、Aが3n個の時にBが来ると終わり。その他の時にはBが来ると１度だけ操作して終わり。
(p) Aが続く限り幾らでも操作でき、Aが(p+2)n個の時にBが来ると終わり。その他の時にはBが来ると１度だけ操作して終わり。
(∞) Aが続く限り幾らでも操作でき、Bが来ると１度だけ操作して終わり。
のどれでも好きなのが選べます。(p=1,2,....)
(∞)はAが続く限り点と線を直線的に延ばしていって、Bが来たら両端を繋ぎます。
(p)はAが続く限り、Aの(p+2)回につき(p+2)点からなるループと、孤立点１個を作る、という操作をします。
こういう感じで、題意に沿ってますでしょうか？

No.6 回答者： stomachman 回答日時： 2001/01/09 22:05

atsuotaさんてば、

> 任意の＜線＞はある２つの＜点＞の間を接続する＜線＞なわけですから
　そうなんですか？＜線＞を追加するのに２つの＜点＞の間を接続する＜線＞が複数あっちゃいけないのはわかるけど、＜線＞が点をむすばなくちゃいけないという条件が付いているようには必ずしも見えませんけど。っていぢわる言っちゃいけませんね。
　そういう意味で解釈することに致しましょう。
　でも、確率を問うにはまだ早いですね。どうもkazu-kunさんてば、抽象化しすぎてません？
　まず、これはゲームなのかどうか。(A)(B)を選ぶ「誰か」はランダムに選ぶのか（だったら(A)と(B)の出現確率がどうなのか）、あるいは「立体」を見ながら意図的に決めるのか。操作するヒトとしては、なるべく早く操作できない状態になりたいのか、なるべく操作を続けたいのか、あるいは複数の選択肢があればランダムに選べというのか（その時は場合の数の数え方の規則がないと、等確率ということが定義できません。たとえば各点を区別するのか、トポロジーだけに注目するのかで確率が違ってきます。）。「誰か」の方の意図も操作するヒトと一致しているのか、それとも操作するヒトを妨害しようとしているのか。(A)(B)操作の列が予め全部与えられるのか、それとも操作ごとに与えられ予見できないのか。ゲームだとしたら確率じゃなくてまずは必勝手順の話になりますし。こういった事が全部関係すると思うんですが。
　もうすこしぶっちゃけて具体的状況を教えて戴けませんでしょうか。

No.5 回答者： atsuota 回答日時： 2001/01/09 21:04

＃４stomachmanさんありがとうございました。

がしかし、それだと条件２に合致しないような…？
任意の＜線＞はある２つの＜点＞の間を接続する＜線＞なわけですから、＜線＞の両端には＜点＞が必要かと思います。

で、そうなると、確かに１回は操作できますが、２回目の操作が不可能になるので、P(1,x)=1となるわけですね。

で、ようやく題意を理解したので、これから考えてみます。
（え！？ここでカッコ良く回答するんじゃないの？って突っ込まないで下さい）

No.4 回答者： stomachman 回答日時： 2001/01/09 16:23

いつもの悪い癖で、質問者をほったらかして議論しますが...

atsuotaさんのおっしゃるように、記載が変でした。
要するに、点とそれに一端を持つ線を、いっぱい並べていけば幾らでも増やせる、という事を言っているに過ぎません。
p1------, p2-------, というふうにね。

主旨としては、「点」「線」という用語、およびそれら満たすべき制約（題意に書いてない基本的制約）がきちんと定義されていないことに文句を付けてるだけです。それに、N>1ではこの問題、どうみたって自明ですよねえ。

No.3 回答者： atsuota 回答日時： 2001/01/09 13:36

回答ではありません。

訂正。

すいません、＃１で
> それにしては操作Bはできそうな気がします。
と書きましたが、操作Aの間違いです。（＃２でstomachmanさんが書かれているとおりです。）

さて＃２でstomachmanさんの書かれた後半部分がよくわかりませんでした。
N=1の場合の
１．まず１個の点p1がある。
２．p1に一端をもつ線を作る。
p1―――
３．この線のもう一つの端の所に新しい点p2を作り
p1―――p2
４．p1に一端をもつ線を作る。
このとき「p1に一端をもつ線を作る」とは、どういう線のことでしょうか？
p1―――p2
｜
｜
｜
とやるとp1でN=2となります。それとも既に引いてあるp1－p2間の線のこと？
さらに
５．この線のもう一つの端の所に新しい点p3を作り
？？？

私の疑問を晴らしてください。お願いします。

No.2 回答者： stomachman 回答日時： 2001/01/09 13:00

これは、できるかできないか、であり、そもそも確率とは何の関係もない問題です。

まず、N>1であれば、Aで幾らでも延ばせます。新しい点(p[n+1])を作り、最後に作った点p[n]と、新しい点p[n+1]を結ぶ線、を追加すればよい。これは際限がありません。だからN=1のときだけ検討すれば十分です。
●最初の点(p1)に対して、別の点(p2)を作り、p1とp2を結ぶ線を描くことができます。
　p1もp2も共に1本の線に繋がっているので、N=1の場合ですよね。実際にできたからP(1,x)=1は間違いで、少なくともP(1,0)=0ですね。
　さて、これ以上増やせないかというとそうじゃない。
●最初の点p1とp1に一端をもつ線を作る。この線のもう一つの端の所に新しい点p2を作り、p1に一端をもつ線を作る。この線のもう一つの端の所に新しい点p3を作り、p1とp3を結ぶ線を作る。
　どの点もN=1ですし、この手は幾らでも拡張が利く。

　線を描くには２つの点が要るに決まってる！という補足が来そうですが、題意にそんなこと含まれてません。察してくれは通用しない。数学はキビシイんです。再度、問題をきちんと定義することをお勧めします。

この回答への補足

確かに数学の問題としては不足がありましたので、補足します。
まずｘ≧１の時の話しです。（この問題は、ある作業を念頭に置いているので・・・全く操作しないというのは私の中では論外だったんです。）
それから、ＡとＢの操作は任意に選べる訳ではなく、誰かが勝手に操作
します。ですので、確率の問題になるわけです。
問題に不足がありすみませんでした。

補足日時：2001/01/09 18:51

No.1 回答者： atsuota 回答日時： 2001/01/09 05:13

すいません、P(N,x)がなんなのかよくわからないんですが。

例えばP(1,x)=1ということは、
１個の＜点＞から始めて、次の操作はできない
ということではないんですか？
それにしては操作Bはできそうな気がします。

一体？？？