ううむ、地下猫さんが『科学がきらわれる理由』をおすすめされた背景では、そんなこと考えていたのか。これはちょっと予想外だった。
確かに『科学がきらわれる理由』は素晴らしい本だが、ダンバー数自体は「まあそりゃ限度のある要素の集まりには何かしらの限界はあるだろうねえ」ぐらいの受け取り方をしておけばいいものだろう。
少なくとも現時点で、具体的にその数に何かがある・その数から何かが言えると考えるのは、百匹目の猿現象みたいな純然たるオカルトとは異なるものの、六次の隔たりレベルの通俗科学でしかないと思うなあ。
まあそれはそれとして、
平面上にいくつかの点がある。点と点が線で結ばれている。１本任意の１点から出ている線の数はＮ。任意の２点を取り出すと、その２点は直接、あるいは、別の１点を経由してつながっている。このような状況が可能な点の個数の最大値は？
という問題そのものには久々にパズル欲が刺激された……と言いたいところだけど、こりゃパズルってレベルじゃねーぞ！
直感で根拠はないが、M、Nが一般の場合の解を求めるのは、数学上の未解決問題ではないかと思う。具体的な数にしたってN = 150なんてとてもとても。
かと言って、一応数学野郎・プログラム野郎の端くれのつもりなのに手も足も出ずに終わるのは悔しいので、小さい数ぐらいでなら遊べるように、ゴリ押しで解を探すスクリプトを書いた。
見つからないと延々と探し続けるので、諦めるときはCtrl+Cで止めて下さい。（実行できる人なら止め方も知ってると思うけど。）
N = 3の時の最大個数は10のようだ。理論上 N^2+1 を上回ることはありえないのでN = 3については解決。
10個のノード。
15本のエッジ。
[0, 1, 2, 7]
[1, 0, 9, 6]
[2, 0, 5, 3]
[3, 2, 8, 6]
[4, 6, 5, 7]
[5, 2, 4, 9]
[6, 1, 3, 4]
[7, 0, 4, 8]
[8, 3, 7, 9]
[9, 1, 5, 8]
N = 4の時は13まで、
13個のノード。
26本のエッジ。
[0, 6, 11, 9, 4]
[1, 6, 11, 12, 10]
[2, 8, 11, 6, 4]
[3, 5, 4, 7, 12]
[4, 0, 2, 3, 12]
[5, 3, 8, 6, 7]
[6, 0, 1, 2, 5]
[7, 3, 5, 11, 9]
[8, 2, 5, 10, 9]
[9, 0, 7, 8, 10]
[10, 1, 8, 9, 12]
[11, 0, 1, 2, 7]
[12, 1, 3, 4, 10]
N = 5の時は16まで、
16個のノード。
40本のエッジ。
[0, 5, 10, 8, 9, 1]
[1, 3, 15, 11, 0, 14]
[2, 10, 12, 11, 4, 3]
[3, 10, 6, 1, 4, 2]
[4, 8, 3, 15, 9, 2]
[5, 15, 0, 7, 10, 14]
[6, 10, 3, 13, 7, 8]
[7, 15, 13, 5, 6, 12]
[8, 4, 0, 6, 14, 11]
[9, 15, 12, 4, 13, 0]
[10, 3, 6, 2, 0, 5]
[11, 2, 13, 14, 1, 8]
[12, 9, 2, 13, 14, 7]
[13, 6, 7, 9, 12, 11]
[14, 5, 12, 11, 8, 1]
[15, 9, 5, 1, 7, 4]
N = 6の時は20個まで発見。（まだあるかも。）（追記：N=4で14はあるみたい。（2009-11-04 – imo758の日記）
20個のノード。
59本のエッジ。
[0, 18, 1, 5, 8, 17, 13]
[1, 7, 0, 10, 4, 16, 14]
[2, 19, 16, 10, 5, 13, 6]
[3, 7, 9, 11, 19, 16, 13]
[4, 12, 18, 16, 19, 1, 11]
[5, 7, 8, 9, 18, 2, 0]
[6, 15, 10, 17, 2, 12, 9]
[7, 9, 3, 5, 1, 15, 17]
[8, 5, 12, 0, 11]
[9, 18, 7, 3, 5, 12, 6]
[10, 12, 15, 2, 6, 13, 1]
[11, 3, 19, 15, 4, 16, 8]
[12, 10, 4, 8, 6, 9, 14]
[13, 19, 10, 2, 18, 0, 3]
[14, 15, 18, 1, 12, 19, 17]
[15, 14, 17, 6, 7, 10, 11]
[16, 17, 2, 4, 1, 11, 3]
[17, 15, 16, 7, 6, 14, 0]
[18, 9, 0, 4, 5, 14, 13]
[19, 2, 4, 13, 11, 3, 14]
もちろん完全ランダムなので、見つからなくてもない証明にはならないが、見つかった解は正しい（はず）。
追記
やっとまともにグラフ理論っぽい説明が来てくれた。面白い。
N=4は15まであるのかよ。やはりN=4で早くもゴリ押しは通用しなくなるみたいだな。まあ今回はN=3の10を見つけるスクリプトがさっと書けたのと、一般には未解決だろうと一目で当たりがつけられたということで個人的には満足しておこう。
おまけ
プログラミングつながり。これは楽しい。
コメント
[ひとりごと][応答]数学野郎どもアリガトウ
前回エントリにトラバありがとう＞数学野郎ども 求めたい値をＰとすると Ｎ=3でＰ=10となる美しい作図は ダンバー数問題（でいいの？） – 雑記 Ｎ=4でＰ=15となるこれまた美しい作図は N=…
もう仲良すぎだろおまいらw
＞高橋直樹
その内容のコメなら僕のところにしてほしいのだが
ここには関係ないじゃん
＞木戸孝紀
sk-44とはゆっくり遊んでもらうよ。
とりあえずいまのところは周囲をぐるぐる。
そうですね、うちのブログで書くべきことでした。すみません。
ちょっとその物言いはねーだろとかちんと来てしまったのでつい書き込んでしまいました。
>社会問題考えてて数学上の未解決問題（たぶん）に
>たどり着くなんて誰にでもできるこっちゃねえぞ（笑）。
文芸の世界でやってほしいですねえ、そういうのは。
突っ込みどうもです、十分条件になり得ないとは……こちらも再考することにします。
実際、もう少し押さえ込める条件はありそうなんですよね……。
昨日私が考えていた、ツリー探索式に追い込んでく方法について自サイトの方に追記しました。
＞地下猫さん
表現の自由の話は突き詰めると自由意志の話と究極の価値の話に
いかざるを得なくて、sk-44氏との最後のあたりは実際行きかけてたから
面白いかと思ってたのに、ちょっとそれましたかねえ。
そっち方面の話はいつか自分でするときはするので
すいませんがいまはパス。
＞高橋直樹さん
うーん、そんなに悪意にばっかりとらなくてもいいじゃんかと思うが。
科学で言うなら正しい回答より魅力的な問題を出す方が
往々にして価値が高いのですよ。
社会問題考えてて数学上の未解決問題（たぶん）に
たどり着くなんて誰にでもできるこっちゃねえぞ（笑）。
もし今後お互いに対する言及がメインの発言をする場合は
それぞれ自分の場所でしてください。
＞angmarさん
3→10の時の作図はお見事です。
4次元ネタとか好きならおおっと思いますよね。
＞ツリー探索式に解を求めるアルゴリズムでしょうか。
うんにゃ、今載せてるプログラムはもっとバカです。
とにかくランダムに合法的なグラフを作って
とにかく条件にあっているかチェックするだけ。
treeと入っているのは単にそれっぽい用語が
思いつかなかったから使っているだけで、
厳密には間違いだろう。
N=4で14の解が見つからないのはバグってるのか、
それとも計算量的に早くもムリなのか
どっちなのだろう……。
＞エイトクイーン的解法
最初魔方陣的なやり方は考えたけど、
魔方陣的に正しいのは解の必要条件かもしれないけど、
十分条件じゃないんだよね。
たとえば普通の5角形を縦に二つ重ねただけの
グラフを考えると、
＞「どの列を見ても、縦にも横にもきっかりN個○が並ぶ」
という条件は満たすけど、
元の問題のN=3の答えとしては間違ってる。
そもそもノードから出るエッジの数が一定という条件が
あればどんなグラフでもその条件は
達成されるんじゃないのかな。
改良する場合どうすりゃいいかなあ。
こんにちは。
rubyはよく分からないのでプログラム斜め読みで申し訳ないんですけど、こちらはツリー探索式に解を求めるアルゴリズムでしょうか。
エイトクイーン問題式に解けないかな？と言う考察をしてみました。自信はあまりナイです（笑）。御笑覧頂ければ。
http://d.hatena.ne.jp/angmar/20091106/1257475789
忙しくて数学問題自体には取り組もうともしなかった俺がいうのもなんだけどさー、根拠もない思いつきの主張をその日のうちに撤回して恥じない態度はどーよ。グラフ理論の問題は、紙の上でエレガントな解法があるとは限らなくて、こういう手間がかかる解法しかないものが多いんだ。自分である程度計算して、見込みがあるのが分かってから提示したほうがよかったんじゃないかとは思うよ。直感的に、多項式時間で解けなさそうな問題だし、やりたくないなーとみんな思っただろう。木戸さんは偉いよ。
ダンバー数と真正性の水準の結びつけは、少なくとも今回の考え方では無理筋っぽかったよねー。
自分のところのコメ欄にも書いたんだけど、社会的認知の各モジュールを資源と捉え、この資源を活用できるような社会がなんとか作れないもんかということを考えているんで、ダンバー数だの真正性の水準だのというところにひっかかってんのよ。
進化の過程で培われてきた「道徳的心性」という資源を活用できるような条件をつくって、低コストでそれなりの公正を実現できんものかなあ、と。
例えば表現の自由にしても、法的に禁止するのはどうしても趣味にあわんのだけど、だからといってその「コスト」負担を弱者に負わせるってのも気にくわないわけで。
だから法などに頼らずにコストを分散させたいのだけれど、その方法として思いついているのが、が例えば公共圏であり、あるいは共同性の規模だったりするわけだ。
なかなかムツカチイですな。