ダンバー数問題（でいいの？）

http://d.hatena.ne.jp/tikani_nemuru_M/20091104/1257322803

Ｎ=3　で10となる美しい作図法がありましたにゃ。びくーりだ。

N=3ではP=8が最適解、が通説とされていたダンバー数業界にとってこれは衝撃であった(大げさ)。
で、御他聞に洩れずP=8説で納得していた私もガガーンとなったわけでした。
ブコメで解も示されていて自分で作図確認して納得もしたのだけど、地下猫さんの「美しい作図」が気になって再考してみた。
私のように忍耐力のない人間には、数学は「解がある」と分かっているときと分かってないときで取り組む気力に大きな差が出る(笑)。
まあそれはいいとして、御覧下さい、こちらがP=10のエレガントな解でございます。

こりゃーすごいね。誰が見ても納得の美しさ。



　

• 私の考え方

私は当初、幾何学的アプローチを考えていたのだけど、まず「ある一点を考えたとき、そこからN分岐し、さらにその先でN分岐して到達する点までを問題にするのだから、高々N×Nで押さえられるな」と思っていたのですね。
つまりN=3のときは高々9ポイントについて考えればいいと。
（当然ながらこの計算は間違い。実際には「ある一点からN分岐し、さらにN-1分岐する場合を、最初の一点含めて数え上げる」、すなわち、N＋N×(N-1)＋1が正解。N=3のときは10ポイント）

で、奇数点はどうも危うい気がしたので（何故なら、奇数点の場合、そこで非対称が発生する、つまり、全ての点から同じ数の枝が出ると考えたとき、点が奇数だとどこかで枝が一本余ると考えた。勿論これも誤り。N=2で五角形を考えれば分かる）、最大偶数値の8から考えた。

で、8個の点を幾何学的に配置すると4個4個なので、まあ、四角＋四角で考えますわな。
その場合で作図したのがこちら。

んで次に、先の計算ミスに気づいて10ポイントがありうることに気づいて再考を始めたのだけど、10点の組み合わせでは五角形+五角形と六角形+四角形が考えられるわけだが、どちらもどうも上手く行かなかった。
なので、幾何学思考は捨てて、ツリー描いて各点からの到達可能性で考えて行ったのだけど結局これも上手く行かなくて（このときの考え方の何がまずかったかは未検証）結局「10ポイントは不可能」と結論づけてしまったわけだ……。

で、続けてN=4の場合の試行に移っていったのだけど、こちらは上述の式から高々17点と推測される。
でも当時はid:imo758さんのP=13限界説が出ていたので、じゃあ14点で考えていったのだけど、七角形+七角形も五角形+五角形+四角形もなんか上手くいかなくて、ツリー式に考えても厳しいので、ちょっと諦め気味でした。

そんな折、N=3、P=10達成が報じられたので、そちらを検証していた私。
「あれ？これ、五角形をもう一段組み合わせたらN=4、P=15いけるんじゃね？」
と思ったわけなのですが、ちょっとこれは浅墓過ぎました。やはり同じ考え方では厳しい。
なのでP=15は今のところ未達成です。

• もう少し利口に考えろ、馬鹿。

そろそろ↑このようなお叱りが聞こえてきそうですね。
お前は大学で何を学んでたんだと……。

グラフ理論的に考えると、この問題はある点の集合Ｐから、任意のN点を選ぶ、その組み合わせにおいて各点が等しくN回ずつ現れる場合を求める、と書ける……ような気がします（いまいち自信がない）。
ある点をインデックス的に用いて、0{1,3,9}、1{0,4,5}…的に書き出していったとき、{}の中に現れる回数が等しくN回になるような組み合わせ、と。

で、これを表で考えるとこんな感じになるのかなと。
N=2の場合、先の式に当てはめて高々点は5個。
ゆえに、

のような表を考える。
この表の意味は、縦軸が各ポイント。横軸は、そのポイントから出ている枝の端点と考える。
例えば点1から点2と点5に枝が伸びているときはこう

そして、対称性から縦軸側にも同じ位置に○をプロットする。

これを繰り返して、「どの列を見ても、縦にも横にもきっかりN個○が並ぶ」組み合わせを見つければいい。
この場合で続けると、

となる。
まあこれをプロットすると五角形になるわけですが。

