Question

ゲスト

ゲーム スプラウト
数学が好きで得意な方、 教えて頂けると嬉しいです。

io
2. スプラウト

問題 ゲーム スプラウト
n 個の孤立点を適当に配置し、以下のルールに従って、2 人のプレイヤーは交互にゲームを進めていく。

①

@
③
@
(GO)

   

新たに作る。

 

|え、更に、その辺の上|

 

適当に頂点を選んで、接続する辺を1つ付
各頂点の次数は 8 以下。

ループも話す。
どの 2 つの辺も、頂点以外で交わってはいけない。
平面グラフとして、①から④を満たす辺が引けなくなった方が負け。

後手の手によらず、先手がうまく手を選んで必ず勝てる時に、先手必勝という。逆に、 先手の手によら
ず、後手が必ず勝てる手がある時、後手必勝という。

司義s+」

頂点く<のように、ある頂点から出て同じ頂点に入る辺を ループ (loop )、
頂点がのような隣接する辺がない頂点を孤立点 (solated vertex )という。

与えられたグラフが、頂点以外では、どの 2 つの辺も交わらないように平面上に

 

描ける時、平面グラフ

であるという。

課題A

nが5や6 の場合について、先手必勝か、後手必勝か調べてみよ。
nmが7以上の場合についてはどうか?

スプラウト