一昨日のパズル。もう終わっちゃってるけど、乱数でのゴリ押しだけでは芸がなさ過ぎるでしょう常識的に考えて……ということで、ちょっと改良した。
互いに行き着けないノードの数をスコア（当然低い方が良い）として、ステップごとに上位1/4だけ残してそれを4倍に複製。二本のエッジをちょん切ってつなぎ替える。
N=4で15個の解はわりとすんなり見つけられるようになった。
15個のノード。
30本のエッジ。
0のスコア。
0:[9, 12, 5, 8]
1:[3, 9, 11, 6]
2:[5, 11, 13, 12]
3:[1, 5, 10, 13]
4:[7, 5, 14, 6]
5:[2, 4, 3, 0]
6:[14, 12, 1, 4]
7:[4, 11, 9, 10]
8:[10, 14, 11, 0]
9:[13, 0, 7, 1]
10:[8, 12, 7, 3]
11:[2, 7, 1, 8]
12:[6, 10, 0, 2]
13:[9, 14, 2, 3]
14:[6, 13, 8, 4]
まだやってないけど、パラメータ設定とかける時間次第ではN=5もいけるかもしれん。
11/9追記
ちょっと時間かかったけどN=5で24個いけた。populationは800に設定。
24個のノード。
60本のエッジ。
0のスコア。
0:[6, 11, 7, 16, 13]
1:[15, 3, 13, 4, 18]
2:[6, 5, 14, 3, 23]
3:[1, 7, 20, 2, 11]
4:[19, 13, 17, 1, 5]
5:[2, 16, 4, 12, 10]
6:[2, 0, 23, 15, 19]
7:[17, 21, 0, 3, 10]
8:[12, 10, 23, 13, 20]
9:[14, 20, 17, 15, 16]
10:[8, 22, 15, 7, 5]
11:[12, 0, 22, 3, 17]
12:[8, 11, 21, 15, 5]
13:[14, 4, 1, 8, 0]
14:[13, 9, 21, 2, 22]
15:[1, 6, 9, 12, 10]
16:[20, 0, 5, 18, 9]
17:[23, 7, 4, 9, 11]
18:[23, 21, 1, 22, 16]
19:[20, 22, 4, 6, 21]
20:[19, 16, 9, 3, 8]
21:[7, 18, 14, 12, 19]
22:[19, 10, 11, 14, 18]
23:[18, 17, 8, 6, 2]
おまけ
もうすぐCDが出るらしい。
by 木戸孝紀
tags:Ruby パズル プログラミング 数学
ううむ、地下猫さんが『科学がきらわれる理由』をおすすめされた背景では、そんなこと考えていたのか。これはちょっと予想外だった。
確かに『科学がきらわれる理由』は素晴らしい本だが、ダンバー数自体は「まあそりゃ限度のある要素の集まりには何かしらの限界はあるだろうねえ」ぐらいの受け取り方をしておけばいいものだろう。
少なくとも現時点で、具体的にその数に何かがある・その数から何かが言えると考えるのは、百匹目の猿現象みたいな純然たるオカルトとは異なるものの、六次の隔たりレベルの通俗科学でしかないと思うなあ。
まあそれはそれとして、
平面上にいくつかの点がある。点と点が線で結ばれている。１本任意の１点から出ている線の数はＮ。任意の２点を取り出すと、その２点は直接、あるいは、別の１点を経由してつながっている。このような状況が可能な点の個数の最大値は？
という問題そのものには久々にパズル欲が刺激された……と言いたいところだけど、こりゃパズルってレベルじゃねーぞ！
直感で根拠はないが、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を見つけるスクリプトがさっと書けたのと、一般には未解決だろうと一目で当たりがつけられたということで個人的には満足しておこう。
おまけ
プログラミングつながり。これは楽しい。
by 木戸孝紀
tags:Ruby パズル プログラミング 数学
全員で生還する確率を上げたければ、皆が何かしらの意味で協調した行動を取らなければならない。それなのに、挑戦中にも挑戦後に一切情報をやりとりできない。この一見取り付く島もなさそうなルールの裏をかくにはどうしたらいいか。
情報をやりとりすることはできなくても、新しく全員が得ることができる情報がひとつだけある。というか、ひとつしかない。名前の書かれた紙である。突破口があるとしたらこれしかない。
考えやすくするためにまず用語の準備をしよう。
生徒には出席番号がついているものとして以後数字で考える。ついていなければどんな基準でもジャンケンでもくじ引きでもいいので適当に決める。以後生徒1〜42と呼ぶ。生徒nの名前の書かれた紙を紙nと呼ぶ。
ロッカーにも番号を振る。たとえばロッカーに番号や記号がついていたら辞書順あるいは小さい順に、仮に番号がついてなかったとしても、左上が1でその右が2など事前に決めておいた何らかの規則性に基づいて、やはり1〜42と番号を振る。以後ロッカー1〜42と呼ぶ。
さらに便宜的に同じ状態の42部屋で全員が同時に挑戦しているとして考え、生徒1が案内される部屋を教室1と呼ぶことにする。同様にして仮想の別々の教室をそれぞれ教室1〜42と呼ぶことにする。
このゲームでは、生き残るために必要なのは自分の名前の紙だけである。仮に他人の名前の紙が入っていると分かっているロッカーがあるとしたら、そこを開けるのは避けるべきである。これが基本方針である。
それを知る手段がないから困ってるんだろーが！ と思ってしまいそうだが、もう少し待て。
まず最初に開けるロッカーは全員別々にすると決めよう。あえて違う選択をする理由はないのでわかりやすさのため、生徒nはロッカーnを開けることにする。
仮に自分が生徒13だとして、ロッカー13を開ける。もし幸運にも紙13が出てきたら、それでクリアだ。あとは他人の幸運を祈るのみである。しかし、そんなことは1/42の確率でしか起きないので、大抵は外れる。
出てきたのが紙4だったとする。生徒13は「ああ外れた」と嘆き悲しむ。しかし、死にたくないので嘆いてばかりいないで2個目のロッカーを選ばなければならない。2個目はもう当てずっぽうで選ぶしかないだろうか？ そんなことはない。
実はこのとき、生徒13は、絶対に手に入らないと思われた他の部屋の情報を、知ることができている。
- 教室4で生徒4が、紙4以外の紙を引き「ああ外れた」と嘆き悲しんでいるということ
がわかるのだ。なぜなら、紙4はロッカー13に入っているのだから。ロッカー4を開けることになっている生徒4が紙4を引いたということは、ありえない。
ということは、生徒13が次に選ぶべきは？ ロッカー4である。なぜか？ この時点で生徒13が何らかの情報を持っているのは教室4に関してのみである。たとえば教室7でロッカー7を開けた生徒7が紙7を引いている可能性は、僅かながらある。
もちろん、生徒13が自分の生き残りだけ考えた場合、ロッカー4もロッカー7も「紙13が入っているかもしれない」ことにおいては何も変わることはない。
しかし、全員で生き残りたいと考えている場合には、すでに他の生徒の正解と決定している（かもしれない）ロッカーを避けることには意味がある。
よって生徒13は2個目にロッカー4を開ける。出てきたのが仮に紙9だったとする。このとき、生徒13には新たに2つのことがわかる。
- 少し前、教室4で生徒4が1個目に開けたロッカー4から出たのは紙9だったこと
- 現在、教室4で生徒4がロッカー9を開けて紙x(4,9以外の何か）を見ていること
- 現在、教室9で生徒9はロッカーxを開けて紙yを見ているがyは9ではないこと
最初の2つは当然として、紙yが紙9ではないというのはなぜわかるのか？
紙yが紙9だとすると、紙9はロッカー4に入っているのだから、生徒9は2回目にロッカー4を開けたことになり、ひいては1回目に紙4の入ったロッカー13を開けたことになる。作戦上1回目にロッカー13を開けるのは生徒13である自分なのだから、生徒9が作戦に逆らったことになる。作戦に逆らう生徒はいないことになっているので矛盾である。よってyは9ではない。
こうして2個目のロッカーを開けた時点で、生徒13は部屋を一歩も出ずして、生徒4と生徒9がいまだクリアしていないことがわかる。
生徒13が3個目に開けるべきロッカーは？ 先と同様の論理で9だ。なぜなら紙13が入っているかもしれない点では他と変わらず、かつ、すでに他の生徒の正解として確定してしまっている可能性がないロッカーだからだ。
ここで、なんと！ ロッカー9から紙13が出てきたとしよう。生徒13はもちろんクリアの喜びで雀躍する。だが、同時に生徒4と生徒9もクリアの喜びで雀躍していることがわかる。
というのは、少し前、生徒4が開けたロッカー9に入っていた紙xが紙13だったというのなら、今現在、生徒4はロッカー13を開けて紙4を発見したところだからだ。生徒9に関しても同様。
では、肝心のその作戦で全員生き残れる確率はいくらかぐらいになるのか？ とりあえず10万回試行させてみたところ、なんと約32%もある。こんな怖ろしいゲームに巻き込まれて笑い話で済む可能性が1/3近くもあるなんて、約4兆4千億分の1とか言ってたのに比べると夢のような話ではないか。
ただし、いくら同様に続けても紙13が発見できず、今だクリアしていないと分かっている生徒が増えていくだけの可能性もある。21個目のロッカーを開けても紙13が発見できなかった場合。生徒13は死ぬ。
そして同時に、これまで紙の上に名前を見てきた4,9をはじめとする他の21人も同時に死ぬということがわかってしまう。なぜなら、すでに自分とその21人のクリアはかならず同時になることがわかっているからだ。自分が助かっていない以上みんな死ぬ。
要するに、例の場合4,9,13の3つのロッカーが13→4→9→13というループを形成していたことになる。すべての番号は必ず1以上42以下の長さのループに所属することになる。ルール上そうならないことは不可能である。
22以上の長さのループが存在しさえしなければ、全員が、確実にクリアできる。逆に22以上の長さのループが存在してしまうと、そのループにつかまった生徒は一人残らず死ぬ。
ループの長さがいくつになるパターンがいくつあるかをちゃんと計算すれば厳密な確率も求まるはず……だが、その方法は自分も思い出せないので発展課題にしておく。
試行に使ったRubyスクリプト
#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-
TIMES = 10000
NUM = 42
max = NUM / 2
all = 0
win = 0
live_sum = 0
dead_sum = 0
TIMES.times do
all += 1
arr = (0...NUM).to_a
arr = arr.sort_by{|i| rand}
live = 0
dead = 0
(0...NUM).to_a.each do |i|
cnt = 0
box = i
loop do
cnt += 1
if cnt > max
dead += 1
break
end
if arr[box] == i
live += 1
break
else
box = arr[box]
end
end
end
live_sum += live
dead_sum += dead
win += 1 if live == NUM
puts "#{win}/#{all}回目の試行：#{live}人生存・#{dead}人死亡"
end
puts "個人が助かる確率：#{live_sum.to_f / (live_sum + dead_sum).to_f}"
puts "全員助かる確率：#{win.to_f / all.to_f}"
追記 8/5
HandDrumさんのコメントを元に、厳密解の求め方をコードにしたもの。これでよさそう。
#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-
class Integer
def factorial
(1..self).inject(1){|r, i| r * i}
end
def permutation(n)
self.factorial / (self - n).factorial
end
end
NUM = 42
puts 1 - (0...(NUM/2)).inject(0) {|r, n| r + NUM.permutation(NUM - n) / (NUM - n) * n.factorial}.to_f / NUM.factorial
おまけ
死にゲーつながり。選曲と天丼が秀逸。（釣り・微ビックリ注意）
by 木戸孝紀
tags:クイズ ネタ パズル 解答 数学
極東の全体主義国家大東亜共和国では、学力向上のため、全国の中学3年生のクラスから無差別に数十クラスを抽出して、命を賭けたパズルをさせるという怖ろしいプログラムが実行されています。
あなたの3年B組（生徒数42名）は運悪くこのプログラムに選ばれてしまいました。そして、今年のパズルのルールは以下のようなものです。
今からクラスの生徒は一人づつ別々に、42個のロッカーがある教室に案内されます。それぞれのロッカーの中には紙が一枚入っていて、それぞれの紙には3年B組の誰か一人の名前が記されています。
教室に案内された各生徒は、21個のロッカーを開けて調べるチャンスを与えられます。自分の名前が記された紙を発見できれば、勝利。生きて帰れます。21個開けても自分の名前が記された紙を発見できなければ、失敗。監視している軍隊に射殺されてしまいます。
生還した生徒も隔離されるので、まだ挑戦していない生徒に情報を伝えることはできません。また、ある生徒が教室で何をしても、次の生徒が挑戦する前に内部は完全に整頓され、最初の生徒が来たときと全く同じ状態に戻されてしまい、教室の中に情報を残すこともできません。
ただし、プログラムがスタートする前に、全員でゆっくり時間をかけて相談をすることが可能です。
あなたは主人公属性の思考法の持ち主なので、どうしても全員生きて帰りたいです。全員が助かる作戦を考えて下さい。その作戦を使った場合、全員が助かる確率はいくらぐらいになるでしょうか。
おまけ
射殺つながり。TECH Winって懐かしい。（バイオレンス注意）
by 木戸孝紀
tags:クイズ ネタ パズル 数学
最近Ruby1.9.1が出たので、乗り換えついでに久しぶりにプログラミングっぽい話題でもと思い、ピクロスのソルバを書いてみました。
ファイル
使い方
ruby picross.rb sample.txt
と問題ファイルを与えると、
｜ 2 1 1 2 ｜
｜ 1 1 1 1 3 2｜
｜ 4 6 2 1 1 2 2 1｜
----＋----------------＋
4｜ ｜
2 2｜ ｜
2 2｜ ｜
8｜ ｜
2｜ ｜
2 2｜ ｜
2 2｜ ｜
4｜ ｜
----＋----------------＋
｜ 2 1 1 2 ｜
｜ 1 1 1 1 3 2｜
｜ 4 6 2 1 1 2 2 1｜
----＋----------------＋
4｜××■■■■××｜
2 2｜×■■××■■×｜
2 2｜■■××××■■｜
8｜■■■■■■■■｜
2｜■■××××××｜
2 2｜■■××××■■｜
2 2｜×■■××■■×｜
4｜××■■■■××｜
----＋----------------＋
のような結果を表示します。解なしなら解なしと判定します。解が一つ以上あれば最初に見つかった解を表示します。複数解になっているかどうかまでは気にしません。
問題ファイルの形式は、
- 最初の一行が盤面の高さと幅
- 次の行からは、一行ごとに
- 横のヒントを左から順に並べたものを、上から下に
- 縦のヒントを上から順に並べたものを、左から右に
- 区切り文字に使えるのは半角のスペースかカンマ
です。詳しくはサンプル問題のファイルを見て下さい。
ruby picross.rb sample.txt -v
とオプションをつけると途中経過も表示します。この場合よほど単純な問題でなければ長くなりすぎるので、
ruby picross.rb sample.txt -v > result.txt
などとして、後で結果を書き出したファイルを見るようにした方がいいでしょう。大きな問題でも時間とRubyの許す限り解けるはずですが、ヒントの数字が3桁に達するような場合は、表示されるのは下2桁の値だけになります。
ちなみに単純な計算を山ほど行うので、1.9.1では1.8系より目に見えて早くなりました。うちの環境では30×30の広さでも数秒、さらにスカスカの難しそうな問題でもせいぜい30秒程度です。
あまり巨大なのは問題が見つからなかったので試していませんが、人間が解くことを想定しているような問題なら大体リーズナブルな時間で解けるのではないかと思います。
また、一番面倒くさかったのは解かせてみる問題を打ち込むことでした。入力した問題があったらメールフォームからでも送っていただけるとありがたいです。もちろん著作権のあるものは公開できませんが。
追記 2/20
横に細長い問題の扱いでバグがあったので修正しました。
追記 2/24
途中経過の表示時に「★」マークを出力するようにしました。結果ファイルで「★」を次々に検索するようにすれば簡易アニメーションのように見ることができるようになるはず。
おまけ
誰が得すんだこのTAS。
by 木戸孝紀
tags:Ruby パズル ピクロス プログラミング
- まず誰か1人でいいので、自分と志を同じくするか、自分の言いなりになる人間を連れてくる。
- その2人を含む3人で、多数決で全てを決する1つ目の秘密結社を作る。
- その3人を含む5人で、多数決で全てを決する2つ目の秘密結社を作る。
- その5人を含む9人で、多数決で全てを決する3つ目の秘密結社を作る。
- n番目の秘密結社は2^n+1人を支配できる。
世界の総人口はいまちょっとググったところでは約67億人。
2^10 = 1024 ≒ 10^3
2^33 ≒ 8*10^9 > 67*10^8
だから、33段階の秘密結社を通じて全人類を支配することができる。めでたしめでたし……という話が何の役に立つだろうか？
世界で最も大きな組織には何段階の階級が存在するでしょうか？
というフェルミ推定の問題が出されたときに役に立つかも知れない。実際には全人類は1つの組織に統一されていないし、各階層が単純多数決というもっとも効率が悪いと思われる意志決定方法であってこの数なので、現実の組織に必要な階層数はこの推計よりかなり少ないと思ってよいだろう。
たとえばアメリカ合衆国大統領からイラクのどこかで哨戒中の二等兵に何か命令を伝える必要が生じたとする。途中で何回命令を受け渡す必要があるだろうか？ 直接つまり1ということはなさそうだというのは常識でわかるが、上限について何か推定できることがあるだろうか。ここで33より多くなることは絶対にありえないと断言してよさそうである。
答え合わせにちょっとググってみる。概ね妥当と言ってよさそうである。
おまけ
by 木戸孝紀
tags:パズル フェルミ推定 社会 数学
上のニュースを見てルービックキューブで検索していたら、昔持っていたこれが復刻されているのを発見した。
もっとも、様々な点でルービックキューブに比べると遥かに劣る。一番の問題は繋ぎの部分がテグスのせいで耐久性がなくて、ちょっと力の入れ方を間違えたり古くなったりするとすぐ壊れるところで、昔もかなり短い時間で壊れたような記憶がある。
今考えるとそこまで面白いとも思えないのだが、かなり懐かしい。買ってみようかな。
おまけ
これと同じ作者とか。多芸だなあ。
by 木戸孝紀
tags:おもちゃ パズル 買い物
清涼飲料水のキャップのオマケとして、10 種類の清涼飲料水マンのキャップがついてくるキャンペーンがありました。そこで、豪気な凛さんは 24 本の箱買いを実行しました。24 本も買えば、10 種類そろっていそうな感じですが、実際には（以下省略）そこで、そろわない場合の確率はどのくらいになるのか？ 果たして凛さんは、全部の種類の清涼飲料水マンのキャップを持っているのだろうか？
（サンプル: "多倍長計算のサンプル(ペプシ算)"）
ペプシ算ファイナル – 永字八法で知って、久々にパズル欲を触発されたのでやってみた。我ながらなかなかエレガント。大元ページの再帰的な計算法では手も足も出ない数になっても瞬殺。rubyのBignumが許す限り。
pepsi.rb
class Integer
def factorial
(1..self).inject(1){|r, i| r * i}
end
def combination(n)
self.factorial / (n.factorial * (self - n).factorial)
end
end
def pepsi(m, n)
result = (0..m).inject(0){|r, i| r + (-1)**i * m.combination(i) * (m - i)**n}
(result * 10000000000000000 / m**n).to_f / 10000000000000000
end
puts pepsi(ARGV[0].to_i, ARGV[1].to_i)
下のように実行するとm種類のおまけ付きのペプシn本入りを箱買いしたときにコンプできている確率を返してくれます。
ruby pepsi.rb m n
たとえば例題の通りなら、
ruby pepsi.rb 10 24
ね。それだけ。
11/27追記
combinationも整数のメソッドにしてみたりちょっと表現を整理。ロジックはまったく一緒。それと、30 300程度で計算できなくなるのは、よく見たらBignumに入りきらないって言ってるんじゃなくてFloatで表現できないと言ってるだけだった。道理で少なすぎると思った。整数だけで最後の割り算をするようにしたらもっとでかい数でもいけるようになった。
ruby pepsi.rb 365 2287
0.500370783936947
つまり誕生日が均等に分布していると仮定して2月29日を無視した場合、人口2287人以上の街では「毎日誰かしらは誕生日を迎えている」確率5割以上。へー。
おまけ
by 木戸孝紀
tags:Ruby パズル プログラミング 数学
|
|
|
木戸孝紀