相当力技的ではあるけど、これだと計算機的にもアルゴリズム化しやすい気はする。
まあ、数学者的にはもう少しエレガントな一般化が可能な気もするけれど、エレガントな解法VS計算量による力技だと、後者に軍配が上がってしまう御時世な気もするので…（適当な感想）。

しかしこれ、描いてみて思ったけどエイトクイーン問題に似てますね。
N個並ぶ、なので問題としてはあちらより複雑だけど、対称性の縛りがあるので条件としてはどっこいどっこい？

多分世間的にはとっくにこっちの方向での試算が進んでるんだろうと思われて、幾何学的に考えてとかツリー描いて到達可能性とか迂遠なことをやってるのは私くらいだったんだろうが、まあ、自分の覚え書き的に……。
（しかしおよそ一年ぶりのダイアリ更新がこれか）。

• 追記

昨日考えていたやり方。

例はN=4,P=14の場合。

まず、14個の点をプロットし、そのうち1点から4本の枝を出す。
次にその先の4点から3本以下の枝を出すことで全ての点を尽くす。

ここで、4本の枝を出し切った点を赤くプロットする。
これらの点はこれ以上枝を出せない。

次に赤い点の一つを選び（☆印）そこから現在の状態で2hopで到達可能な点に二重丸をつける。

到達できていない点に対し、1hopで先の点から枝を伸ばす。
これで全ての点に2hopで到達可能となる。

別の赤い点に移動して同様のことを繰り返す（黄☆印）。
ここでは、まだ枝を伸ばせる可能性がある点を赤☆印で示している。

前述の赤☆から、適宜未到達の点に枝を伸ばす。
枝を伸ばしたことで、枝の本数が最大に達した点を再度赤くプロットする。
こうして、赤い点が増えるたびに同じことを繰り返す。

これによって、稠密な精査が行えると思ったのだけど、やっぱり枝の伸ばし方には恣意性があるので中々全てを尽くすのは難しい。
結構頑張った例としては

があるのだけど、これもこの時点で詰んでます。
まあ、これも計算機パワーに頼ることで、うまいアルゴリズム組めば追い詰めて行ける気もしますけど。

• 再追記

takanorikidoさんに突っ込み頂きました。上記の陣取り式は十分条件を満たさないとのこと。言われてみりゃ2hopで到達可能の条件が全然入ってないや上の議論。うーん、まだまだ考えが浅かったか……。

• 再々追記

というわけで必要条件を考慮するアルゴリズム考えてみたよー。

まず上記の表が完成した時点で、1行目に着目します。
ここでは2と5に○が入っているので、自身を含め、1、2、5の上に黄○をポインティング。

次に、2の行を見ていくと、1と3に○が入っているので、既にポイントされている1を除き、3の上に黄○をポインティング。

次に、5の行を見ていくと、1と4に○が入っているので、4の上に黄○をポインティング。
1の行に○印が入っているのは2と5の二点なので、この時点で、最上段の数字の上に全て黄○が入っていたら、横の1のとなりに☆をマーク。

まあ要するに「2hopで全てのポイントに届く」の検証です。
これを繰り返して、縦列の数字の隣に全て☆が並べば条件成立。
どうかな？

• ブコメにお返事

id:md2tak ちなみにモンテカルロ法でN=4、P=14,15を１０万回ぐらい試行してみたが、無理だった。

考え方が正しいかどうかいまいち自信がありませんが、P=14の場合、ある一点からN=4点に接続しうる組み合わせは13×12×11×10通り、掛けることのP=14点なので、
　14×13×12×11×10＝240240通り
で全ての場合を尽くせそうな気がするので、試行を25万回にすれば白黒はっきりするのかも！？
あ、でもモンテカルロ法だと、過去の同一試行を弾けないのかな。

• 結論

http://d.hatena.ne.jp/smoking186/20091106/1257485014

まともな数学的見解が出ておりました。
あー、距離空間ね。直径ね。ありましたねそんな概念が……。
紹介されていた論文
http://www.combinatorics.org/Surveys/ds14.pdf
すっごい綺麗。

• N=4,P=15

上記で私が放り出した五角形2つ＋星型での解法をimo758さんが完成させて下さいました！
http://d.hatena.ne.jp/imo758/20091106
これはすごい！ほんとに感動。
imo758さんの粘りに感服です。
いやー、やっぱ私忍耐力ないなー(笑)。