メイン

雑念レポート アーカイブ

2005年01月05日

さいころをn個投げたとき、目の和が4の倍数になる確率

解けたので、記念に。


【問題】
さいころをn個投げたとき、目の和が4の倍数になる確率 a(n) を求めよ。


【解答】
さいころを n 個投げたときの目の和が
4で割って1余る数になる確率を、b(n) とおきます。
同様に、4で割って2余る数になる確率を c(n)、
4で割って3余る数になる確率を d(n) とおきます。

a(n),b(n),c(n),d(n) を、それぞれ a(n-1),b(n-1),c(n-1),d(n-1) を
用いて表します。
つまり、確率漸化式を立てます。
n 個のさいころの目の和が4の倍数になるというのは、以下の場合です。
・(n-1) 個のさいころの目の和が4の倍数で、
さらにそこからもう1個ふったさいころが「4」のとき。
・(n-1) 個のさいころの目の和が4で割って余り1の数で、
さらにそこからもう1個ふったさいころが「3」のとき。
・(n-1) 個のさいころの目の和が4で割って余り2の数で、
さらにそこからもう1個ふったさいころが「2」または「6」のとき。
・(n-1) 個のさいころの目の和が4で割って余り3の数で、
さらにそこからもう1個ふったさいころが「1」または「5」のとき。

したがって、a(n)は次のように表すことができます。
a(n) = (1/6)×a(n-1) + (1/6)×b(n-1) + (2/6)×c(n-1) + (2/6)×d(n-1) ... ①

同様に、b(n),c(n),d(n) は次のように表せます。
b(n) = (2/6)×a(n-1) + (1/6)×b(n-1) + (1/6)×c(n-1) + (2/6)×d(n-1) ... ②
c(n) = (2/6)×a(n-1) + (2/6)×b(n-1) + (1/6)×c(n-1) + (1/6)×d(n-1) ... ③
d(n) = (1/6)×a(n-1) + (2/6)×b(n-1) + (2/6)×c(n-1) + (1/6)×d(n-1) ... ④

ところで、確率の性質から、
a(n)+b(n)+c(n)+d(n) = 1 ... ⑤
は明らかです。
また、①-②+③-④ を計算すると、
a(n)-b(n)+c(n)-d(n) = 0 ... ⑥
となることが分かります。
よって、⑤+⑥ を2で割って、
a(n)+c(n) = 1/2 ... ⑦
が得られます。

①+i×②-③-i×④ を計算すると、( i は虚数単位。)
a(n)+i×b(n)-c(n)-i×d(n) = -(1-i)/6 × ( a(n-1)+i×b(n-1)-c(n-1)-i×d(n-1) )
よって、数列 {a(n)+i×b(n)-c(n)-i×d(n)} は、
初項 a①+i×b①-c①-i×d① = 1/6+i×2/6-2/6-i×1/6 = -(1-i)/6
公比 -(1-i)/6 の等比数列となることが分かります。よって、
a(n)+i×b(n)-c(n)-i×d(n) = { -(1-i)/6 }n
が得られます。

さらに、
a(n)+i×b(n)-c(n)-i×d(n)
= { -(1-i)/6 }n
= (-√2/6)n × { cos(-45)+i×sin(-45) }n
= (-√2/6)n × { cos(-45n)+i×sin(-45n) } ... ⑧
最後の1行は、ドモアブルの法則を使っています。

同様に、 ①-i×②-③+i×④ を計算することで、
a(n)-i×b(n)-c(n)+i×d(n) = -(1+i)/6 × ( a(n-1)-i×b(n-1)-c(n-1)+i×d(n-1) )
が得られます。よって、
a(n)-i×b(n)-c(n)+i×d(n)
= { -(1+i)/6 }n
= (-√2/6)n × {cos(45n)+i×sin(45n)} ... ⑨

⑧+⑨ を2で割って、
a(n)-c(n) = (-√2/6)n × cos(45n)

この式と、⑦より、
a(n) = 1/4 + (1/2)×(-√2/6)n × cos(45n) ... (答)

これが答えです。


--------------------------------------------------------------
ちなみに、行列を用いて、
①②③④は、次のように書くことができます。
|a(n)|  | (1/6) (1/6) (2/6) (2/6) | |a(n-1)|
|b(n)| = | (2/6) (1/6) (1/6) (2/6) | |b(n-1)|
|c(n)|  | (2/6) (2/6) (1/6) (1/6) | |c(n-1)|
|d(n)|  | (1/6) (2/6) (2/6) (1/6) | |d(n-1)|
この4×4の行列に対し、固有値を求めると、
1, 0, -(1-i)/6, -(1+i)/6
が得られます。それぞれの固有値に対応する固有ベクトルは、
(1, 1, 1, 1), (1, -1, 1,-1), (1, i, -1, -i), (1, -i, -1, i)
となります。
上記の解説で出てきた、
①-②+③-④ や、①+i×②-③-i×④ や ①-i×②-③+i×④ といった計算は、
この固有ベクトルから導いたものです。
Aを行列、λを固有値、uを固有ベクトルとすると、
Au = λu
となるからです。

2005年01月09日

最高によく当たる占い?

 読んだ本からの抜き書き。

人はなぜエセ科学に騙されるのか」(著:カール・セーガン、訳:青木馨、出版:新潮文庫)から。

 今回紹介するのは、世にいる占い師や超能力者と呼ばれる人たちが、共通して持っている、とある商売道具について。
 それは「コールドリード」などと呼ばれたりする、非常に巧みな言葉のテクニックです。

 あなたが、ある占い師に性格判定をしてもらっている状況を想定します。
 コールドリードの技術を磨いた占い師は、例えばあなたに対してこのような判定結果を伝えるわけです。以下引用。

---------------------------------------------------
 「あなたは外交的で、愛想がよく、社交的になることもありますが、ときには内向的で用心深く、控えめになりますね。自分のことをあまり他人に知られるのは、賢明なことではないと思っています。多少の変化や多様性を好み、枠にはまっていることに満足できません。外ではよく規律を守り、自分を押さえることができますが、おおむねそこはカバーできています。あなたには、まだうまく使えていない才能がたくさん眠っているようです。自分に対して批判的になりがちですね。そのくせ、他人に好かれたい、誉めてほしいという気持ちが強いようです。」
---------------------------------------------------

 もうこれはお見事と言いたくなるような表現です。
 こんなふうに言われたら、誰が聞いても当たってると思ってしまうはず。
 ポイントは、抽象的な言い回しに終始し、正反対の内容を巧みに取り入れているということでしょうか。

 最近は占星術や運勢診断など、色々なタイプの占いを目にすることが多いです。
 もちろん占い師の中には、お客さんの態度や言葉遣いを注意深く観察して、その人にふさわしい答えを用意してくる占い師もいるでしょう。
 けれども結局のところ、こういった占いが提供するお告げとは、本質的には上のような「誰にでも当てはまる抽象的表現」に、神秘性や歯切れの良さといったカモフラージュを施したものに過ぎないのではないでしょうか?

 ちなみに今回の引用は、上記の本の極めて一部分を抜き出したものです。
 上下巻合わせて全部で800ページほどある大変ボリュームたっぷりな本なのですが、僕が絶対に読む価値アリだと思っている本の一つです。
 本書のポイントを抜き出せと言われると、恐らくは非常に大量の箇所を引用してしまうことになるでしょう。
 この本において著者は、オカルトや占星術等といった非科学的な思考や、科学の皮をかぶったエセ科学の風潮を取り上げ、人々がこれらに魅了され信じ込んでしまっている現在の状況について警告しており、その上で、不思議さに驚嘆する心と懐疑的精神とをバランスよく持つことが重要である、と説いています。
 今回の引用箇所は、単に僕が読んでいて笑えたという理由のみで挙げているので、これがこの本の代表的な内容であるとは思わないのが正解です。。。

2005年01月12日

日経サイエンスの懸賞パズルに挑む(1)

 日経サイエンスにて、創刊400号特別企画ということでこんな懸賞パズルをやってました。
 なんとなく面白そうだったので、コンピュータの力を借りて取り組んでみることにしましょう。

http://www.nikkei-bookdirect.com/science/page/magazine/puzzle/puzzle0502/question.html

 1から9までの数字を使った、算数のパズルです。
 今回出題されたのは全部で3問。
 問題の詳しいルールはリンク先を参照なのですが、一応ここでも簡単に引用します。

【問1】
□1□2□3□4□5□6□7□8□9□
の□に四則の演算子(+,-,×,÷)や空白、カッコの記号を入れて、答えが400になるようにして下さい。

 小町算と呼ばれる問題だそうです。ちなみに、
解答例:1×2÷3×4×5× (6+7+8+9) = 400
 だそう。他にもいろいろ正解のパターンはあるので「面白い例を見つけて下さい。」とのこと。

 まあたぶん適当に記号を当てはめていったら正解が見つかるのでしょう。
 あまり興味が湧かなかったので、パスして問2に挑戦。

 今度は,1から9までの数字が現れる順番にはこだわらず,数式の長さ・短さを競って下さい。四則に限らず,三角関数,対数関数,微分積分,ベクトルや行列,順列など高校程度の数学で使われるものならなんでもよいとします。数字はそれぞれ1回しか使えませんが,定数(π,e,iなど)は何度でも使えます。
【問2】
 できるだけ短い数式を作って下さい。
解答例: (4×5)^2×1^36789 = 400
【問3】
 できるだけ長い数式を作って下さい。
解答例: sin (3!×5°) ×|2+6×i|^4÷ (18-9-7) = 400
(iは虚数単位。||は絶対値記号。)

 注釈によると、式の長さは演算の個数で決めるのだそうです。
 つまり問2の解答例だと、乗算とべき乗が2回ずつ行われているので、長さは4となります。
 (カッコや定数、数字は数えない。べき乗演算や行列演算,定積分も1個と数える。)
 問3の解答例は、長さが11となります。
 以上をもとに、これらの解答例よりも優れた解答を作ってね、というのが問題です。

 直感的に問2の方が易しそうです。こっちから考えることに。

 ていうかこの問2、解答例の長さ4でもずいぶん短いじゃないか。
 それ以下の長さといえば、あとは1か2か3の場合だけ。
 長さ1の数式なんて、演算が1回しか使えないわけで、これはちょっと無理がありそう。

 というわけで、長さ2で何かよいのないのかな・・・と考えてるときに、ふっと気付きました。
 「ガウス記号使えばいけるんじゃないか?」
 そんな思い付きを元に試しにプログラムを組んでみたところ、出るわ出るわ、どっさり解答例が見つかりました。

長さ2の解答:[384527÷961] = 400
([...]はガウス記号。記号内の数を超えない最大の整数。)

 こんな感じのが、[6桁÷3桁]の場合だけでも数百パターン見つかりました。

 うーむ、でもやっぱり、これじゃ面白くない。
 そもそもガウス記号っていうのが何だかダサい。
 もうちょっときれいな解答か、あるいはいっそ長さ1の解答なんてのがないかな? と言う気がします。
 そうしたら再び、ある思いつきに襲われました。
 「3×3行列の行列式なんてどうだろう?」
 さすがにそんな都合のいいことはないかな、と思いつつも再びプログラムを組んでみたところ、なんとびっくり、見つかっちゃいました。
 
長さ1の解答:  |148|
         det |926| = 400
           |573|

 非常にシンプルな形で、かなり気に入りました。(行列式は大学1年の範囲だけど。)

 実はこれ以外に、行列を使わない長さ1の解答を思いつきました。
 非常にユニークで最高のネタなので、懸賞の募集締切が過ぎるまで秘蔵っ子ということにしておきましょう。
 ていうか、募集締切は1月20日。もうすぐなんですね・・・。(この問題を知ったのは昨日。)
 明日以降、問1と問3を考えてみようと思います。

2005年01月13日

日経サイエンスの懸賞パズルに挑む(2)

 前回の日記に引き続き、日経サイエンス400号記念の懸賞問題にチャレンジ中。
 
http://www.nikkei-bookdirect.com/science/page/magazine/puzzle/puzzle0502/question.html
 
 前回でまだ答えを出していなかった問1と問3のうち、とりあえず問1だけ先に解いておきましょう。
 
【問1】
 □1□2□3□4□5□6□7□8□9□
の□に四則の演算子(+,-,×,÷)や空白、カッコの記号を入れて、答えが400になるようにして下さい。
 いろいろ正解のパターンはあるので面白い例を見つけて下さい。

 □に入れて良いのは、四則の演算子の他に空白もOKですので、例えば「1□2」を「12」としても良いわけです。
 あまりこの問題に興味が湧かない上に、何よりも今回は問3の方が圧倒的に厄介なので、この問1は情熱なくあっさりと終らせる方向でやります。
 とにかく作業量を減らしたいので、□の中に空白は用いず、4つの演算子を総当りで当てはめて答えを探しましょう。
 さらに乗除を加減に優先させるのが面倒なので、左から順に演算をしていくやり方で答えを探します。要はサボり過ぎということです。
 というわけであっさりと答えが見つかりました。

((1+2)×3+4)×5×6-7+8+9 = 400

 というわけで、何の面白みも感じられない答えの完成です。
 よほど他に奇抜で面白いアイデアが浮かばない限り、ひとまずこの答えで確定でしょう。

 さて、厄介なのは問3ですね・・・。
 
【問3】
 今度は,1から9までの数字が現れる順番にはこだわらず,数式の長さ・短さを競って下さい。四則に限らず,三角関数,微分積分,順列など高校程度の数学で使われるものならなんでもよいとします。数字はそれぞれ1回しか使えませんが,定数(π,e,iなど)は何度でも使えます。
 できるだけ長い数式を作って下さい。

 食事の間にぼんやりと考えてみたものの、さすがにパッとひらめくようなアイデアは出てきません。
 明日以降に、のんびり時間をかけて考えることにします。

2005年01月15日

日経サイエンスの懸賞パズルに挑む(3)

 日経サイエンス400号記念の懸賞問題にチャレンジ中。
 
http://www.nikkei-bookdirect.com/science/page/magazine/puzzle/puzzle0502/question.html

 最終問題の問3に取り掛かっています。
 会社の同僚に話してみたところ、結構多くの人が乗って聞いてくれました。
 
【問3】
 今度は,1から9までの数字が現れる順番にはこだわらず,数式の長さ・短さを競って下さい。四則に限らず,三角関数,微分積分,順列など高校程度の数学で使われるものならなんでもよいとします。数字はそれぞれ1回しか使えませんが,定数(π,e,iなど)は何度でも使えます。
 できるだけ長い数式を作って下さい。

 注釈に書いてありますが、「いくらでも式をのばせるような仕組み」を使うことは禁止だそうです。
 つまり、例えば「×π÷π」を何回も続けて書くというのはダメなわけです。
 他にも、「log(exp(3))」や「sin(3-2-1)」といったふうな表現も禁止。

 さて、どんな演算を使ってもOKなどと言われると、かえって何をすればよいか、途方に暮れてしまいます。
 指数関数もOKとありますが、果たしてこれを使ったところでどうやって整数の答えが出せるというのか。
 ・・・そこで、問2のときにも使った、ガウス記号をここでも使ってみようという発想に至ります。
 そもそも、小数→整数に直せるというガウス記号は、はっきり言って最強の演算ではないかと思えるわけです。
 三角関数や指数関数を使ってぐちゃぐちゃの小数になったところで、ガウス記号で整数化すれば良いのですから。
 一番の問題は、数学的な美的センスに著しく欠けていることでしょうか。
 しかしそれでも、果たして実際に400を作ることができるかどうか、試してみたくなりました。

 というわけで、1~9の各数字に三角関数や指数関数を12回演算し、そのガウス記号を取ったものの和で400を表現するよう、プログラムを作ってみました。
 そして、その結果出てきた答がこれ。

 [exp(exp(exp(sin(sin(cos(exp(exp(exp(cos(sin(sin(1))))))))))))]
+ [exp(exp(exp(sin(sin(cos(exp(exp(cos(cos(exp(cos(2))))))))))))]
+ [exp(exp(exp(cos(exp(exp(exp(cos(sin(exp(sin(exp(3))))))))))))]
+ [exp(exp(exp(sin(sin(exp(exp(cos(sin(sin(cos(exp(4))))))))))))]
+ [exp(exp(exp(sin(exp(exp(exp(exp(sin(exp(sin(exp(5))))))))))))]
+ [exp(exp(exp(sin(cos(exp(sin(exp(exp(cos(exp(exp(6))))))))))))]
+ ...
+ [exp(exp(exp(sin(sin(exp(exp(cos(sin(sin(sin(exp(9))))))))))))]

= [44.357397] + [45.683404] + [44.440939] + [44.990710] + [45.636213]
+ [44.941717] + [45.504981] + [45.694271] + [44.183854]

= 44 + 45 + 44 + 44 + 45 + 44 + 45 + 45 + 44

= 400
([...]は、カッコ内の数を超えない最大の整数)

 完成した答えを見て、思わず笑ってしまいそうになりました。
 演算回数は合計125回。
 数学的な美的観点から見れば、この上なくひどい、興醒めな解答であることは間違いないと思います。

 気になる点が一つ。
 このやり方は、いくらでも式をのばせる仕組みを禁止するルールに違反する、との指摘を受ける可能性があるということです。
 今回は各数字の演算回数を12回に限定して探索を行いましたが、原理的には12回どころか、15回でも18回でもいくらでも増やして探索することが可能だからです。
 しかし、そのような指摘には、次のような反論が可能であることにも気が付きました。
 本当に「いくらでものばせる」ことを証明することができますか?
 この解答で本当に投稿するかどうか、一度保留しようと思います。

2005年01月18日

眠りについて、思い付いた2つのこと。

 眠るということについて、思いついたこと2編。

 眠りに関連して、歴史上最も有名な人物と言えば、多くの人はナポレオンを挙げるだろう。
 聞くところによると、彼は一日にたったの3時間しか眠らなかったのだそうだ。

 これはちょっと前に知ったのだけれども、眠りに関しては、アインシュタインも同じぐらい有名であるらしい。
 彼はナポレオンとは逆で、一日に10時間も眠っていたのだそうだ。

 僕は、ナポレオンやアインシュタインのような眠りの特徴を持った人は、世の中には非常に稀であると思っていたのだけれども、どうやらそうではないらしい。
 現代の医学知識によると、ナポレオンのような睡眠の体質を持った人は専門用語でショートスリーパーと呼ばれ、一方、アインシュタインのような体質の人はロングスリーパーと呼ばれるのだそうだ。
 どちらのタイプも、それぞれ全人口の5~10%ほどの割合で存在するということである。

 この知識が僕たちに教えてくれるのは、結局、人間に必要な睡眠時間とは個人個人で差があるものだということ。
 そして、自分にとって最適な睡眠時間を認識し、うまく管理するのが好ましいということだ。

 そのはずなのに、休日の寒い朝、ベッドの中にいるときに自分の頭に思い浮かんでくるのは、ナポレオンではなく、アインシュタインである場合がほとんど。
 なんというか、困ったことだ。

 一日に必要な睡眠時間は、同じ人間でも年齢によって違うのだそう。
 小さい頃にそんな話を聞いたことがあるのを思い出した。

 気になったのでちょっと調べてみると、平均して、
新生児は、13~17時間
2歳で、9~13時間
10歳で、10~11時間
16歳~65歳で、6~9時間
65歳以上で、6~8時間
の睡眠が一日あたりに要求されるらしい。

 歳をとればとるほど、必要な睡眠時間は少なくて済む。
 そんなわけだから、僕たちが中学生や高校生のときは、多くの人が競って自分の睡眠時間の短さを自慢していた。
 睡眠時間が短いということは、それだけ自分が大人に近いということであって、つまりは成長した自分の証しだった。

 ・・・と、そんなことを最近思い出して、そこでふと気付いた。
 成長すればするほど眠る時間が短くて済むっていうけれども、それって実は、頭の働いていない時間がそれだけ長くなったということなんじゃないか。
 何も考えずにただぼんやりと、電車を待ってる時間や道を歩いている時間。
 そんなふうに頭を使わない時間が多いなら、夜に長い間休ませる必要もないわけだ。
 そういえば、小学生くらいのときの自分って、四六時中、何かを考えていたり周りに興味を持っていたりしてたんじゃなかったっけ。

 つまりは、成長したと見せかけて、実は上手な頭のサボらせ方を身に付けたに過ぎないんじゃないかな。

2005年01月22日

時間を買う? 時間を売る?

 このブログで、就職活動・新社会人のジャンルに登録しておきながら、会社の話題をちいとも出さないのは変な気がしてきたので、住まいの話でも。

 僕は現在、会社の社員寮で生活しています。
 いわゆる独身寮といわれる施設です。
 おそらく世間のイメージでは、独身寮と言えば、例えば風呂トイレは共同、朝は食堂で食事、というような生活を想像される方が多いかもしれません。
 ですが、僕の済んでいるところはそういう感じのところではなく、どちらかかというとワンルームマンションに近い感じです。
 キッチンと乾燥機は共同ですが、各部屋にユニットバスと洗濯機が備わっています。
 もちろん食事は自分で用意しないといけません。
 さすがに、寮費は一ヶ月に数千円というわけではなく、それなりの金額を支払ってはいるのですが、それでも会社の施設だけあって非常にお安く、快適に生活することができます。

 と、こういった感じの寮なのですが、同期たちの間では、一つ不満に思っている点があります。
 それは、職場までの通勤時間が長いと言うこと。
 会社の寮であるにも関わらず、職場まで乗換えを含め片道1時間20分ほどかかってしまうのです。
 別の会社に勤めている大学の友人の話を聞くと、たいていの場合、寮から職場まで数十分、というケースがほとんどです。
 結局、往復すると一日あたり3時間弱の時間を通勤に費やしている計算になります。

 そこで最近、僕の同僚の人でも多いのが、寮を退寮して職場の近くにマンションを借りて済む人。
 実は僕の所属しているチームの先輩もその一人で、彼は職場から徒歩20分の場所に住んでいます。
 彼は現在の自分の生活をこう言います。
 
「たしかに寮の方が安くて生活も快適なんだけれどもね。いちおう会社から住宅補助のお金は出してもらえて、それを含めて計算すると、寮のときと比べて一ヶ月に3~4万円ほど多く支出していることになるかな。けれどもその分、通勤時間は前と比べて往復で2時間ほど短くなっているよ。結局は、一日あたり2時間の自分の自由時間を、その金額で買っているということだね。」

 逆の立場から見れば、今の寮での生活は、一日あたり2時間の自分の自由時間を売って、現金を手にしていることになるでしょうか。
 ふいに昔どこかで聞いた、「学生は自分の時間を売って現金を得る。社会人は現金を支払って自分の時間を買う。」というフレーズを思い出しました。

 きっとこれって人によって大きく意見の分かれる問題ですよね。
 自分が同じ立場なら、さてどちらの選択肢をとるでしょう?

2005年01月23日

日経サイエンスの懸賞パズルに挑む(4)(完結)

 このブログでこれまで3回にかけて、日経サイエンスで募集していた懸賞パズルへの挑戦の過程を書いてきました。
 この前の木曜日をもって募集の締切が過ぎたことですので、今回の最終的な応募作品を紹介することにいたします。
 もう一度、問題を引用。

【問1】
 □1□2□3□4□5□6□7□8□9□
の□に四則の演算子(+,-,×,÷)や空白、カッコの記号を入れて、答えが400になるようにして下さい。

【問2】
 今度は,1から9までの数字が現れる順番にはこだわらず,数式の長さ・短さを競って下さい。四則に限らず,三角関数,対数関数,微分積分,ベクトルや行列,順列など高校程度の数学で使われるものならなんでもよいとします。数字はそれぞれ1回しか使えませんが,定数(π,e,iなど)は何度でも使えます。
 できるだけ短い数式を作って下さい。

【問3】
 同様に、できるだけ長い数式を作って下さい。ただし、いくらでも式を長くできるような仕組みを使うことは禁止です。(例:「×π÷π」を何回も書く。)

 前回までの段階で、一応の一通りの解答は出揃っていたのですが、もうちょっと良質の解答を検討し直そう、という話になっていました。
 けれども、残念なことにそれからというものは新しい解答を考える気分がさっぱり抜けてしまい、結局はこのままの解答で応募することとなりました。
 問1、問3の解答は前回の日記をご覧いただくとして、今回非常に自信があるのは問2の解答。
 1~9の数字を1回ずつ使って、できるだけ少ない演算回数で400を作れという問題ですね。
 出来上がった答えはこれ。
 
 928715 mod 463 = 400
 (ただし、A mod B は、A を B で割った余り。)

 余り演算を1回というシンプルさだけでなく、さらに実はこれ、商が2005になっているというオマケ付きです。
 問1、問3はさておき、この問2だけでも本書で紹介されないかなあ・・・と淡い期待を抱く次第です。

2005年01月27日

詩。むしろなぞなぞ。

~~~~~~~~~~~~~~~~~~

T に、1を足すと、音が聞こえる。

G に、1を足すと、去ってしまって。

L に、1を足すと、独りぼっち。

N に、1を足すと、何もない。

だったら、
B に、1を足すと、何になるというのか?

~~~~~~~~~~~~~~~~~~


 ・・・というなぞなぞを、今日の午前に思いつきました。
 答が分かった、という方がいらっしゃいましたら、ぜひコメント欄にどうぞ。

 勤務時間中に何を考えているんだ、という突っ込みは、残念ながら受け付けておりません。

2005年01月29日

未だに理解していない、確率のパラドックス

 確率に関連して、未だに僕がさっぱり理解してなくて、非常にもやもやしている問題があるのです。
 ひとまずは前振りとして次の問題を考えてみて下さい。
 
【問題】
 あるゲームをやりましょう。
 あなたは、このゲームに参加するために、参加料を支払わなければなりません。

 あなたはゲームに参加すると、サイコロを1回振ることができます。
 そして、サイコロを振って出た目の金額を、賞金として手に入れることができます。
 例えば、1の目が出れば、1円の賞金をもらえるというルールです。
 
 さて、あなたはこのゲームに対して、どの位の参加料だったら挑戦しようと思いますか?

 
 
 おそらく、高校の数学で確率について習ったことがある人は、たいていの場合、
 「3円以下だったら参加する。」
 と答えるのではないでしょうか。
 
 なぜそう答えるかと言えば、頭の中で期待値を計算したからでしょう。
 
 期待値とは、賞金の平均値にあたる数のことで、これだけの金額はもらえるだろう、と期待できる数を表します。
 期待値の導出のしかたは簡単で、このゲームで起こり得る結果の全てに対して、
 (もらえる賞金)×(その結果の起こる確率)
 の積を計算します。そして、その数字を全て足し算したものが、期待値となります。

 この場合だと、各結果についての(賞金)×(確率)の積は、
 
 --------------------------------
 賞金 |  1  2  3  4  5  6
 確率 | 1/6 1/6 1/6 1/6 1/6 1/6
  積  | 1/6 2/6 3/6 4/6 5/6 6/6
 --------------------------------

 そしてその数字を足し算したものは、
  1/6 + 2/6 + 3/6 + 4/6 + 5/6 + 6/6 = 3.5 円
 となります。
 ですから、これよりも参加費が少なければ、結果として儲けが期待できるというわけです。


さて、以上を踏まえて、次の問題。

【問題】
 今度は、別のゲームをやります。
 先ほどと同様、あなたはこのゲームに参加するために、参加料を支払わないといけません。

 あなたはゲームに参加すると、コインを1回投げることができます。
 もし裏が出たなら、そこでゲームオーバーです。
 もし表が出たなら、あなたはもう1回、コインを投げることができます。
 もう一度投げて、裏が出ればゲームオーバーですが、表が出れば、またもう1回、コインを投げることができます。
 以後、コインの表が続ける限り、何回でもコインを投げることができます。
 裏が出たら、その場でゲームオーバーとなります。

 ゲームオーバーになったら、それまでにコインを投げた回数に応じて、賞金がもらえます。
 コインを投げた回数が1回のとき、つまり、いきなり裏が出てゲームオーバーになった場合は、賞金は1円です。
 コインを投げた回数が2回、つまり、1回目に表が出たものの2回目で裏が出てゲームオーバーになった場合は、賞金は2円です。
 コインを投げた回数が3回なら、賞金は4円。
 コインを投げた回数が4回なら、賞金は8円。
 以後、賞金は2倍で増えていきます。
 つまり、コインを投げた回数をN回とすると、2のN-1乗の金額をもらえるというわけです。

 さて、あなたはこのゲームに対して、どの位の参加料だったら挑戦しますか?


 この問題、さっきと同じようにして期待値を求めれば、答が得られると思うのです。
 そう思って、賞金と確率の積の表を作ってみるのですが。
 
 --------------------------------------------
 賞金 |  1   2   4   8   16   32 ...
 確率 | 1/2 1/4 1/8 1/16 1/32 1/64 ...
  積  | 1/2 1/2 1/2  1/2  1/2  1/2 ...
 --------------------------------------------
 
 どの縦の列を見ても、賞金と確率の積が 1/2 になっているのです。
 このゲームのルールでは、表が出る限り、何回でもコインを投げて構わないことになっています。
 ですからこの表は、右に果てしなく続いていくと言えます。
 ずっと 1/2 が続くことになるのです。
 したがって、期待値は、
 
 1/2 + 1/2 + 1/2 + 1/2 + 1/2 + 1/2 + ... = 無限大!
 
 ・・・ということは。
 このゲームは、いくら参加料を支払ってでも、挑戦する価値があると言えてしまうのです。
 仮に参加料が1万円や1億円だったとしても、それよりもずっと大きな賞金がもらえることが期待できるのです。

 ですが、これは明らかに、僕たちの直観と全く相容れない結果です。
 実際にコインを何回か投げてみても分かるのですが、表が連続して出るのは、せいぜい1回か2回といったところ。
 下手をすると、いきなり裏が出てゲームオーバーです。
 1万円を支払ってこのゲームに参加しようとは、とても思えません。
 
 さて、この逆説を、どう説明するか?
 

 これは、大学のときに、講義の中でちらりと出てきた話題です。
 一般には、「ペテルスブルグのパラドックス」として知られているそうです。
 この話題を扱った本を以前に読んだのですが、その本では、賞金の対数を満足度と定義する、という説明だったと思うのですが(忘れてしまいました)、納得の範疇をすっかりと超えてしまう内容でした。

 現在もなお、頭の中がもやもやしている問題です。

2005年02月03日

作文でハマるとき、プログラミングでハマるとき。

 ・・・意外と研究所の仕事って、文章を書く機会が多いなあ。
 
 入社してから以後、こんな感想を持つようになってきました。
 
 大学生やっていた頃は、文章と言えばせいぜい講義のレポートや卒論・修論などを書くぐらいでした。

 現在の生活では、毎週末に提出している週報のほか、例えば社内向け報告書、あるいは特許の申請書など、文章を書かなければならない機会がけっこうあるのです。
 というのも、研究所という場所は他の部署と比べて、従業員の客観的な成果評価が難しいという側面があるようです。
 ですから、「報告書を何本書いたか」「特許を何件書いたか」ということが、成果評価の際には重要なポイントとなってくるわけです。

 そういったわけで、現在、ようやく報告書が一本書き終わりました。
 今月以降は特許の執筆作業をやっていくことになりそうです。
 
 さて、一連の執筆作業をやっていて気付くのですが、書いてるうちに、自分は作文が下手なのだなあ、とだんだんと思い知らされてくるのです。
 
 ひとまず頭に浮かんだフレーズをタイプしていって、なんだか意味の分かり難い文だなと思いつつも次に進み、4~5行ほど書いた時点で、前後の文章のまとまりが全然なっていないことに気付き、それではと思いあちらを直してみたものの、今度はこちらの表現が不自然、もう二進も三進もいきようにないので、結局半分ほどデリート。

 ・・・というような感じで、非常にゆっくりとしたペースで進行しています。
 まるで終わりのないもぐら叩きのよう。
 
 そうして、数十時間もの時間を費やして、やっと今回の報告書の完成にたどり着けたわけですが。
 これと似たような苦労を、つい最近にやっていたことを思い出しました。

 それはプログラミングをしているときでした。
 
 ろくにデータの構造やロジックについて検討しないままにコードを書き始め、しばらくするうちに条件分岐が必要なことに気付いて判定用の変数をその場で1コ増やし、またしばらく進めるものの、どうやら状況によって変数がおかしな値をとることを発見し、修正したものの、その結果今度はあちらで間違った処理が行われ・・・と結局、諦めて関数ごとデリート。

 作文の際とほぼ同様な手順を踏んでいることに気が付いてしまいました。

 例えば、おもちゃの積み木遊びをするときに、
 とりあえず面白そうな積み木から順番に組み上げていって、バランスが悪くなったところで、既に積んである他の積み木を直してなんとかするという遊び方。
 あるいは、はじめに漠然とでも全体像を頭に思い浮かべてから、はじめに土台の積み木を並べ、順に2段目3段目を組み上げていく遊び方。
 おそらく、僕の思考経路はこれまで前者のタイプだったのでしょう。
 勝手な推測ですが、おそらくこのタイプは、作文が苦手な人が多いはず(笑)。

 積み木もプログラミングも、これまでは特に意識せずに前者の遊び方でやっていたと思うのですが、今後はもうちょっと土台作りを意識する必要があるみたいです。

2005年02月04日

サイコロの確率と格闘する ~5の倍数編~ (1)

 以前にこのブログで、こんな問題を紹介しました。
 
【問題】
さいころをn個投げたとき、目の和が4の倍数になる確率 a(n) を求めよ。

 このページから引用したものです。
 問題のシンプルさといい、最終的な答を出し終えたときの爽快感といい、僕の中では最高にお気に入りの問題でした。
 解答も非常にキレイな形をしています。
 
  a(n) = 1/4 + (1/2)×(-√2/6)n × cos(45n)
 
 実際の導出の仕方は、この1月5日の記事を参照して下さい。


 さて、最近になって、新しい欲求が生まれてきました。

 次のような問題は果たして解けるのだろうか?
 
【問題】
さいころをn個投げたとき、目の和がkの倍数になる確率 a(k,n) を求めよ。

 このページでも紹介されている問題です。
 さっきの4の倍数の場合を、より一般化させた問題です。
 
 果たして、どんな答が出てくるのか、非常に気になるところです。
 4の倍数になる確率があれだけキレイな形なのだから、ひょっとしたら、一般的なkの倍数になる確率も、同様に非常にシンプルで美しい形をしてるんじゃないか? と思うわけです。
 取り組んでみることにしました。

 とは言ったものの、おそらくこの問題は、大変な難問になることが予想されます。
 そういうわけで今回は、いきなり一般的なkの場合を考えるのは置いておいて、まずk=5の場合から考えてみようとか思います。
 上のページが言うには、k=5のときはやめておいたほうが身のためでしょう、とのことなのですが。
 力の続く限り(そして気の向く限り)、やってみようと思います。
 
 ・・・と言うことで、ひとまず今晩の分の成果。
 
-------------------------------------------------------------

 さいころをn個投げたときの、目の和が5の倍数になる確率を x0(n) とおきます。

 そして、目の和を5で割ったときの余りが1になる確率を x1(n) とおきます。
 同様に、余りが2になる確率、3になる確率、4になる確率を、それぞれ x2(n), x3(n), x4(n) とおきます。
 
 以上5つの確率を列ベクトルで表現したもの:
  t( x0(n), x1(n), x2(n), x3(n), x4(n) )
 を、 x(n) と書きます。
 (表記の都合で横書きですが、列ベクトルです。)
 
 さて、x(n) の漸化式は、行列Aを用いて以下のように書けます。
 
  x(n) = A * x(n-1)
 
 行列Aは、以下で与えられます。
 
     |1/6 1/6 1/6 1/6 2/6|
     |2/6 1/6 1/6 1/6 1/6|
  A = |1/6 2/6 1/6 1/6 1/6|
     |1/6 1/6 2/6 1/6 1/6|
     |1/6 1/6 1/6 2/6 1/6|
 
 上の式の「*」は、行列とベクトルの積を表します。
 
 ひとまず、このAに関して、いろいろ調べてみます。
 この行列の固有多項式を、Maximaを使って計算させました。
 結果、固有多項式 f(x) は、以下のようになります。

  f(x) 
= (1/1296) * ( 1296*x5 - 1080*x4 - 180*x3 - 30*x2 - 5*x - 1 )
= (1/1296) * ( x-1 ) * ( 1296*x4 + 216*x3 + 36*x2 + 6*x + 1 )

 ここで 6*x = y と置き換えると、

  f(x)
= (1/1296) * ( y/6-1 ) * ( y4 + y3 + y2 + y + 1 )

 ・・・おお、来ました来ました。
 この根って、1の5乗根になるんですね。
 
 したがって、Aの固有値は、と、
 
  (1/6) * exp( 2 * j * π * i / 5) ( j は1~4)
 
 の5つとなります。( i は虚数単位。)
 
-------------------------------------------------------------

 むちゃくちゃキレイな形の固有値が出てきました。
 そうそう、大事なことを言い忘れてましたが、基本スタンスは、
 「ややこしそうな計算は機械任せ優先で」
 です(笑)。
 
 続き(がもしあれば)は、次回。

2005年02月06日

サイコロの確率と格闘する ~5の倍数編~ (2)

【問題】
さいころをn個投げたとき、目の和がkの倍数になる確率 a(k,n) を求めよ。

 ・・・という問題を解決するべく、あれこれ格闘しています。
 本日は第2回。

 前回までに、行列A(参照)の固有値 λi (i は0~4)を導出しました。
 
 λ0 = 1
 λj = (1/6) * exp( 2 j π i / 5 ) ( j は1~4)
 
 となります。
 
 さて本日は、これらの固有値に対応する固有ベクトルuj ( j は0~4)を求めてみます。

 λ0 に対応する固有ベクトルが u0 = (1,1,1,1,1) なのはいいとして、他の λ1 から λ4 をどう計算するかが難しいところですね。
 ひとまず、例によってMaximaに丸投げです。
 
 ・・・ですが、そんなにうまくはいきません。
 数式処理ソフトでありがちな、根号が複雑に織り絡まった出力がわらわらと出てくる有様です。
 おそらくはそのまま代数的に計算して固有ベクトルを求めてくれているのでしょう。
 exp 等を使ってスマートな形にまとめる、ということはしないようです。
 だったらどうすれば対応してくれるのかな・・・とマニュアルを読むのですが、結局分からない。
 
 半ば諦めだしてきて、もうダメ元で、そのごちゃごちゃした表現を手計算で整理してみることに。
 そうしたらなんと、意外にキレイな形でまとまってしまいました。
 
1 = ( 1, exp(2πi/5), exp(4πi/4), exp(-4πi/5), exp(-2πi/5) )
2 = ( 1, exp(4πi/5), exp(-2πi/5), exp(2πi/5), exp(-4πi/5) )
3 = ( 1, exp(-4πi/5), exp(2πi/5), exp(-2πi/5), exp(4πi/5) )
4 = ( 1, exp(-2πi/5), exp(-4πi/5), exp(4πi/5), exp(2πi/5) )

 
 固有値同様、これまた非常に美しい形の固有ベクトルですね。。
 続きにもかなり期待が持てます。
 

 
 さて、今後の方針は、数列 { uj ・ x(n) } が公比 λj の等比数列になることから、{ uj ・ x(n) } の一般形を求めて、そこから x(n) を導出して解決! ・・・といきたいところです。
 なのですが、どうやって x(n) に戻すか、というところでたいへん難儀しています。
 進展があれば、また次回。

2005年02月07日

サイコロの確率と格闘する ~5の倍数編~ (3)

 前回、前々回と、「n個のサイコロを投げて出た目の和が5の倍数になる確率」を求めるべく、奮闘しています。

 日曜日の午後をまるまる使って、やっと答を出すことができました。
 
 答えを先に書きます。
 n個のサイコロを投げて、目の和が5の倍数になる確率 x0(n) は、
 
x0(n) = (1/5) + (2/5)×(1/6)×(cos(2πn/5)+cos(4πn/5))
 
 です。あるいは、
 
x0(n) = { (1/5) + (4/5)×(1/6) (nが5で割り切れるとき)
      { (1/5) - (1/5)×(1/6) (上以外のとき)

 と書いても同じです。
 後者の方が分かりやすいですかね。
 
-------------------------------------------------
 
 以下、上記の結果の導出法。(前回からの続き。)
 
 行列A(参照)の固有値を λ 、対応する固有ベクトルを とすると( j は0~4)(参照)、固有値・固有ベクトルの定義より、

 j(n) = λjj(n-1)
 
 とできる。
 つまり、数列 {j(n)} を、初項 j(1) 、公比 λj の等比数列と見なせる。
 したがって、
 
 j(n) = (j(1)) × λjn-1
 
 前回の結果を使って、右辺の部分を計算すると、
 
 (n) = 1
 (n) = (1/6) × exp(2πin/5)
 (n) = (1/6) × exp(4πin/5)   ... (*)
 (n) = (1/6) × exp(-4πin/5)
 (n) = (1/6) × exp(-2πin/5)
 
 上の式の左辺は、ベクトル形式でまとめて書くと、次の行列
 
    |1,       1,       1,       1,       1 |
    |1, exp( 2πi/5), exp( 4πi/5), exp(-4πi/5), exp(-2πi/5) |
P = |1, exp( 4πi/5), exp(-2πi/5), exp( 2πi/5), exp(-4πi/5) |
    |1, exp(-4πi/5), exp( 2πi/5), exp(-2πi/5), exp( 4πi/5) |
    |1, exp(-2πi/5), exp(-4πi/5), exp( 4πi/5), exp( 2πi/5) |
 
 を使って、 P・(n) と書ける。ここで、

           |1,       1,       1,       1,       1 |
           |1, exp(-2πi/5), exp(-4πi/5), exp( 4πi/5), exp( 2πi/5) |
-1 = (1/5)×|1, exp(-4πi/5), exp( 2πi/5), exp(-2πi/5), exp( 4πi/5) |
           |1, exp( 4πi/5), exp(-2πi/5), exp( 2πi/5), exp(-4πi/5) |
           |1, exp( 2πi/5), exp( 4πi/5), exp(-4πi/5), exp(-2πi/5) |

 だから、この P-1 を、ベクトル形式でまとめた(*)式に左から作用させて、(n) を得ることができる。
 第1成分(x0(n))が目的の確率。
 
 x0(n) = (1/5) + (1/5)×(1/6)×(exp(2πin/5)+exp(4πin/5)+exp(-4πin/5)+exp(-2πin/5))
 
 これを整理して、
 
 x0(n) = (1/5) + (2/5)×(1/6)×(cos(2πn/5)+cos(4πn/5))

 を得る。
 
-------------------------------------------------

 出来上がったときは、本当に身体の力が抜けていく感じがしました。
 あー、やっとできた、というような。
 あっさり書いてますが、P-1 の導出あたりでものすごく苦労してます。
 大学のときの数学の知識がけっこう頭から抜けてしまっているので、過程に誤りを含む可能性が非常に高いです。(結果は合ってると思いますが。。。)

 ・・・さて、一般形の場合はどうしましょう。
 やる気が起きれば、また次回。

2005年02月08日

雑メモ2つ

 雑メモ その1
 
 「最強のファイナンス理論」(著:真壁昭夫、出版:講談社現代新書)
 という本が、たいへん面白い。
 現在はまだ、序章を読み終わったばかり。続きがすごく気になります。
 
 この本が取り扱うのは、「行動ファイナンス理論」と呼ばれる理論。
 
 この理論は、ファイナンスの中でも比較的新しい分野にあたり、心理学の知識を使って、金融市場の動向を解析しようとする理論らしい。

 従来から知られている、いわゆる「伝統的ファイナンス理論」は、とある重大な前提を元に理論を組み立てている。
 それは、投資家は常に合理的に行動しており、それゆえに市場は合理的に動いている、ということ。
 ところが、実際の投資家は、人間であるがゆえに、間違いもするし、非合理的な行動をとる。
 そのため、短期的に金融市場では、理屈どおりではない事象や動向がしょっちゅう起こっている。
 伝統的ファイナンス理論では、そういった現象は、すべて例外的であるとして片付けられてしまう。
 
 そこで、行動ファイナンス理論は、伝統的ファイナンス理論の補強剤としての役割を果たす。
 この理論は、経済学と心理学を融合させることによって、人間の非合理性を前提にした、より現実に近いファイナンス理論を構築しているのだそう。

 ちなみに、この理論の礎となる「プロスペクト理論」という理論があるそうだが、この理論を発表したD・カーネマン教授は、2002年のノーベル経済学賞を受賞している。



 雑メモ その2
 
 明確な根拠はないけれど、なんとなく、こう思った。
 あるいは、自己反省も含めて。
 
 「逆説的に言うと」と言ったとき、およそ半分の場合は、
 「逆に言うと」と言った方が適切。
 「逆に言うと」と言ったとき、およそ半分の場合は、
 「別のことを言うと」と言った方が適切。

 
 

2005年02月12日

聖ペテルスブルグのパラドックス(1)

 以前、1月29日の日記で、聖ペテルスブルグのパラドックスを紹介しました。

 この問題に関して、グーグルでいろいろと検索してみました。
 Stanford Encyclopedia of Philosophyこのページで、非常に詳しい解説が載っていることを発見しました。
 ですが、日本語での記事となると、なかなかどうも見当たりません。
 問題の簡単な紹介・説明をしているページや、ファイナンス理論の話題の一つとして軽く触れているページはいくつかあるのですが、上記のページのような、この問題に限定して深く論じたものとなると、どうも英語のページ限定となってしまうようです。

 というわけで、よし、せっかくだし訳してみようか、と思い立ってしまいました。
 
 自分の考えをまとめるのは後回しにして、ただひたすら、粛々と訳し続ける。
 自分の英語能力の無さに、すっかり辟易しながらの作業です。
 ひとまず、前章と第1章の訳を、以下に掲載。
 誤訳・珍訳は覚悟の上。


-------------------------------------------
聖ペテルスブルグのパラドックス

前章

 聖ペテルスブルグのゲームは、一枚の適正なコインを、裏が出るまで投げることによって行われる。賞金は、コインを投げた回数nによって決まり、それは2^nドルに等しい。だから、もし1回目にコインの裏が出たなら、賞金は2^1=2ドルとなり、ゲームは終了である。もし1回目に表が出たなら、もう一度コインを投げる。2回目に裏が出たなら、賞金は2^2=4ドルとなり、ゲームは終了である。表だったらもう一度投げる。後はこの繰り返しである。起こり得る「結果」(表表・・・表表裏)の数は無限にある。コインを投げた回数がn回という結果の確率(「P(n)」とする)は、1を2^nで割ったものであり、それぞれの結果の「期待利得」は、賞金に、その確率をかけたものになる。以下の表は、n=1...10の結果に対する数字を示している。

n 確率    賞金  期待利得
1 1/2    $2    $1
2 1/4    $4    $1
3 1/8    $8    $1
4 1/16    $16   $1
5 1/32    $32   $1
6 1/64    $64   $1
7 1/128   $128   $1
8 1/256   $256   $1
9 1/512   $512   $1
10 1/1024 $1024  $1

このゲームの「期待値」は、全ての結果の期待利得の合計になる。起こり得る各結果の期待利得は1ドルであり、それらは無限にあるのだから、この合計は無限ドルになる。理性的なギャンブラーなら、期待値よりもゲームの参加費の方が小さければ、ゲームに参加する。この聖ペテルスブルグのゲームでは、参加費が有限であるなら、いくらであってもそれはゲームの期待値より小さい。したがって、理性的なギャンブラーなら、参加費がどれだけ大きくともゲームに参加をする。しかし、明らかに、そのような参加料は高すぎて、理性的な人にとって支払えない。多くの解説者は、Hacking(1980)の見積もりに同意している。「ゲームの参加料が25ドルだったとしても、ほとんどの人は支払わないであろう。」 もしこれが正しいのなら、上記の標準的な決定理論の期待値計算に、どこか誤りがあることになる。スイスの18世紀の数学者 Daniel Bernoulli(1738; 英語には1954年に翻訳) によって発見されたこの問題を、聖ペテルスブルグのパラドックスという。

第1章 限界逓減効用
第2章 リスク回避
第3章 効用の上限
第4章 有限個の結果
第5章 無限大の値?
第6章 理論と実践


1.限界逓減効用

 Bernoulli はこの問題に答えるために、次のような観察をした。計算の誤りは、期待されるドルの利得を足していることによって生じているのであり、正しくは、各結果の期待効用を足すべきである。概略を言うと、彼は、金銭には限界逓減効用がある、という広く受け入れられる原理を提案し、金銭の効用の現実的尺度は、金銭の量の対数によって与えられるだろうと主張した。(効用)=log(ドル)とするならば、この賭けの表のはじめの数行は、次のようになる。

n 確率    賞金  効用  期待効用
1 1/2    $2   0.301 0.1505
2 1/4    $4   0.602 0.1505
3 1/8    $8   0.903 0.1129
4 1/16    $16  1.204 0.0753
5 1/32    $32  1.505 0.0470
6 1/64    $64  1.806 0.0282
7 1/128   $128  2.107 0.0165
8 1/256   $256  2.408 0.0094
9 1/512   $512  2.709 0.0053
10 1/1024 $1024 3.010 0.0029

期待効用の和は無限大とはならない。およそ 0.60206 の効用で極限に達する(これは4ドルの価値に相当する)。理性的なギャンブラーなら、4ドル以下の参加料で、賭けに参加するだろう。

 しかしながら、パラドックスへのこのような回答は、不十分である。限界効用逓減を認め、そして、(議論のため、)ドルの対数をとることがドルの効用の妥当な計算法であると認めよう。すると、提案されたように、聖ペテルスブルグのゲームはパラドックスを示さない。しかし、ただ賞金を変えるだけで、容易に、パラドックス持つ聖ペテルスブルグのゲームを作り上げることができる。例えば、n回続いたときに2^nドル支払われるのでなく、10を2^n乗した金額のドルを賞金にしてみよう。このゲームの表は次のようになる。

n 確率    賞金    効用 期待効用
1 1/2    $10^2   2  1
2 1/4    $10^4   4  1
3 1/8    $10^8   8  1
4 1/16    $10^16  16  1
5 1/32    $10^32  32  1
6 1/64    $10^64  64  1
7 1/128   $10^128  128  1
8 1/256   $10^256  256  1
9 1/512   $10^512  512  1
10 1/1024 $10^1024 1024 1

 このバージョンでは、もともとのバージョンよりもずっと大きな賞金を含んでいる。そしてギャンブラーは、推定されるように、もともとのバージョンよりも多くの参加料を、このバージョンでは支払おうとするだろう。しかし、このゲームの期待値(最右列の無限級数の和)は無限大となり、パラドックスが再び発生する。

 もちろん、実際どのようにドルが効用と関連付けされるかは明確ではないが、一般化された、パラドックスを含む聖ペテルスブルグのゲームを次のように考えることができる(Paul Weirich(1984)、Menger(1967))。効用が、ドルまたは他の財貨にどのように変換されようとも、コイン投げがn回続いたときに2^nの効用に相当する賞金を与えることにする。このゲームは無限大の期待値を持つことになり、理性的なギャンブラーは、参加料がどれだけ高額であっても支払うべきである。ここでは話を簡単にするため、この一般化されたバージョンのゲームを無視することにし、もともとのドルの賞金のバージョンについて議論を続ける。しかしながら、ドルの限界逓減効用により、パラドックスを発生させるためには賞金を見直す必要がある、ということは認識しておく。

-------------------------------------------

 ここまでの内容は、日本語のページでも比較的いろいろな場所で見受けることができるようです。
 問題は、第2章以降ですね。。。
 2章の2/3ほどを粗く訳してみたのですが、読んでてさっぱり分かる気がしません;
 忍耐が続いたら、いつか続きを掲載です。

2005年02月18日

ご注文は以上でよろしかったでしょうか

 コミュニケーションということに関して、思いついたことを2つ。

 人から人へ、何かを伝えるときって、どういうことをしているのだろう。
 と、いうことを考えてみたのです。
 大雑把に書いてみると、おおよそ次のような過程を経ているように思います。
 
ステップ1:頭の中に伝えたいものが、漠然としたイメージとして存在する。
ステップ2:頭の辞書を使って、イメージをメッセージに変換する。つまり、言語化する。
ステップ3:メッセージを、声・文章で相手に伝える。
ステップ4:メッセージを受け取った相手は、頭の辞書を使って、メッセージをイメージに変換する。

 基本的な流れは、イメージ⇒メッセージ⇒イメージという流れです。
 この矢印の部分で、頭の中の辞書を使って、次に進むという感じです。
 この辞書は、<イメージ>と<メッセージ(語句)>の翻訳を行う、自分専用の辞書です。
 何か伝えたいことが頭に浮かんだとき、辞書の中を探して、その内容に最もよく一致する語句を見つけ出します。
 そして、そのような語句をつなぎ合わせ、文をつくり、それを相手に投げるという手続きをとります。
 そして相手は、その逆の手順をとり、受け取った文の語句のひとつひとつをイメージに変えていって、最終的にイメージの全体を手に入れるわけです。

 こういうプロセスって、例えばネットワークで映像データを伝送する様子にも似てなくもないように思えます。
 もともとの映像データでは、データサイズの都合のため、そのままではネットワークを通じて相手に送ることはできません。
 そこで、一度、データを別の形式(MPEGとか)に変換してから、ネットワークに流します。
 受け取った相手は、元の形式にデータを変換して、自分の環境で映像を再生することが可能になります。

 なぜ、このような方法で、映像データの伝送が可能になるのか。
 それは、相手と自分の間でお互いに、変換のルールについての詳しい了解があるからにほかなりません。
 MPEGにしても、非常に詳細な変換のルールが規定されていて、両者はその内容を知っているからこそ、映像の伝達が可能になるわけです。
 
 これと同じような原理が、イメージを相手に伝達するときにも働いているのではないでしょうか。
 つまり、相手と自分との間であらかじめ、ある暗黙の了解を交わしているということになります。
 「お互いの辞書で、同じ語句には同じイメージを割り当てておきましょうね」というような。
 こうやって辞書の変換ルールについて了解をしているおかげで、イメージの伝達が可能になっていると言えます。
 
 では、そこでさらに疑問。
 そんな了解を交わした覚えなんてないよ。僕はいつの間にそんなことをしたの?
 仮に了解してたとしても、イメージの辞書なんて、いったいどうやって作ったのよ?

 ・・・イメージの語源を調べてみました。
 
 イメージ(image)という言葉は、ラテン語の「imago」が語源だそうです。
 imagoという言葉には、「映像」「似顔絵」という意味のほかに、「似ること」という意味もあるそうです。
 imitation(模倣する)という言葉と同じ語源ですね。

 イメージとは、他のものに似せるということ。
 つまり、自分の辞書とは、「他人の真似をして、他人に似せようとすること」によって作られるものなんじゃないか。
 
 ちょっとこじ付けかもしれないけれど、ひとまずの考えとしてまとめておくことにします。
 

 「こちらブレンドコーヒーになります。」

 という表現が、このごろよく話題に上がります。
 言葉の話し手(店員)が、聞き手(客)に対して敬意を伝えようとして、つい使いがちになっている表現です。
 ですが、上記の表現は、敬語どころか日本語としてまず成立していません。
 そのために、聞き手は一瞬、違和感を感じてしまいます。
 あるいは、
 
 「ご注文は以上でよろしかったでしょうか?」
 
 という表現も同様ですね。
 
 この頃は、こういったおかしな敬語に対する世間の注目が大きいそうで、つい最近も、この件に関する書籍が出版されたそうです。
 
 ですが、このような傾向を受けて、ちょっと気になっていることがあるのです。
 今の風潮は、「敬語のおかしい人=敬意のおかしい人」というような解釈に、人を陥りやすくしているんじゃないか。
 
 いわゆる「おかしな敬語」の話し手自身は、あくまでも「敬意を伝えたい」と思っているわけです。
 その思いを表そうとした結果、言語として成立していないおかしな敬語が出てきてしまっているのです。
 これは、上で書いた「イメージ⇔メッセージ」のプロセスの図式で言うと、ステップ2の言語化の段階に問題があるということになります。
 頭の中にある敬意というイメージを、敬語というメッセージにうまく変換できていないわけです。
 
 ですから、このようなおかしな敬語を誰かが言ってるのを聞いたとしても、それは単にその人の言語化能力に落ち度があることが明らかになっただけであって、その人の持つ敬意に問題がある、と短絡的に結びつけることは決してできないと思うのです。
 
 いや、だからといっておかしな敬語を使っても構わない、ということには絶対になりませんが。
 実際、僕もすごく気になってしまいますしね。
 ただ、おかしな敬語を話す人を批判するときには、ぜひとも批判するポイントをはっきりさせてから批判すべき、ということなのでしょうかね。

2005年02月20日

聖ペテルスブルグのパラドックス(2)

 以前(2月12日)に紹介した、聖ペテルスブルグのパラドックスについての解説ページ。
 現在、無謀にも、このページの翻訳にチャレンジしています。

 Stanford Encyclopedia of Philosophyこれです。

 前回に前章と第1章を訳し、そして今回、第2章の訳に挑んだわけですが。
 ・・・だんだんと、やめとけばよかった、という気になってきました。
 なんというか、自分で読んで、文脈の意味不明な箇所が多い。
 
 ですが、ここまで来たからには、それなりの形のものを作りたい。
 というわけで、気が付いたときに適時修正を加えていく、という前提で、ひとまずのアップ。

-------------------------------------------

2.リスク回避

 次のような議論を考えよう。聖ペテルスブルグのゲームは、莫大な賞金を得るチャンスを提供している。例えば、表が40回続けば、非常に莫大な1.1兆円という金額が支払われる。もちろん、この賞金が起きるのは稀である。およそ1.1兆回に1回だ。半分の割合で、このゲームではたった2ドルしか支払われず、75%の割合で、4ドル以下の賞金という結果になる。25ドル以上が得られるチャンスは、25回に1回以下である。(25ドルは、Hacking が提案する、リーズナブルな参加料の最大値である。)非常に低い利得しか得られないのがほとんどで、高い利得が得られるというのは非常に稀である。25ドル以上を投資するというのは、愚かしいリスクである。

 この種の推論は魅力的であり、これが説明する直観的な考えは Hacking のそれと一致する。私たちの多くはリスク回避的であり、極めて小さなチャンスで莫大な賞金が得られるとしても、チャンスが小さ過ぎるため、賭けをしようとは思わない。Weirich は、この種の考察が聖ペテルスブルグのパラドックスを解決すると主張する。彼は、リスク回避要因を理性的な計算に取り入れた、複雑な方法を提示し(ここでは立ち入らない)、理性的なゲーム参加料には、ある有限の上限があるという結果を出した。

 しかし、このアプローチには反論がある。1つには、リスク回避要因は、理性的な決定を行う上で、一般的に適用できる考えではない。なぜなら、中にはリスク回避的でない人々もいるからだ。現実にはリスクを楽しむ人々もいる。例えば、州営宝くじを日課として楽しんでいる人々はどう見なすべきなのだろう? あるいは、カジノで純粋なゲームに賭けをする人々は?(これらのゲームでは、期待効用よりも、参加料の方が大きい。)単にそのような振る舞いは理性的でないだけだ、と片付けることも可能だが、時にこれらのプレイヤーは、自分たちはリスクの興奮を楽しんでいるのだ、と説明する。いずれにせよ、聖ペテルスブルグのゲームの理性的な参加料の最大値はかなり小さいと広く感じられているのはなぜか、といった疑問に、リスク回避の考えが説明をしてくれるかどうかは、決して自明ではないのである。一方で同時に、多くの人々が、極めて低い確率でしか大きな賞金は得られないことから生じる、くじの巨大なリスクを回避しないのである。

 しかし、議論のために、聖ペテルスブルグのゲームの適切な参加料は有限で小さいものだという理性的な直観は、リスク回避という考えによるものであると仮定しよう。しかし、こう仮定しても、パラドックスはなくならない。なぜなら、このリスク回避が考慮に入れられるよう、再び賞金を調節することが可能だからである。

 あなたが賭けを好まず、たとえ勝算があったとしても、小さな確率で大きな賞金が得られるようなゲームに、参加料のリスクを冒したくないものとしよう。例えば、1ドルの宝くじ券を提示されて、そのくじは、10分の1のチャンスで20ドルの賞金が得られるものと想像しよう。ゲームへ参加することによって、あなたは効用を失う。あなたはリスクを嫌うからだ。しかし、推定されるように、賞金をやや増加させることで、この効用の損失の埋め合わせをすることができる。おそらく、10分の1のチャンスで100ドル得られるのであれば、あなたは1ドルを投資するだろう。もしそうでないなら、1000ドルはどうだろう。リスク回避に対して、埋め合わせをするのに十分大きな賞金があることは明らかである。

 では、聖ペテルスブルグのゲームに、あなたは参加料として20ドルしか払うつもりがないものとしよう。リスク回避のため、これ以上は払わない。利得が大きくなることから増加するリスクをこれらの効用から差し引くと、その結果として、最右列の数字は、確率が小さくなるにつれ減少していく。そして最右列の和は極限に達する――おそらく25ドルである。しかし今は、各結果に固有のリスクに応じて、賞金の増額によって返金を行うよう、ゲームの再公式化を行うことができる。例えば、より大きな賞金に対するリスクの増加(=確率がより低くなる)への埋め合わせとして、それぞれの賞金額を2乗したとしよう。もしこれがリスク回避にとって十分な埋め合わせでないなら、さらに賞金を高くしてもよい。いずれの場合も、リスク回避の埋め合わせをするのに十分大きい、賞金のスキームが存在するようだ――それぞれの賞金のドル効用からリスク要因を引いたものを、1効用に等しくするというやり方だ。このような、より大きな賞金のあるゲームもまた、パラドックスである。

 しかし Weirich は、数列の和を無限にするようなやり方では、賞金を増やしてもリスク回避の十分な埋め合わせとはならない、と主張する。彼は、ある結果に対し賞金を増やすことにより、リスクの恐れ、という意味でのコストが増加すると述べている。宝くじの例だと、賞金を1000ドルまで増やしたとしても、それに対応するように、あなたにとってのリスクが増えることとなり、それゆえあなたは賭けようとしないだろう。提示された賞金がいかに大きくとも、あなたはなお1ドルの券を買おうとはしない。より高い賞金はあなたにとってリスクを高めるからだ。彼が言うには、「面白い言い方をするなら、手の中にいる数羽の鳥が、茂みの中の何羽もの鳥に匹敵する」のである。

 リスク回避がこのように作用すること、あるいは、いずれにせよこの種のリスク回避が理性的として正当化されることを、怪しく思う人もいるかもしれない。賞金が増えるとゲームのリスクが大きくなるなんて、まったく疑わしいことだ。宝くじの例で言うなら、このようなリスク回避のためだけに、どれだけ賞金が高くとも賭けを拒むというのは、病的であって理性的ではない。理性的でリスク回避的な人であれば、誰もが1ドルに見合うとみなすような、十分価値のある賞金(そのようなドル額は普通の小さな効用を持つ)があるに違いない。茂みの中にどんな価値のある鳥がいようとも、手の中の1ドルの価値の鳥のほうがよい、というような人がいれば、そんな人は精神医学の助けが要るだろう。これは理性的な決定戦略ではない。

 しかしながら、リスク回避要因にとって、賞金の増額のような要素が特定のゲームをより魅力的にはするものの、リスク要因を覆すほど十分に魅力的だとは決して言えない、という主張をする人もいるだろう。リスク回避を考慮に入れた上で、ゲームの効用を計算する最も明らかな方法は、そのリスクの負の効用を、まるでそのリスクが賞金の負の面であるかのように、それぞれの賞金の正の効用に足し合わせるという方法である。この計算方法だと、利得の効用を増やすことによって、リスクの埋め合わせをすることが常に可能である。しかし、Weirich の提案は、リスクを、ギャンブル全体と現在のその人の効用レベルとの関数だと見なしている。そうすれば、賞金を増額したところで、リスク回避的な人にとってゲームが好ましいものになることはない。これはどうも疑わしい。もし、ある人のゲームに対するリスク回避には限りがあり、単純に利得の増加によって増えないのであれば、そして、賞金の効用は限りなく増加するのであれば、いくらか賞金を増額させることによって、リスク効用を埋め合わせできることになるだろう(それがどんなに理性的に計算されようとも。)しかし、もし賞金が増加し、さらにゲーム全体の期待効用(リスク要因を無視する)が増加したにも関わらず、それが有限のリスク回避を上回るのに十分でなかったならば、その場合は他の何か(賞金の限界逓減効用や、効用の上限)が作用する。これらの可能性についてはこの記事のほかの場所で議論する。

 しかし聖ペテルスブルグのゲームは、非常に巨大な参加料を正当化するとしている。そのため、宝くじの例は正確には適切でない。高い参加費――例えば、あなたの生涯の蓄え――を持つような例を考えてみよう。どんなギャンブルであっても、常にこのリスクを拒むというのは理性的だろうか? そうではなさそうだ。堅実な銀行に1年間、あなたの生涯の蓄えを預けたなら、あなたは事実上、賭けを受け入れたことになる。非常に高い確率で、年の終わりにあなたは貯蓄を利子付きで戻してもらえる。しかしまた、極めて低い確率で、銀行と預金保険のいずれもが破綻し、一文無しになることもあるのだ。それだけ利子が高く、破滅の確率が低くとも、ほんのわずかのリスクを冒すのを拒むような人がいれば、明らかにそのような人は理性的でない。実際、道路を横断する人は、みな自分の命を賭けているのだ。なぜなら、道路を横断することは、わずかではあるものの、車にひき殺されるというリスクを冒しているからだ。しかし、地上で道路を横断することを拒むような人は、理性的ではない。このようなリスク回避が一般的に適用されれば、誰も身動きが取れなくなるだろう。重要なのは、実際のリスクを考慮に入れ、適切に小さいものを行うことである。

 考えられる対抗する議論は、リスク回避の考え方によって、賞金がいくら高くても小額の参加料を賭けるのを拒んだり、あるいは賞金を得られる確率がいくら高くても高額の参加料を賭けるのを拒んだりするというのであれば、リスク回避は理性的ではないというものだ。しかしこれで聖ペテルスブルグの反論が万事解決するわけではない。ここで私たちが想定しているのは、参加料が高く、賞金が高額になる確率が小さくなるような賭けだからだ。賞金がいくら高額でも理性的にリスクを受け入れられない、ということの最も説得力のある例を出すなら、参加料が高く、賞金が得られそうにもないというような賭けが挙げられるだろう。たとえば、あなたがリスク回避的で、次のような賭けを提示されたとしよう。参加費は、あなたの生涯の蓄え10万ドル(たとえば)で、賞金の得られるチャンスは100万回に1回である。どれだけ賞金が莫大であっても、賭けを拒むのが理性的だろう。なぜそうなのかは考察に値する。

 古典的決定理論によれば、この賭けが理性的であるためには、賞金は非常に甚大なものでなければならない。想定されているケースでは、生涯の蓄えの額の、少なくとも100万倍、つまり1000億ドル以上だ。賞金の増額によりリスク回避の埋め合わせをしようとすれば、賞金はいっそう高額になる。2000億ドルだろうか? 1兆円だろうか? ――莫大すぎて私たちの直観では評価できない。あなたにとって、生涯の蓄えの100万倍以上の価値があるものとは何だろう? 分からないだろう。このような賭けを考えば、あなたの直観は尻込みしてしまうだろう。金銭や家財の限界逓減効用がここでも作用しているのである。そのような大きな効用を与えてくれるものなどない、と考える人もいるかもしれない。しかし、世の中がそのような莫大な効用を持ち合わせていないという事実や、あるいは、これらのことを考える上で直観が当てにならないという事実は、古典的決定理論それ自体にとって難しいことではない。このことに関して、より多くは以下で述べられる。そこでは、この種の実践的な考察であっても古典的決定理論のどこかに誤りがあるとは示されない、という案が議論に出される。

 では、聖ペテルスブルグのゲームにおいて、賞金を増やし、理性的と見込まれたリスク回避的参加者の埋め合わせをしてみよう。ここで再びゲームは、そのような人にとって無限大の期待値を持つ。

-------------------------------------------

 翻訳とは、非常に熱中してしまう反面、自分の英語・日本語能力の乏しさに愕然とさせられる側面を持つ行為なのだと思いました。

2005年02月26日

サイコロの確率と格闘する ~8の倍数編~

 【問題】
さいころをn個投げたとき、目の和がkの倍数になる確率 a(k,n) を求めよ。

 という問題が気になっているので、相変わらず挑戦しています。
 出題元はこのページ
 
 これまでに、kの値が4のときと、5のときの答えを導出することができました。
 (k=4の場合は1月5日の記事、k=5の場合は2月7日の記事を参照。)
 ひとまずこれで、kが1から7までの場合の答えについては、導出が完了したことになります。
 (上記の出題元ページで、k=1、2、3、6、7の場合の答えが紹介されています。)
 
 さて、当初の思惑では、「k=5のときの答えを出すことで、一般的なkの値について何か予測が立てられないだろうか?」という淡い期待を抱いていました。
 そういうわけでk=5の場合の解答をがんばって導き出したにもかかわらず、一般的なkの場合について、未だうまく予測が立てられないでいます。

 というわけで、今回は、k=8の場合について考えました。
 ひょっとしたらこ、これでもうちょっと予測について何か言えるかもしれない、という期待からです。
 
 やっと、答えが出せました。
 以下、導出の過程。
 
---------------------------------------------------

 さいころをn個投げたときの、目の和が8の倍数になる確率を x0(n) とおく。
 そして、目の和を8で割ったときの余りが1になる確率を x1(n) とおく。
 同様に、余りが2になる確率、3になる確率、...、7になる確率を、それぞれ x2(n), x3(n), ... ,x7(n) とおく。
 以上8つの確率を、列ベクトル形式で現したものを、
 
x(n) = t( x0(n), x1(n), ... ,x7(n) )
 
 とする。
 x(n) の漸化式は、行列Aを用いて以下のように書ける。
 
  x(n) = A * x(n-1)
 
 ここでAは以下のような8次の正方行列である。
 
     |  0  0 1/6 1/6 1/6 1/6 1/6 1/6|
     |1/6  0  0 1/6 1/6 1/6 1/6 1/6|
     |1/6 1/6  0  0 1/6 1/6 1/6 1/6|
  A = |1/6 1/6 1/6  0  0 1/6 1/6 1/6|
     |1/6 1/6 1/6 1/6  0  0 1/6 1/6|
     |1/6 1/6 1/6 1/6 1/6  0  0 1/6|
     |1/6 1/6 1/6 1/6 1/6 1/6  0  0|
     |  0 1/6 1/6 1/6 1/6 1/6 1/6  0|

 Aの固有値を λ0, λ1, ... ,λ7 は、Maximaを使って、以下のように得られる。

λ0 = 0
λ1 = (1/6)×(-i/√2 - 1/√2 - 1 )
λ2 = (1/6)×( i - 1 )
λ3 = (1/6)×(-i/√2 + 1/√2 - 1 )
λ4 = 1
λ5 = (1/6)×( i/√2 + 1/√2 - 1 )
λ6 = (1/6)×(-i - 1 )
λ7 = (1/6)×( i/√2 - 1/√2 - 1 )

 そして、それぞれの固有値に対応する固有ベクトル 0, 1, ... ,7 は、以下のようになる。

0 = ( 1, 1, 1, 1, 1, 1, 1, 1 )
1 = ( 1, (i+1)/√2, i, (i-1)/√2, -1, (-i-1)/√2, -i, (-i+1)/√2)
2 = ( 1, i, -1, -i, 1, i, -1, -i )
3 = ( 1, (i-1)/√2, -i, (i+1)/√2, -1, (-i+1)/√2, i, (-i-1)/√2)
4 = ( 1, -1, 1, -1, 1, -1, 1, -1 )
5 = ( 1, (-i-1)/√2, i, (-i+1)/√2, -1, (i+1)/√2, -i, (i-1)/√2)
6 = ( 1, -i, -1, i, 1, -i, -1, i )
7 = ( 1, (-i+1)/√2, -i, (-i-1)/√2, -1, (i-1)/√2, i, (i+1)/√2)
 
 ここで、数列 {jx(n)} ( j は0~7) が、初項 _j ・ (1) 、公比 λj の等比数列と見なせる。
 実際に計算してみると、

jx(n) = λjn

 となることがわかる。(おお、むちゃくちゃきれいだ。)
 つまり、
 
0x(n) = 1
1x(n) = λ1n
2x(n) = λ2n
3x(n) = λ3n   ... (*)
4x(n) = 0
5x(n) = λ5n
6x(n) = λ6n
7x(n) = λ7n
 
 である。
 
 対角化行列Pの逆行列P-1を、(*)式の左から作用させると、x(n) を得ることができる。
 (なお、P、P-1 の具体的な形については、ここでは省略。)
 
 以上の計算をすると、x0(n) は以下のようになる。
 
x0(n) = (1/8)×( 1 + λ1n + λ2n + λ3n + λ5n + λ6n + λ7n )

 λ2n と λ6n の和については、以前にやっているので、それを使って式を簡単にできる。

x0(n) = (1/8) + (1/4)×(-√2/6)n×cos(nπ/4)
    + (1/8)×( λ1n + λ3n + λ5n + λ7n )
 ・・・ (答)

ただし、

λ1 = (1/6)×(-i/√2 - 1/√2 - 1 )
λ3 = (1/6)×(-i/√2 + 1/√2 - 1 )
λ5 = (1/6)×( i/√2 + 1/√2 - 1 )
λ7 = (1/6)×( i/√2 - 1/√2 - 1 )

---------------------------------------------------

 途中の経緯はかなりアヤシイですが、なんとか、おそらく正しいと思われる結果を出すことができました。
 一応、n=6まで、手計算の結果と一致していることを確認してます。
 式の最後の部分が、もうちょっとシンプルな形に整理できるような気がしますが、まあ今回は許容範囲。

 ・・・と、さてここまで来てついに、一つの面白い発見をしてしまいました。
 一般的なkの場合の答えを示唆する内容です。
 しかし、今日はもうこれで疲れてしまったので、続きは次回。

---------------------------------------------------

【追記】
 もうちょっとシンプルな表記で書けることに気づきました。
 λ1, λ3, λ5, λ7 は、次のように書くこともできます。
 
λ1 = (-1/6)×√(2+√2)×( cos( π/8)+isin( π/8) )
λ3 = (-1/6)×√(2-√2)×( cos(3π/8)+isin(3π/8) )
λ5 = (-1/6)×√(2-√2)×( cos(5π/8)+isin(5π/8) )
λ7 = (-1/6)×√(2+√2)×( cos(7π/8)+isin(7π/8) )

 ・・・こっちの方が、何かを暗示している表現ですね(笑)。
 これらを使って、x0(n) を整理すると、

x0(n) = (1/8) + (1/4)×(-√2/6)n×cos(nπ/4)
    + (1/4)×(-√(2+√2)/6)n×cos(nπ/8)
    + (1/4)×(-√(2-√2)/6)n×cos(3nπ/8)

 となります。
 やっと虚数を使わない形で書けましたね。

2005年02月27日

サイコロの確率と格闘する ~一般の場合~(1)

 【問題】
さいころをn個投げたとき、目の和がkの倍数になる確率 a(k,n) を求めよ。

 という問題に取り組んでいます。
 昨日までの段階で、kの値が4、5、8の場合について、答えを導出することができました。
 
 ・・・さて、ここに来て、とある一つの発見をしました。
 一般的なkの値の場合についての発見です。
 kが4、5、8の場合の、答えの導出の過程を見ていて気づきました。
 
 それは、
 
 結果は、固有値のn乗の和を、kで割ったものになっている。
 
 というものです。
 
 したがって、ここから、以下の予想が立てられます。
 
【サイコロの確率に関する予想】
 さいころをn個投げたときの、目の和がkの倍数になる確率 a(k,n) は、確率の遷移を x(n) = A * x(n-1) のように表現したときの、確率行列Aの固有値 λ0, ... ,λkを使って、

a(k,n) = (1/k)×( λ0n + ... + λkn )

と書ける。

 もしこれが本当だとすると、かなり感動ですね。。
 
 はたして、kの値が4、5、8以外の場合についても、上記の予想は当たっているのか?
 チェックしてみました。
 k=2、3、6、7の場合については、比較的容易に答えを出すことができるので、上記の予想から得られる答えと一致しているかどうか見てみます。(参照:出題元

【k=2の場合】
 確率行列は、
 
A = |1/2 1/2|
    |1/2 1/2|

 です。この固有多項式は、(x-1) x です。
 ですから固有値は、λ0 = 1, λ1 = 0 となります。
 よって、
 
a(2,n)
= (1/2)×( λ0n + λ1n )
1/2

 おお、確かに正しい答えが出ています。


【k=3の場合】
 確率行列は、
 
    |1/3 1/3 1/3|
A = |1/3 1/3 1/3|
    |1/3 1/3 1/3|

 固有多項式は、- (x-1) x2 です。
 固有値は、λ0 = 1, λ1 = 0, λ2 = 0 となります。
 λ1, λ2 は重根ですが、別個のものとして扱います。
 (ゼロなのでここでは意味はないです。)
 
a(3,n)
= (1/3)×( λ0n + λ1n + λ2n)
1/3

 k=3の場合もオーケーです。


【k=6の場合】
 確率行列は略。
 固有多項式は、 (x-1) x5 です。
 固有値は、λ0 = 1, λ1 = λ2 = λ3 = λ4 = λ5 = 0 となります。
 よって、

 a(6,n)
= (1/6)×( λ0n + λ1n + λ2n + λ3n + λ4n + λ5n)
1/6

 k=6の場合もオーケー。


【k=7の場合】
 確率行列は、
 
    | 0 1/6 1/6 1/6 1/6 1/6 1/6|
    |1/6  0 1/6 1/6 1/6 1/6 1/6|
    |1/6 1/6  0 1/6 1/6 1/6 1/6|
A = |1/6 1/6 1/6  0 1/6 1/6 1/6|
    |1/6 1/6 1/6 1/6  0 1/6 1/6|
    |1/6 1/6 1/6 1/6 1/6  0 1/6|
    |1/6 1/6 1/6 1/6 1/6 1/6  0|

 固有多項式は、 -( x-1 ) ( x+1/6 )6 です。
 固有値は、λ0 = 1, λ1 = λ2 = λ3 = λ4 = λ5 = λ6 = -1/6 となります。
 よって、

 a(7,n)
= (1/7)×( λ0n + λ1n + λ2n + λ3n + λ4n + λ5n + λ6n)
= (1/7)×( 1+6×(-1/6)n)
(1/7)×( 1-(-1/6)n-1)

 よって、k=7の場合も予想が正しいことが示せました。


 どうやら、kの値が8までの全ての場合について、上記の予想は正しいようです。
 はたしてkが9以上の場合についても、この予想は当たっているのか?
 だとすれば、それは証明可能なのか?
 固有値そのものは、kにどのように依存するのか?
 難問が山積みとなってしまいましたが、ひとまず面白い予想が立てられたので、非常に満足です。

2005年03月06日

聖ペテルスブルグのパラドックス(3)

 英文資料を粛々と訳しつづけるぞシリーズ(笑)の第3回です。
 確率のパラドックスとして知られている「聖ペテルスブルグのパラドックス」。
 なかなか興味深い問題であるにもかかわらず、これを日本語で解説した記事がウェブ上に少ないです。
 そこで少しでもリソースを増やすことに貢献しよう、と思い立ってはじめたシリーズです。
 大義名分は以上で、あるいは、自分の英語能力のトレーニングとして。
 あいかわらず、自分の考えというものがまだちゃんとまとまっていない状況ですが、とにかく機械的に翻訳し続けます。
 今回は第3章。


-------------------------------------------

3.効用の上限

 これまでに提案された2つの再公式化は、いずれも、賞金のドル値が埋め合わせとして増加するという特徴を持っている(第1の場合では、金銭の価値の逓減限界のためであり、第2の例では、そのあり得なさとリスク回避のためである)。いずれの場合も、それぞれの結果の効用は限りなく増加するものと仮定していた。しかし、おそらくこの仮定は正しくなく、賞金の効用には上限がある。その結果、級数の和は極限に達する。Menger は、彼のこの問題の古典的な取り扱いの中で、効用に上限があるという仮定はパラドックスを解決する唯一の方法であると議論する。たとえば、100効用を上限にして、効用=ドル値だと仮定しよう。このゲームの表はこのようになる:

n 確率    賞金 効用  期待効用
1 1/2    $2   2  1
2 1/4    $4   4  1
3 1/8    $8   8  1
4 1/16    $16  16  1
5 1/32    $32  32  1
6 1/64    $64  64  1
7 1/128   $128  100 0.78
8 1/256   $256  100 0.391
9 1/512   $512  100 0.195
10 1/1024 $1024 100 0.098

右側の列の無限級数の和は、およそ 7.56 の極限に達する。理性的な参加料は、7.56 ドル以下のものとなる。

 100ドル以上なら、どんなドル賞金でも最大の効用に達するという仮定は疑わしい。100ドル、1000ドル、100万ドルの価値が、みな同じ――最大の価値ということになるからだ。ドルの最大効用は、もっと高いほうがもっともだろう。ドルの最大効用を1600万に設定すれば、ゲームの理性的な参加料の最大値は25ドル近くになる。この数字は、Hacking が推測する、私たちの直観が受け入れる値である。

 いくらかの人々は、効用に上限を設けることは理性的だと考えている。たとえば、Russell Hardin (1982) は、この仮定を「効用の正当性のための強制」と呼ぶ。William Gustason (1994) は、いかなる結果の価値にも上限があると規定することにより、期待値の概念に制限を加えることを提案している。Richard Jeffrey (1983) も同意している。

 しかし、効用の上限というアイデアは、効用の正当性のための強制だとは見なされないだろう。このアイデアは、金銭の限界逓減効用と区別されなければならないことに注意しよう。理性的に考えて次のことがわかるだろう。もし、(たとえば)1600万ドルが銀行にあったとしたら、おそらく望むものは何でも買うことができるだろう。しかしこのことは、そのような金額によって、許容される最大の効用が与えられると言っているわけではない。すぐに想像がつくことだが、そのような金額を持つ人――あるいはどんな金額であっても――は、お金では買えない、ある種の物を持たないため、なお効用に欠いていることになる。効用の上限というアイデアが意味するのは、ある量の効用が存在し、それは高すぎるため、追加的な効用が不可能――つまり、何を付け加えてもこれ以上の価値を決して増やせない――ということである。あらゆる富を使用できる人を想像してみよう。彼はなお、満たされない願望を持っているだろう。たとえば、彼の友人・親戚が彼と同じくらい幸福であるようにという願いだ。もしこの願いが叶えられたなら、そのときは、彼はなお、見知らぬ人が同じく幸福であるようにと願うだろう。そして、彼の幸福を分け与えるために、現在よりも多くの人が世にいることを願い、そしてより多くの星が幸せな人々で満たされることを願うだろう。より多くとはどのぐらいだろう? 多ければ多いほどいい――限りなく多くだ。もしも効用に上限があるのなら、これが最良だ、というある有限の量の効用が存在し、その量は、他のいかなるものとも引き換えにしたいと思うものである。そのような量が存在するなんて、もっともらしいとは思えない。

 享受可能な効用に上限がある人々がいると想像するかもしれない。ある有限個の願望を持ち、それぞれの願望が、ある有限状態によって完全に満たされるような人々だ。このような人々にとって、賞金の効用は限りなく増加するのではなく、聖ペテルスブルグのゲームは、ある有限の期待効用を持つ。はたしてそのような人々は存在するのだろうか? これは経験にもとづいた疑問である。どんな場合でも、「多ければ多いほどいい」という願望を持つ人々は確かに存在するし、そんな人々はいないとか、価値は無限には増加しないとかいった、経験的で不確かな主張によって理性的な選択理論が制限を加えられるべきではない。そして、このような主張はたしかに、聖ペテルスブルグのパラドックスの解決として機能するには根拠が十分でない。

 Gustason は、「このパラドックスの要点は、もし無限大の値のようなものが存在するのなら、それを含むような行為や結果は、期待値の概念の範囲を超えているということだ」と言っている。Jeffrey は、私たちがここで適用している評価理論は、「そもそも、望ましさが有界だという考えに密接に結びついている」と述べている。しかし、この理論がそのような結果を想定して設定されていないという事実は、この場合の適用を拒もうとするのにちょうど良い理由とはならない。両方の著者が、望ましさに限りのないゲームを除外した主な理由とは、そうしないと、聖ペテルスブルグのゲームが無限の期待効用を持ってしまうからだ。しかし、このアドホック(特別)な論理的根拠は、この結果が耐えられないものでない限り、強制的なものではない。この結果を容認できる可能性は、のちほど考察する。

 Hardin は、効用が有界かどうかは「論理的というよりも事実的な問題」であり、聖ペテルスブルグのパラドックスを解決するためにそれを実施することは、「このパラドックスがアンチノミー(二律背反)ではないと仮定することだ」という意見を提案している。彼が意味するのは、このゲームによって課される困難は、効用が有界でないという事実的な仮定(単に論理的な特徴によらない)に起因するするものであって、この仮定をはずすことによって、この困難は取り除かれるということだ。しかし、もしこのゲームによる困難が見出せないなら、この仮定をはずそうとは思えない。

-------------------------------------------

 コメントをちょこっとだけ。
 僕の直観では、聖ペテルスブルグのパラドックスは、本質的には、無限の概念と無関係のように感じています。
 たとえば、「表が1000回続いたら強制的にゲーム終了」というルールを新たに付け加えたなら、ゲームから無限の概念は消えうせます。
 しかし、ゲームの期待値は1000ドル、非常に高額であり、たとえ100ドルでも参加料として支払いたいとはやはり思えません。
 したがって、この章の、効用の上限というアイデアは、はたしてまともに取り合ってよいものか、疑問のあるところです。
 いや、僕の考察が不十分だ、という結論が今のところの最有力候補ですが。。;

2005年03月13日

聖ペテルスブルグのパラドックス(4-1)

聖ペテルスブルグのパラドックスの解説記事(ここ)の翻訳作業中。
とりあえず、第4章の半分を翻訳。

-------------------------------------------

4.有限個の結果
 
 Gustason は、聖ペテルスブルグの問題を避けるために、次の2つのいずれかの制約を期待値の概念に課すことを提案している。

(a) それぞれの行為は有限個の結果しか持たない。
(b) 値は「有界」でなければならない。つまり、ある数nとmが存在し、結果に割り当てられたどんな値もnを超えたりmを下回ったりしない。

 彼は、いずれかの制約を課せば、聖ペテルスブルグの結果を排除するのに十分だろうと指摘する。この場合、結果の値に上界を定める制約(b)を課さないならば、おそらく制約(a)でうまくいきそうだと分かるだろう。

 制約(a)を課す一つの方法は、単純に聖ペテルスブルグのゲームがこの制約にそぐわないと言い切ることであり、それゆえ、その値や適正な参加料は標準的な期待値理論を用いて計算できない。もし仮にできるとするなら、それはどうやって計算するのか? 25ドルは高すぎるという直観はどこから(もしあるなら)来るのか? それは(可能なら)どのように正当化されるのか?

 もう一つの方法は、ゲームのやり方は前記のように厳密ではなく、可能性はあれども決して発生しないような長い列が存在すると仮定する方法である。つまり、ゲームの期待値を計算するとき、考えられる賞金は有限個しかないということである。推定されるように、これを適用するには、考えられるコインを投げる回数に上限Lを設ける。もし表が続けてL回出たならば、裏がまだ出ていなくてもゲームは終了し、これまでの試行に対して支払いがなされる。Lを25に定めるならば、ゲームの期待値は25ドルになる。これは、理性的な参加者が支払おうとする参加量の最大値である(Hacking の直観)。25回連続の表を切り捨てて清算するという考えを、私たちはおそらく無意識に仮定しているのだろうか?

 多くの著者はこう指摘する。実際的に言えば、連続した表(裏が一度も出ない)が切り捨てられる点が存在するに違いない。一例を挙げると、ゲームの参加者の忍耐がどこかで終わる。もし限界Lが狭すぎると思うなら、参加者の一生や人類の存続期間にもとづいて、かなり高い目の限界を定めたと考えよう。あるいは、太陽が爆発し地球が蒸発する将来の時によって課される限界だ。これらの限界のいずれもゲームの期待値を有限にするが、これらによって定められるLは25よりも大きい。では、Hacking の25ドルの直観はどうやって説明するのか?

 Lに限界を定めるもう一つの事実は、ゲームの基金に必要な財源が有限であるいうことだ。このゲームを提供するカジノは、どこまでも表が連続するのを切り捨てる用意をしないといけない。もし表が何回も続けば、カジノが賞金にできる基金の合計を上回るコストがかかるからだ。25回連続しても、33,554,432ドルの賞金しか必要にならない。大き目のカジノなら届く範囲だろう。40回連続すれば、約1.1兆ドルの賞金が必要になる。

2005年03月19日

サイコロの確率と格闘する ~一般の場合~(2)

 相変わらずサイコロ問題に取り組んでいます。
 
【問題】
さいころをn個投げたとき、目の和がkの倍数になる確率 a(k,n) を求めよ。

 これまでのこのブログでの成果を整理すると、
 一つは、
 k=4k=5k=8のときの厳密解を導出したこと。
 そしてもう一つは、次のような予想を立てたことです。
 
【予想】
 確率の遷移を x(n) = A * x(n-1) のように表現したときの、確率行列Aの固有値 λ0, ... ,λn-1を使って、 a(k,n) は、

a(k,n) = (1/k)×( λ0n + ... + λn-1n )

 と書ける。
 
 
 さて、調べたいことはたくさんあるのですが、
 ひとまずこの予想がどこまで正しいかを確かめようと思います。
 そんなわけで、今回は、k=12のときのチェック。
 はたして、予想から導いた確率の値と、実際の値とがどこまで一致しているか。
 
 まず、予想から導いた結果。
 経過は省略しますが、確率行列Aの固有値を計算すると以下のとおり。

λ0 = 1
λ1 = (( 2+√3)i-1) / 6
λ2 = ((-2+√3)i-1) / 6
λ3 = (( 2-√3)i-1) / 6
λ4 = ((-2-√3)i-1) / 6
λ5 = (-i-1) / 6
λ6 = ( i-1) / 6
λ7 = λ8 = λ9 = λ10 = λ11 = 0

 ここから、 上の予想の式に代入すると、次のような予想が得られます。
 
a(12,n)
= (1/12)×( λ0n + ... + λ6n )
1/12 + (1/12)×(1/6)n×{ ((2+√3)i-1)n + ((-2+√3)i-1)n + ((2-√3)i-1)n + ((-2-√3)i-1)n + (-i-1)n + (i-1)n

 さらにこれをきれいに整理して、

a(12,n) = (1/12) + (1/6)×(-√2/6)n×cos(nπ/4)
     + (1/6)×((√6-√2)/6)n×cos(13nπ/12)
     + (1/6)×((√6+√2)/6)n×cos(17nπ/12)

 もう、何が何だか分からない式ですね。。(笑)
 もし予想が正しいなら、この式が、サイコロをn個投げた目の和が12の倍数になる確率なのだそうです。
 どうも信じられない形です。
 
 さて、はたしてこれが正しい確率の値を示すのか。
 予想の式にnを値をいくつか実際に入れて計算してみました。
 
a(12,1) = 0
a(12,2) = 1 / 62
a(12,3) = 25 / 63
a(12,4) = 127 / 64
a(12,5) = 510 / 65
a(12,6) = 3888 / 66
a(12,7) = 25396 / 67
a(12,8) = 135832 / 68
a(12,9) = 817192 / 69
a(12,10) = 5145856 / 610
...

 と、好きなnに対して確率の値を計算することが可能です。
 さて、実際に厳密な確率の値を出してみると分かるのですが、少なくともn=10まで、ちゃんとこの予想値と一致しています。(漸化式を解くプログラム組んで値を出しました。)

 というわけで、k=12の場合は予想がどうやら正しいようだ、ということが示せました。
 厳密な解析は全く行っていないのですが、予想にかなり自信のもてる結果となりました。

2005年03月25日

相似的なぞなぞ

【問題】
 久しぶりにクイズ。
 ふと、次のような問題を思いつきました。
 空欄に当てはまる平仮名はいったい何でしょう、という問題です。
 完全にオリジナルな問題というわけではなく、かつてどこかで見た問題の日本語アレンジですが。

 ヒントは、答えはあなたが今見ているものですよ、ということです。
 分かったよ、という方は、コメント欄へ、ぜひどうぞ。
 
 ひ ふ つ く と か か
 ひ こ と わ と こ [?]

2005年04月02日

日能研の広告を眺めながら。

20050401 電車でついつい見てしまう広告の一つ、日能研。  ご存知の方も多いと思いますが、中学校の入試問題を掲示している広告です。  いつも通勤の時間が長いこともあって、ついつい見入ってしまいます。  さて、今回、目に付いたのはこんな問題。

 
【問題】
 砂地を行列をつくって行き来していたある種のアリの列のすき間を、太い棒で横切るようにサアーッと地面に線を引いたら、行列をつくっていたアリは引いた線の後側で右往左往して行列はとぎれてしまいました。
 なぜ、行き来できなくなったのですか。あなたの考えを一つ書きなさい。また、それを証明する実験を考え、あなたの考えが正しければどのような結果になるか簡単に書きなさい。

 こういうタイプの問題、大好きです。
 真実を知ってるかどうかを問うのではなく、自由な発想、科学的な思考ができるか否かを問う問題です。
 日能研のサイトにて、解答例&解説が掲載されています。
 
【解答例】
(あなたの考え)
 アリの列がたどれるように道につけた印が棒でけずられたためにとぎれたから。
(証明する実験)
 アリを紙の上で歩かせ、その紙の向きや場所を変えて、別のアリを歩かせてみる。
(結果)
 前のアリが歩いたあとを、別のアリもたどっていく。

 
 うん、たしかにこれは正解だと思います。一般に真実として知られている内容だと思います。
 ですが、僕としてはちょっと物足りない気持ちに。
 これ以外にもさまざまな解答例が考えられるのだから、それらをたくさん紹介してほしかったなあ。
 たとえば、こんな答え。
 
● 線の上を危険な場所と判断して、進むのをためらうから。
● 棒を捕食者と勘違いし、あわてているため。
● 記憶していた地面の形が変わり、進むべき方向が分からなくなったから。
● サアーッという音を、捕食者の出す音と勘違いし、あわてているため。

 問題文のみから判断するのなら、極端な話、このぐらい突拍子もない回答も十分OKだと思うのです。
 この問題で問いたいのは自由な発想で面白い仮説を立てられるかどうかです。
 可能性は決して1つじゃないし、答案に一般的な真実を書く必要だってまったくない。

 そもそも、アリがフェロモンを出して道しるべにすることぐらい、ちょっとした小学生なら知っているんじゃないか、というのも気になるところです。
 これだと、なまじ知っている生徒はいっそう「正解は1つ」なんて厄介な誤解を持ちやすくなるのでは。
 まず誰も知らない動物の生態についてとか、そっちの問題の方が面白そうです。


 最後に、頭の体操としてこんな問題はいかがでしょう。
 
【問題】
 上記で挙げた4つの可能性を証明するためには、それぞれどんな実験が必要か?

 
 これは難しい。。

2005年04月03日

聖ペテルスブルグのパラドックス(4-2)

 翻訳作業の続き。  書籍の翻訳を仕事にしている人って本当にすごいなあ、と思いつつ。  第4章の後半です。

 さて、このページをご覧頂いている方から、聖ペテルスブルグのパラドックスに関する非常に有益な情報を教えてもらいました。
 「サンクトペテルブルクのパラドックスについて
 確率を信念の度合いとしてとらえる、いわゆる主観説への批判。
 詳細はリンク先を参照ですが、パラドックスを直感的に説明するのが困難なのは、期待値が無限大の状況では大数の法則が成り立たないというのが原因だと。
 そしてその上で、聖ペテルスブルグのゲームでは、1回の料金をa円払うなら2回以上賭けをやった方が良い、と言えるらしいのです。
 つまり参加料が1000円なら、21000 ≒ 10301 回ぐらい賭けを行えば元を取れるだろう、とのこと。
 すごく面白い記事です。必読。
 残念ながら僕の理解力が低いため「どうやって証明できるの?」「チャンスが1回のときは結局4円で本当に正しい?」など、いろいろと理解に詰っているのですが。

-------------------------------------------

(第4章後半)

 この世で手に入るお金の量に限りがある、というような他の事情によっても、上限Lはもっともらしくなる。もしこのゲームが、お金を好きなだけ印刷できる国家によって提供されていると考えれば、おそらくこれらすべての金銭上の限界は取り除けるだろう。この国家は賞金をいくらでも支払うことができる。しかし、莫大な量の貨幣を印刷し拠出することは、経済の大混乱を引き起こすので、理性的な国家はそんなことはしないだろう。

 Hardin は、「ほんのわずかの現実主義があれば、聖ペテルスブルグのパラドックスに対処するのに十分である」と主張する。しかし、ほんのわずかの現実主義とは正当な考察なのだろうか? Lに上限が課され、それゆえゲームの可能な結果は有限個となるはずだと私たちは考えているが、その事実は聖ペテルスブルグのパラドックスを本当には解決していない。このゲームの期待値が無限大でないことを示していないからだ。結局、上限Lをもついかなるゲームも、私たちが議論しているゲームとは異なるのだ。私たちの疑問は聖ペテルスブルグのゲームについてであり、その関連物ではない。

 私たちは聖ペテルスブルグのゲームを考えているが、それは現実的な条件での話だ、と議論する人もいるかもしれない。現実の話、ルール上で言及されているか否かに関わらずこのゲームは打ち切られるだろう。このため、このゲームには有限で現実的な参加料が存在する。しかしこの場合、これより若干だけ高い参加料(長期的な利益を得るため)でこのゲームを提供するカジノが存在しないのはなぜだろうか?(結局、完全に現実的なのは誰なのか?)

 このすぐれた聖ペテルスブルグのゲーム――最初に述べたもの――は、決して人生で遭遇し得ない、とこれらの現実的な考察は示しているのだろうか。Jeffrey はこう言う。「簡潔にかつ粗っぽく考ると、聖ペテルスブルグのパラドックスの私たちの反論は、次のような着目点にある。聖ペテルスブルグのゲームをプレイさせようと申し出る人はみな嘘つきだ。無限に大きな銀行を持っているふりをしているのだから。」

 Jeffrey は厳密には正しくないと反論をすることができる。つまり、支払不能な結果が要求される可能性があるとわかりつつも、ゲームをしようと申し出ることはできる。これを、明日あなたを空港に車で送ろうという私の申し出と比較してみよう。私は、自分の車が今後それまでに故障する可能性があり、それゆえ実行不能になるかもしれない申し出をしていると認識している。しかし、可能と思われる申し出をしていないという結論にはならない。もし誰かがあなたを聖ペテルスブルグのゲームに誘ったからといって、その人が実際は聖ペテルスブルグのゲームを申し出ているのではなくある別のゲームを申し出ているのだ、という結論にはならない。

 現状の実際のカジノは、完了不能な長時間の連続、あるいは対処不能な大きな賞金が、きわめて小さな確率で起こり得るゲームをプレイしている。カジノは、あり得ない状況の起こるリスクが非常に小さいと確信しているため、あえてこのようなゲームをプレイしている。彼らは、対処できない負債が起こらないかと心配して眠りを失う必要はない。彼らは、必然性でなく偶然性の上に生きながらえ、繁栄するのだ。

 もしこれらの考察が説得力のあるものならば、Jeffrey が与えたものはパラドックスの反論とはならない。実際には、彼はこのゲームには無制限に大きな支払いの可能性があるという事実を受け入れている。カジノがこのゲームを提供しない理由は、遅かれ早かれ(おそらくはずっと後で)、このゲームが破産を引き起こすということを認識しているからである。これは正しい理由付けだ――しかしこれは通常の一般的な選択理論による。カジノがこのゲームの理由付けをするとき、通常の理論によればこのゲームは無限大の値を持つので、その考察を除外するために通常の理論を制限しようとはしない。

 このゲームの考察を除外するために理論に制限を加えるべきでない理由は他にもある。理論的に受け入れられようとするために、この規則づけは聖ペテルスブルグのゲームを特別扱いして単純に除外するべきではない。それは一般的な範囲であるべきだ。そしてもしそうなら、完全に受け入れられる計算も除外されるだろう。Michael Resnik(1987) は、効用理論は「無限大の宝くじをカバーするよう容易に拡張でき、そしてそれは統計的決定理論におけるより進んだ問題に対処するためでなければならない」と記している。しかし彼は例を与えていない。

 子どもの誕生時に購入した生命保険の方針について想像してみよう。やがてその子どもが死亡すると、その財産的価値に対し、それまでに経過した誕生日一日につき$1000が上限なく支払われる(訳注:つまり、死亡年齢×千ドルということ)。保険会社は、この方針に対していくらの価格を請求すべきだろうか?(簡単のため、起こりえるインフレの影響や、参加料投資の利益を無視しよう。)経験則に基づく標準的な死亡率チャートによれば、さまざまな年齢の人の今後1年間を生き延びる可能性を知ることができる。もちろん、140歳の人が今後1年間を生き延びる可能性についてはそれには載っていない。入手可能な経験的証拠がないからだ。しかし、死亡率曲線を、経験的証拠の入手可能な範囲をこえてどこまでも伸ばしていくと、妥当な関数をつくることができる。この曲線は漸近的にゼロに近づく。これに基づけば、通常の数学的な手法によって、この方針の期待値を得ることができる。しかし、支払いに上限がない決まりだったことに気をつけよう。そう考えると、年齢ごとに今後1年間を生き延びる可能性が(大なり小なり)存在する。すると計算の際には、考慮すべき結果の数が無制限に多く存在するが、数学を使えばこの無限級数の極限を計算することができる。そして(そのほかの要因を無視して)保険会社は、この量を上回る金額を請求して、利益を得ようとするだろう。期待値の計算に問題はない。

 この保険会社の方針(方針1と呼ぶ)は、無限の個数の結果がある。しかし、級数を140歳で打ち切った、これとは別の方針(方針2と呼ぶ)を考えると、この方針は、高々140個の結果しかない。140歳の年齢に達する可能性は非常に小さいので、2つの方針の期待値の差は1セントの一かけらであり、無視できる。もしあなたが無限大の宝くじを気に入らないなら、方針1は形が不適格だと主張し、実際上の期待値は方針1と等しいと示した上で、代替の方針2を提案すればよい。しかし、2つの期待値が仮想的に同一であるという判断は、方針1の期待値が計算できたことに依存しているという点に注意しよう。結局は、方針1の期待値が計算可能であることを、この説明は前提としているのだ。

2005年04月14日

教育的なぞなぞ

 20050414ついつい感じ入ってしまったクイズ。  どうぞ考えてみてください。

【問題】  ある規則にしたがって、7つのアルファベットが下に並んでいます。  さて、空欄にあてはまるアルファベットは何でしょうか?    S M T W T [?] S      ・・・という問題。    僕の場合、問題を見た後にすぐ感づきました  ああ、これ、一週間の曜日の頭文字やん。  Sunday、Monday、Tuesday、・・・ という具合なわけね。  よって答えはFridayの「F」。簡単簡単。    というような思考を経たのですが。  実はこの問題、他にも答えはあり得るのですね。  別解例としては「M」。  理由はいたってシンプル。  文字の並びが左右対称になるから。    これを聞いて、思わず「やられた!」と口走ってしまいました。  いやもちろんFだって十分に妥当な解答なのですが。  ですが、どう見たって、Mだと左右対称になるという説明の方が単純で素直な発想のように感じられるのです。  これはつまり、自分の頭の中で勝手に「アルファベットの規則性クイズといえばたいてい何かの頭文字」という先入観が働いていたからに他ならないです。  で、1つの答えにたどり着くと、満足してそれで思考停止。

 

 パズル好きの陥りそうな罠なのかも。

2005年04月19日

聖ペテルスブルグのパラドックス(5)

 このページを粛々と訳し続けています。  一連の作業を通じているうちに、だんだんと、翻訳という行為への関心がむしろ強くなっていってる気が。  頭の中で、各単語の意味のイメージがもわもわと浮いていて、レンガを積むようにそれらを操って文章を構築していく感じ。

 もうちょっと精進しましょう。。

 

 

第5章 無限大の値?

 

 聖ペテルスブルグのゲームは無限大の期待値を持つからだと片付けられることがある。これは単に実践が不可能だと考えられているのではなく、理論的に疑わしいものだと考えられている――思考実験の範疇すらも超えている。しかし、そうだろうか。

  次のような取引きを持ちかけられたと想像してみよう。あなたは、次のような普通でない特徴を持つキャッシュ・マシーンの永続所有を与えられる。あるドル額をこの機会に打ち込むと、いつでもその金額が吐き出されるのだ。これはあなたの口座からの引出しでもなければ、後から請求書が送られてくることもない。これを何回でも行うことができる。さて、あなたはこの機械にいくら出せるだろうか? こんな思考実験をしたり、答えを出したりするなんて無理だと思うだろうか。おそらくそうではない。答えはこうだろう。いくらの額でも、である。この機械を受け取ったあとで、十分な時間、支払いを延期することができるなら、その機械自体から、支払いに必要な額をいくらでも集めることができる。

 

 もちろん、実践的な考察が存在する。たとえば1兆円がその機械の価格だったとして、その機械から1兆円を集めるのにどれだけ時間がかかるだろうか? それまでに衰弱したり死去したりしないだろうか? 無限キャッシュ・マシーンを売ろうとする銀行がもしあれば、そんな銀行は頭がどうかしているだろう。残念なことに、私はこんな申し出をしてくる、頭のおかしな銀行の住所の控えをなくしてしまったようだ。いずれにせよ、このような思考実験を行うのに問題はなさそうだ。これは、期待値に上限のない行動(この機械を買うこと)を想像している。期待値を計算すれば、実践的な考察を容易に無視できる。(この場合は、単純に、引出し可能額マイナス購入額だ。)期待値は無限大である。

 

 直感的に考えて、この機械にたかだか(たとえば)25ドルしか出せないと思うだろうか? そうではないだろう。しかし、この機械と聖ペテルスブルグのゲームとがただ異なるのは、この機械は、限りのない回数の支払いを保証している一方で、このゲームは、限りのない個数の支払い結果(それぞれある特定の確率を持つ)からの1度の抽選結果を提供している。両者の唯一の違いは、確率の要素である。つまり、5ドルの賞金が保証されているゲームと、半分の可能性で10ドル、半分の可能性で0ドルもらえるゲームの間にあるものと同様の差異である。聖ペテルスブルグのゲームと無限キャッシュ・マシーンの両者の期待値は、いずれも限りなく大きい。あなたはいずれに対しても、それがいくらの価格だとしても申し出をすべきである。期待値が無限大だと気づくことは、まったくの理性的であるように思える。

 

 ある考察の中で無限大が出現すれば、ナンセンスな自体が発生するというのは非常に正しい。こんな例を考えてみよう。私は、ある整数をランダムに紙に書きつけ、それを封筒に入れる。あなたは封筒を開き、私の書いた数を確かめる。8830441。私が書かねばならなかった整数は無限にあるので、私がこの数を書く確率はゼロである。これは奇跡である(あるいはたぶん矛盾だ。)ここでの問題はもちろん、文字数が無限の整数から選択をするという考えのおかしさである。

 

 形而上学的な無限の現実についての疑念、そしてそのような概念を正しく雇い入れることについての疑念は、哲学、数学の歴史を通じて起こり続けてきた。それゆえ、聖ペテルスブルグによって引き起こされるパラドックスは、無限を誤って利用していることにただ起因するのだ、という考えは魅力的な考えである。しかしこの賭けやその結果を記述する際に、無限を呼び出す必要はないということに注意しよう。考えられるいかなるゲームも、支払額はつねに有限である。考えられるいかなるゲームの長さも同様だ。パラドックスとなる結果はこのようにして起こる:請求される(有限の)参加料Xがいくらであっても、X回以上コインを投げる確率(非常に小さい)が存在するため、期待されるゲームの支払額はそれよりも大きくなる。(同様に上記の優れたキャッシュ・マシーンは、無限の現実の条件、つまり起こり得る支払いはいつも有限で、いかなる点においても有限の回数だけ使用されているという条件には基づいていないということに注意しよう。)

 

 ある意味では、聖ペテルスブルグの直感に反する結果は、古典的決定理論に対する、一般的で聞き慣れた反対意見の特殊ケースである。古典理論では同じ値を持つとされていても、半分の可能性で10ドル、半分の可能性で0ドルをもらえる賭けよりも5ドルの賞金が保証されている方を好むというのは、まったくもって理性的だ、と反論する人もいるかもしれない。あなたがもし、無限キャッシュ・マシーンは無限大の期待値を持つものの聖ペテルスブルグのゲームはそうではない、と直感的に考えるのであれば、あなたはおそらく、こうした一般的な反論を、古典的理論に依存しているのだろう。保証された賞金を賭けよりも好むというのは理性的でないという議論は可能であるし、また、このような好みの合理性を説明できるように、理論に「修正をほどこす」ことは可能である(たとえば、リスク回避の修正を許容することによって。)しかしながら、聖ペテルスブルグだけの問題でなく、このような古典的理論のより一般的な「問題」には対処がなされる。そして、聖ペテルスブルグを排除するために理論に特別な修正をほどこすことは、より一般的なこの問題を取り扱う上で助けとはならないだろう。

 

2005年05月02日

画像閲覧ソフトを作ってみました。

20050502  連休なので、プログラミングの練習中です。

 たいへんこじんまりとしたソフトですが、ひとまず版が完成したので公開です。

 なんというか、特定の用途の画像閲覧に特化した画像ビューワです。

  -----------------------------------------------------

    シンプル画像ビューワ 「マウスビューワ ver.0.1」

     ダウンロード
 (注:念のためウィルスチェックして下さい)

  -----------------------------------------------------

 巷にあふれている画像ビューワと比較して、当ビューワには、こんな特徴があります。

超シンプル画像切り替え!

  マウス右ボタンが「次の画像」、左ボタンが「前の画像」。お手軽な画像切り替えをご提供。

なめらかズーム!

  ふつうの画像ビューワって、段階的なズームしかできないんですよね。

  マウスホイールを回してみて下さい。なめらかなズームにきっと驚くはず。

ドラッグ不要のズーム位置変更!

  今までの画像ビューワは、ズームインをした後で表示する位置を変えたいとき、画像をドラッグして位置変更する、というのがほとんどです。

  このソフトでは、単にマウスを動かすだけで位置変更が可能。

  ドラッグなんてストレスのたまる操作はさせません。

もちろんフルスクリーン機能対応!

  この機能がない画像ビューワなんてあり得ません。


 ・・と、いかにも胡散臭い広告のような煽り文句を並べ立てましたが。

 近頃のますます複雑化するアプリ操作に対抗して、必要最低限の画像閲覧機能を、いかに負担の少な


い操作で実現するか、に注目したビューワです。


 こういうソフトのニーズは、間違いなく異様に高いはず。

 上記の宣伝文句を見て、いいかもと思われた方、是非お試しあれ。

★★ 注意! ★★

 なお、このソフトは単体では動作しません。

 閲覧したい画像フォーマットに対応した SPI プラグインが必要です。

 例えばこのサイト
から、適切な SPI プラグイン(拡張子は.spi)をダウンロードしてきて下さい。

 解凍してできたSPIファイルを、実行ファイルと同一フォルダに置きます。


 詳しくは同梱の "readme.txt" をご参照下さい。

2005年05月15日

言葉への思いつき2点

 電車のなかでふと思いついたこと。

 「悩む」とは、問題解決の以下のプロセス:

 

0.問題にきづく。

1.問題を分析する。

2.対処法を挙げて、その妥当性を検討する。

3.適切な対処法を実施する。

 のうち、1~3 のいずれかを、行えないか、または行わないでいること。

 

 0 にすら及ばない人、あるいは、0から3をあまりにスムーズに実行する人は、

 「悩みなんかなさそうな人」 と呼ばれることがある。

 「地球にやさしい」なんて表現があるけれど。

 

 ここでの「やさしい」という言葉は、絶対的ではなく、相対的なやさしさを指す。

 つまり、たとえば、ある生徒から毎月1万円をカツアゲしていたいじめっ子が、

 「今月からは毎月5千円でいい」 なんてことを言ったときに、

 それを 「彼はやさしくなった」 と表現するのと同じ感覚。

  

2005年05月19日

科学シンポジウムに寄ってみた。

 先週の土曜日に大手町で開催された、科学シンポジウム「サピエンス」に行ってきました。

 僕が関西で学生やっていた頃は、へーこんなんやってるんだー、と遠い地のこととしか思っていなかったのですが、せっかく関東に移り住んでいるのだし、と思い立っての参加です。

 テーマは、「2005年世界物理年 アインシュタインは超えられるか」。ここ

 のちに「奇跡の年」と呼ばれる1905年は、アインシュタインが、相対性理論や光量子仮説、ブラウン運動を含む5つの論文を相次いで発表した年で、今年はそのちょうど100周年になる年です。

 そういうわけで、講演会では、アインシュタインの業績がらみ、ということで、

 量子情報通信理論の井本先生、宇宙論の白水先生の講演が行われました。


 (あともう1人いたけどここでは省略。)

 なによりも、2人の先生の講演のうまさに惚れ惚れときました。

 井本先生は、双子の光子の性質を、火星と地球を訪れた夫婦にたとえてみたり、実験環境を魔法ビンにたとえてみたり。

 あるいは、暗号鍵を暗号文に作用させる様子を、2枚の透明シートを重ねることで隠れたメッセージを浮かび上がらせて表現するというアイデアには、目から鱗でした。

 僕がいちばんウケたのは、白水先生が講演の開始直後に言ったジョーク。

 「アインシュタインが明らかにしたのは、時間とは絶対的なものではないということです。ですから、今年は奇跡の年から100周年だと言われていますが、相対論の立場で見てみれば、100年という数字にも、もはや絶対的な意味なんてないということですね。」

 

 講演後はパネルディスカッション。

 お題目が「アインシュタインの遺産と21世紀の科学技術」というものだったのですが、他のとあるパネリストの独演・宣伝と、「研究者と変人について」の笑い話で終始した気がしたのは、ちょっと残念な感じ。

 まあいずれにせよ、やっぱりこういう講演会って、ただ知識を習得するだけに限らず、その後に自然と、いろんな話題への興味のアンテナがすごく敏感になっているのが良いですね。

 ふだんやってる会社の仕事以外のジャンルにも、触手を伸ばしておく余裕が欲しいです。

2005年05月21日

円周率の任意の桁を一発で計算する。

 先日の記事で紹介した、円周率の任意の桁の数字をもとめる方法について。 
 16進数での表現をもとめるには、以下の公式を紹介しました。
 この公式を使うことで、きわめて小さいメモリ使用量での計算が可能になります。

20050521a
 ・・・ (1)

 ですが、ぱっと見ただけでは、実際にこの式どう使うのかがよく分かりませんでした。
 適当にグーグルしたものの、適切な解説は見つからず。
 そこで、この公式を使った、円周率の任意の桁の導出アルゴリズムについて、以下に解説を提供。
 というか、むしろ、ここのページの日本語訳です。
 
 
【BBP公式による円周率の任意の桁の導出アルゴリズム】

 上記の (1) 式は、4つの部分に分けられます。
 それらを、以下のように、s1, s2, s3, s4 と表記します。
 s1 と s2 については、係数の4と2をひとまず除外しています。
 
20050521b
 ・・・ (2)
 
 いま、円周率πを16進数で表したときの、小数第d位以下の桁の数字が知りたいとします。
 すぐに分かりますが、これは、π に 16d をかけたものの小数部分に等しいです。
 同様に、s1 の小数第d 位以下の桁の数字は、s1 に 16d をかけたものの小数部分に等しいです。
 これは、zの小数部分を、frac(z) と表記すると、frac(s1×16d ) と書けます。
 frac( s1×16d ) は、次のように変形できます。
 
20050521c
  ・・・ (3)
 
 1行目から2行目は、単にk=dで分けただけ。
 2行目から3行目で、余りを求める演算 mod が入っていますが、この式で必要なのは小数部分だけなので、和の結果に影響はありません。

 さて、この式の前半部分の計算をします。
 ここに登場する、べき乗した数から余りをもとめる計算というのは、それほど大変な作業ではないんですね。
 16k の値を計算して格納する必要はなく、1回16をかけるごとに mod 演算をしても答えは変わりないので、メモリ使用量を節約して計算することができます。
 3兆桁程度であれば、値を格納するのに64ビットのメモリがあれば十分だそうです。
 
 こうして、式の前半部分の計算が完了します。
 
 次に、後半部分を計算します。
 後半部分には無限個の項が含まれています。
 ですが、この級数はゼロに収束するので、ある程度のkのところで計算を打ち切ってかまいません。
 ここの計算では、前半部分と違い、べき乗の計算を自力でやらなくてはいけないのですが、この収束のスピードは非常に速いため、それほど大きな計算量というわけではありません。

 以上のようにして、s1×16d の小数部分が求められます。
 同様に s2, s3, s4 についても求め、4*s1-2*s2-s3-s4 を計算すれば、円周率の小数第d位以下の桁の数字がもとめられます。
 
-----------------------------------------------

 以上です。
 さて、やっぱり気になるのは、任意の基数での表現方法ですね。。
 Simon Plouffe により、この方法が見つけられたそうなのですが(ここ)、どういう方法なのかなんとなくは分かったものの、実際にどうやって計算できるのか、未だ不十分な理解で困っています。
  
 と思ったら、上記の方法のコードを書いてる方がいらっしゃいました。ここ Home>今日の一行>2005年5月9日)。
 いったいどういう仕組みなんだろう、これ。そもそも全く見たことない言語だ;

2005年05月24日

暗号パズル。

 なんとなくネタが思いついたので、暗号パズルを作ってみました。

 ひらめき重視です。

 特に難しい数学は必要ありません。


 分かったよ、という方は、コメント欄へぜひどうぞ。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

7つの線分は語る。

 {1+(8-7)} + 1 + (0-1) + (8-1)

が示すものとは?

 {4+(6-5)} + (8-1) + {(0-7)+(9-3)} + {F+(8-6)}

が「助け」となるだろう。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 ・・・よくあるネタだったらごめんなさい。

2005年05月26日

このごろのモヤモヤ2点

 このごろ頭の中でモヤモヤとしていたことがらを2点。

 文体に素っ気がないのは、気にしないのが吉です ^^;



 頭脳を働かせるためのルーチンワークが流行するのはなぜだろう?

 ルーチンワークって、頭の働きを節約するためのものなのに。

 

 頭のよく働く人にはなりたいけど、そのためにどうすればよいか、には頭を働かせたくないってこと?



 「頼りにする」と「当てにする」の違いは、

 依頼する側に、解決する意志があるかないか。

2005年05月27日

すごく素敵な確率の問題

 あまりの面白さに、ついついうなってしまった確率の問題。

 先日にこのブログで紹介した井本先生の、ホームページ(ここ
)を訪問したときにこの問題と遭遇しました。

 以下に抜粋。(一部修正。)

----------------------------------------------------

 n組の男女ペアが一旦バラバラになり再びランダムに男女ペアを組むとする。このとき、

1.元のペアが一組もできない確率P(n)を求めよ。

2.lim(n→∞)P(n)を求めよ。

----------------------------------------------------

 ことによると、先生は中高生のときにこの問題を考えついたのだそう。

 この手の問題は、紹介する側がしゃべりすぎると、せっかくの面白さが半減してしまいます。

 そういうわけで、この問題の正解・解説 etc. の話は、ひとまずは置いておくことにします。

 (いや、僕自身は、結局正解にたどり着くことはできずにギブアップしたのですが。)


 興味を持った方はぜひチャレンジしてみてください。

 と、せっかくですので、いったいこの問題のどんなところが面白かったのか、をそれとなく示してみます。

 各nに対するP(n)の値を、プログラムを書いて導出してみました。

 以下のような結果になります。

 

P[1] = 0.000000

P[2] = 0.500000

P[3] = 0.333333

P[4] = 0.375000

P[5] = 0.366667

P[6] = 0.368056

P[7] = 0.367857

P[8] = 0.367882

P[9] = 0.367879

P[10] = 0.367879

P[11] = 0.367879

P[12] = 0.367879


...

 どうやら、0.367879... という数字に収束するみたいですね。

 さて、手元に電卓を用意して、0.367879 の逆数(1をこの数で割る)を計算してみてください。

 きっと、「え・・・どういうこと?」という表情になるはずです。(高校で文系だった人はごめんなさい。)

 

 ちなみに、適当に検索をかけてみると、この問題の正解にたどり着いている方のページを発見できます。

 そこへのリンクの紹介は、また後日ということで。

2005年06月04日

すごく素敵な確率の問題 ~答え~

 前回(これ )紹介した、とても素敵な確率の問題。

----------------------------------------------------

 n組の男女ペアが一旦バラバラになり再びランダムに男女ペアを組むとする。このとき、

1.元のペアが一組もできない確率P(n)を求めよ。

2.lim(n→∞)P(n)を求めよ。


----------------------------------------------------

 僕は、数時間ほど考え込んだものの、結局ギブアップ。(漸化式を出すことには成功したのですが。。)

 適当にグーグルに聞いてみると、この問題の正解に到着している方がいらっしゃったので、リンクを紹介です。

 ここ


 リンク先を参照しながら、他の説明の仕方を模索してたのですが、結局それもかなわず、以下はリンク先の解答の言い直しになってしまいました。残念;


1.


 正解はこれ。


20050605a

 以下ではn=4の場合について書きます。

 もともとのペアを夫婦1、夫婦2、夫婦3、夫婦4と名付けます。

 求めるべき確率の余事象は「少なくとも1組がペアになる」ですので、全事象の確率1から、この確率を引き算すれば良いです。


 


P(4) = 1-(少なくとも1組がペアになる確率)

 このカッコ部分を、次のような計算で求めようと思います。

Q(1) ≡ (夫婦1がペアになる確率)+(夫婦2がペアになる確率)+・・・+(夫婦4がペアになる確率)

 つまり、P(4) を、1-Q(1) で求めようとするわけです。

 ですが、これでは求めるべき確率よりも小さくなってしまいます。

 いくらかの場合の数を重複して数えているので、結果として引き過ぎてしまっているからです。

 引き過ぎた分をリストアップすると以下のようになります。

 

(ちょうど2組がペアになる確率) ・・・ 1個 (1-=-1)

(ちょうど3組がペアになる確率) ・・・ 2個 (1-=-2)

(ちょうど4組がペアになる確率) ・・・ 3個 (1-=-3)

 これらのバランスをとるために、次のような計算式Q(2)を足すことを考えます。

Q(2)

≡ (夫婦1,夫婦2がペアの確率)+(夫婦1,夫婦3がペアの確率)+(夫婦1,夫婦4がペアの確率)

 +(夫婦2,夫婦3がペアの確率)+(夫婦2,夫婦4がペアの確率)+(夫婦3,夫婦4がペアの確率)

 つまり、1-Q(1)では引き過ぎたので、Q(2)を足して、1-Q(1)+Q(2)でP(4)を求めようとするわけです。

 ですが、今度はこれでは、以下の分を足し過ぎています。

 (ちょうど3組がペアになる場合の数) ・・・ 1個 (1-=1)

 (ちょうど4組がペアになる場合の数) ・・・ 3個 (1-=3)

 そこで次は、以下のQ(3)を引きます。

Q(3)

≡ (夫婦1,夫婦2,夫婦3がペアの確率)+(夫婦1,夫婦2,夫婦4がペアの確率)

 +(夫婦1,夫婦3,夫婦4がペアの確率)+(夫婦2,夫婦3,夫婦4がペアの確率)

 すると今度は引き過ぎなので、最後に、次のQ(4)を足して、やっとバランスがとれます。

Q(4) ≡ (夫婦1,夫婦2,夫婦3,夫婦4がペアの確率)

 結局、

20050605b  

 となります。

 実は、この関係は一般的なP(n)について言えます。

(これは (-1+1)の2項展開を考えると分かります。1--・・・+ は常にゼロです。)

 さて、あともう少し。

 実は、一般的な Q(k) は計算可能です。

 Q(k) を書き下したときの項の数は全部で nCk 個。

 各項の確率の値はすべて同じで、(n-k)!/n! で求められます。

 ですから、


20050605c


 以上から、P(n) は以下のようになります。

20050605d    ...(答)

 というわけで、2.の極限は、1/e に収束します。

2005年06月14日

暗号パズル。

 ふうっとした拍子に、暗号パズルを思いつきました。

 

 思いついたは良いものの、絵をかくのにけっこう苦労しました。

 さて、この図に隠された言葉とは何でしょう。


 分かったよ、という方は、コメント欄へ、ぜひどうぞ。

 

~~~~~~~~~~~~~~~~~~~~~~


隠された言葉とは?

20050614

                     (クリックして拡大)

 ヒントというか、カラースケール。

   20050614b

~~~~~~~~~~~~~~~~~~~~~~

 ちょっと、グラデーションが分かりにくいかも知れません。ごめんなさい。

2005年06月18日

すごく素敵な確率の問題 ~アレンジ編~

 先日に紹介した、男女ペアをつくるときの確率をもとめる問題。これ

 さて、これをアレンジしたバージョンを考えてみました。

 もともとの問題はこんなのでした。

----------------------------------------------------

 n組の男女ペアが一旦バラバラになり再びランダムに男女ペアを組むとする。このとき、

1.元のペアが一組もできない確率P(n)を求めよ。

2.lim(n→∞)P(n)を求めよ。


----------------------------------------------------

 解答はこんな感じです。

 さて、今回は、これをアレンジした次の問題を考えてみることにしました。

 

----------------------------------------------------


 n組のペアが一旦バラバラになり再びランダムにペアを組むとする。このとき、


1.元のペアが一組もできない確率R(n)を求めよ。

2.lim(n→∞)R(n)を求めよ。


----------------------------------------------------

 つまり、もともとの問題では必ず男女でペアを組まないといけなかったのに対して、今回の問題では誰とでもペアを組んでもよいという設定です。

 はたして、もとの問題と同様に、この問題の確率もなにか面白い数字に収束するのでしょうか?


 というわけでしばらく考えてみたのですが、実は1.は、もとの問題の簡単な応用ですぐ導出できました。

20050619

 間違ってたらごめんなさい。

 ここで、(2n-1)!! とは、(2n-1)×(2n-3)×・・・×1 のこと。

 さて、できたはいいのですが、ではこれのn→∞のときの収束先はいくらなのかがどうも分かりそうにないです。

 で、例によって、ここから先はプログラムに任せてみます。

 

R[1] = 0.000000

R[2] = 0.666666

R[3] = 0.533333

R[4] = 0.572429

R[5] = 0.575661

R[6] = 0.581049

...

R[1000000] = 0.606531

...

 どうやら、今回の場合は、0.606531... という数字に収束するみたいです。

 で、電卓をしばらく叩いていて、発見しました。

 この 0.606531... という数字、1/√e にきわめて近いのです。

 

 なんだかすごく不思議な結果が出てきました。

 どうやら、1.の確率が、n→∞で 1/√e に収束するようなのですが・・・しかし、残念ながら、自分の力ではそれを証明することができません。

2005年06月19日

突発的に思いついたこと。

 単純な発想な上に、もう既にだれかやってそうだけど、メモ。 

 携帯電話の番号を変えたとき、知人に新番号のお知らせをするのってけっこう面倒だったりします。ごく親しい知人だけなら大したことはないのですが、それより広い範囲の人もとなると、けっこう大変な作業です。

 

 さて、そんなときの対処法として、「自分の個人ページやブログで、新番号を公開してしまう」という方法はどうでしょうか。

 

 もちろん新番号をそのまま書くのではありません。「旧番号との差分」を書くのです。つまり、これこれの数字を前の番号に足し算してください、という情報だけをのせておくわけです。

 

 たとえば、以前の番号 09012341234 から、新しい番号 09087654321 に変更したとすると、

 

~~~~~~~~~~~~~~~~~~~~~~~~~

 

 携帯の番号かえました。

 前の番号に 75313087 を足してください。

 

~~~~~~~~~~~~~~~~~~~~~~~~~

 

 ということを、自分のブログに書いておく、と。こうすれば、もともとの番号を知ってる人に限定しながら、広範囲の人に正しく新番号を伝えられます。

 

 この方法の難点は、自分のブログの存在を知っていて、なおかつ定期的に見にきている知人にしか通用しないということですが。あくまでも補助的な方法として、直接お知らせする方法とうまく併用して使えば、効果を発揮することができそうです。

 

2005年07月04日

自分の安全は自分で守る ~アメブロとの共存のために~

 平素は大変お世話になっているアメブロブログについて。7月1日~4日の間、メンテナンス作業のためにサービスが一時停止になっていました。予定では停止は4日までだったのですが、作業が順調に進んだらしく、3日の16時15分の時点で既にサービス再開。おそらく、「お、ラッキー、早く終わってるやん」と、喜んだ方も多くいらっしゃることと思います。

 

 ですが、再開直後の3日晩からトラブルが発生しているもよう。システムエラーが表示されたり、ページそのものに接続できなかったりしてます。4日晩の現在の時点でも、接続にやたらと時間がかかっています。

 

 そういえば、以前から、「記事アップの際にエラーが出て、書いてたテキストが消えた」とか、「メンテナンス予定が直前になって中止になった」とか、どうも不安定な空気を感じるところがありました。さて、今回のことを踏まえて、そろそろ、次のことを本気で心配すべきじゃないか? という気がしてきました。

 

 ・・・そのうち、過去の記事が消えた、なんてトラブルが発生するんじゃないか??

 

 ユーザの記事が消えるなんて事態は、ブログサービスにおいて一番の最悪な結末でしょうから、定期的なバックアップなどの対策は(きっと)もう既に実施中なのでしょう。ですので、このような心配はたんなる杞憂に過ぎないのかも知れません、ですが次第に、「何が起こっても変じゃない」という不安な気持ちがしてくるのも事実です。

 

 というわけで、「自分の安全は自分で守る」の精神にのっとって、過去の記事が消えた! という万が一の事態の際に、いかに受ける被害を最小限に抑えるか、そのためにどんな予防が考えられるか、を考えようと思います。地震対策と同じです。それも、できるだけ、手間のかからないやり方を模索。以下、思いついた対処法と、その妥当性を考えます。

 

 

 【対処法1】 ブログサービスを乗り換える。

 

 いや、そもそもこれがすごく手間だから、今回の検討を始めるわけです。それにある程度つづけていくと、愛着(意地?)のような気持ちも湧いてくるわけですし、ねえ? というわけで、基本的に却下。

 


 

 【対処法2】 書いた記事を毎回テキストファイルで自分のPCに保存しておく。

 

 もっとも確実であり、かつもっとも面倒な予防法でしょう。いちど習慣付けてしまえば楽ちんなんですが・・・。かつてアメブロは、記事アップ時にエラー→たった今書いた文が消えた、というトラブルが頻繁に起きていた頃があったので、そのときからのユーザは、自分のPCで記事を作成→ブラウザにコピーペースト、という習慣を既につけている人が多いかもしれません(僕はそうしてます)。そういった人は、毎回書いたテキストファイルを適当なフォルダに放りこむことを新たな習慣とすることで、比較的負担を少なく実施できるかもしれません。

 


 

 【対処法3】 グーグル・デスクトップを常駐させておく。

 

 グーグル・デスクトップ検索というアプリケーションがあります。ここ
から無料で入手できます。これを普段からPCに常駐させておきます。自分のPC内のファイルやチャット、表示したウェブページのテキストなどをキャッシュとして定期的に保存してくれ、必要なときにキーワード検索できます。自分では「もうとっくに消しちゃったよ・・・」と思っていた文章でも、デスクトップ検索で探すと、意外と無事に残っていることがあります。

 

 こんな画面に・・・

 

 20050704a

 

 例えば、ameblo+(自分のID)+(目的の文章の一部) とキーワードを入れると・・・

 

 20050407b

 

 何件かがヒットします。ここで「キャッシュ」をクリックすると、キャッシュに残っていた文章を手に入れることができます。ただ、この手段の難点は、かならずしも目的のテキストのキャッシュが残っているとは限らず、100%完全に復旧できるとは言えない点ですかね。。

 とはいっても、グーグル・デスクトップ検索は普通に便利なので、導入しておくのがおすすめ。


 

 【対処法4】 ウェブ検索エンジンのキャッシュから発掘。

 

 これは予防法というより、災害時の復旧方法ですね。グーグルやヤフーの検索エンジンで、上と同様のキーワードで探すと、けっこう引っかかります。で、同様に「キャッシュ」をクリックすると、目的の文章を救出することが可能です。この方法も、3と同様、かならずしも目的の文章がキャッシュ化されていない可能性があります。あと、回収の手間がかかるのもこの手段の特徴。

 


 

 【対処法5】 更新内容のメール自動送信機能をアメブロに要望する。

 

 これはアメブロへの要望ですので、出したからといって即効性はないでしょうが。。記事を更新したときに、自分のメールアドレスに、たったいま自分の書いた文章のコピーが自動的に送信される機能があれば、今回の問題はすべて解決しそうです。(さらにあわよくば、使った画像ファイルも添付してくれると最高によいです。)

 ただ、この要望をたんに「バックアップのために・・・」として出したところで、実施にいたらせるだけの説得力に欠けるように思えます。「複数のメンバーでブログを更新しているときの更新通知のために」などという理由を併せて訴えた方が、説得力がありそうです。

 

 

 ・・・と、ひとまず現状のところ、思いつく手段を挙げてみました。他に、なにか手軽で、なおかつ万が一のときの復旧を確実&効率的に行える手段はないものでしょうか? 思い付いた方は教えてください。

2005年07月25日

ゲーム作りな週末

 ここのところ、毎週週末をゲーム作りに費やす日々が続いてます。

 おかげでブログを書くためのネタと時間の確保ができてません。

 とはいっても、記事を書かずにブログ放置はさすがに避けたいので、作成の進み具合を記録しときます。

 

 こんな感じのゲームです。

 簡単に言うと、「何をすればよいのか自分で推理するパズルゲーム」。

 むかし作ったものWinアプリ焼き直し版ですが・・・。

 

 20050724a
 20050724b

 

 完成したら、このブログからダウンロードできるようにいたします。

2005年07月28日

0.999・・・のモヤモヤを取り除け

 以前に、このブログの訪問者の方から教えていただいた内容をもとに。

 

 高校のときに、「0.999・・・=1」という等式は正しい、ということを習いました。けれどこれは本当に等しいのか? という疑問についてです。

 たしか高校で無限級数のことを習ったときに、ついでにこの等式についての説明を受けた記憶があります。ですが、どうもピンと来なかったし、改めて考えてみると、実は違うんじゃないか、という気にもなってきます。この問題に感じるモヤモヤ感の原因は、いったいどこにあるのでしょうか?

 

 まず、この問題に対する説明の中で、もっともよくありがちなものを挙げてみます。

 

【等しい派の意見】

 こんなの等しいに決まってるよ。分数の1/9は、小数で書くと「0.111・・・」だよね。1/9=0.111・・・なんだから、両辺を9倍して、「1=0.999・・・」。ほら証明できた。

 

【違う派の意見】

 「1未満」って言葉は、「1」そのものを含まないよね。「0.999・・・」ってのは、9をいくらでも伸ばしていける数のこと。9を伸ばしていくと、1にいくらでも近づくことができるけど、それは決して1そのものにはならない。1とは違う数だよ。

 

 前者の意見にせよ、後者の意見にせよ、どうも一筋縄には納得できないと感じてしまうのはなぜなのでしょうか? それはいずれの説明も、「0.999・・・という表記は、結局のところ何を意味するのか?」という部分を、あいまいなままにしてしまっているのが原因なのです。

 

 たいていの場合、「・・・」とは、本来書かれてあるものを省略して表すときや、いつまでも続くことを表すときに使う記号です。この問題を考える上で陥りがちなのは、今回のように「0.999・・・」と書いてあったときに、これを「ゼロに9がいつまでも続く数」だと見なした上で、じゃあこの「ゼロに9がいつまでも続く数」っていったい何だろう? と悩んでしまうパターンなのです。残念ながら、この悩みは、実はどれだけ悩んだところで決して答えが出てこないものなのです。なぜか? それは、「・・・」のくっついた数について、私たちは何も定義をしていないから。だから、定義していないモノについていくら悩んだところで、それが何であるか、絶対に分かるはずがないのです。

 

 「・・・」の記号自体は、上で述べたとおり、本来書かれてあるものの省略を意味したり、いつまでも続くことを表す記号であると考えて問題ありません。ですが、この記号を使って書いた「0.999・・・」の表記には、何も定義を与えていなかったのでした。これが迷いの原因だったのです。

 

 したがって、今回の問題は、「0.999・・・」という表記に、次のような定義を与えることでモヤモヤが解消するはずです。

 

【定義】

 「0.999・・・」とは、次のような数列 a(n)

  a(1) = 0.9

  a(2) = 0.99

  a(3) = 0.999

  a(4) = 0.9999

  a(n) = 1-(0.1)

 を考えたときの、nを無限大にした際の収束値であると定義する。

 

 つまり、

  0.999・・・ = limn→∞a(n)

 だという定義を与えてやったわけです。

 

 気をつけないといけないのは、0.999・・・ は、数列 a(n) に含まれるどの数とも違うということです。上の定義は、0.999・・・ を、数列 a(n) の要素として定義したのではなく、数列 a(n) の「収束先」として定義したんだ、という理解が必要です。

 

 こう考えれば、結局、

  0.999・・・ = limn→∞a(n)

         = limn→∞{1-(0.1)

         =

 というふうに、等式の成り立つことが言えます。

 

 

 (数学にかぎらず、)定義をしてない問題についてウダウダ悩んだところで、答えは絶対に出て来ないですよ、というのが今日の言いたかったことです。


 

2005年08月18日

謎解きクイズ

なんとなあく、謎解きクイズを思いついたので、以下に出題。

 

~~~~~~~~~~~~~~

 

 なたと影は、昼と夜。

 熊のわっかに、別のすっぽん。

 車は首が回らず、花は夜咲く。

 心があるなら、魚も然り。

 

 では次の子は、何なのか?

 

~~~~~~~~~~~~~~

 

 上記の詩から導かれる言葉とは何でしょう?

 答えをひらがな3文字(あるいは漢字1文字)で。

 

 あまり深く考えないほうが良いかもしれません。ごめんなさい。

 分かったよ、という方はコメント欄へ、ぜひどうぞ。

2005年08月25日

吟遊詩人のなぞなぞ

 謎解きクイズを思いついたので出題です。

 

~~~~~~~~~~~~~~

 

 吟遊詩人はうたう。

 

 ぼくを見あげるのは勤勉者。かれの右の右の右は訛り者。

 ぼくを見くだすのは道楽者。かれの左の左の左は哲学者。

 

 涼しいあいつは、だれの上?

 

~~~~~~~~~~~~~~

 

 上の詩から導かれる言葉とは何でしょう?

 とある知識が必要な問題です。

 

 分かった方はコメント欄へ、ぜひどうぞ。

 「分かったよ」というコメントだけでも大歓迎です。

2005年09月03日

日能研の広告をアラ探し

 電車に乗っていると、日能研の広告をよく目にします。

 ご存知の方も多いと思いますが、この広告、中学の入試問題を出題していて、この問題の正解はウェブサイトまでどうぞ、みたいなことが書いてあります。ついつい通勤時間中、見入ってしまいます。

 その中で、すごく気になった問題を2問紹介です。

 

---------------------------------------------------

 

【8月:算数】

 駅とけんたくんの家は400m、小学校とけんたくんの家は300mはなれています。駅と小学校は何mはなれていますか。

 次のア~オから考えられるものをすべてえらび、記号で答えましょう。

 ア.100m、 イ.300m、 ウ.500m、 エ.700m、 オ.900m


 

 日能研1


 (クリックで拡大)


---------------------------------------------------

 

【9月:算数】

 ○×クイズをしました。1題10点で10題です。A君、B君、C君の解答と得点は以下のとおりです。これについて、問に答えなさい。

     1 2 3 4 5 6 7 8 910 得点

 A君 ○○×××○○×○× 80点

 B君 ×○×○×××○×× 20点

 C君 ○○○×○○○×○○ 70点

 問 C君が、確実に不正解であるといえる問題が1題あります。その問題番号を答えなさい。


 


 日能研2


 (クリックで拡大)


 

---------------------------------------------------

 

 下記に、出題元サイトの解説ページのリンクをはっておきますが、ぜひどうぞ、いちど軽く考えてみてからクリックしてください。

 → 8月の問題の解説

 → 9月の問題の解説

 ・・・どうやら、このリンク先にあるような解答が、マルとみなされる解答のようです。

 さて、いまの自分がもし受験生だったら、こんな解答を書いていたかもしれません。

 

---------------------------------------------------

 

【8月:算数】

 ア~エはあり得る。

 オについても、可能性は低そうだが、もし下のような配置だったら、駅と小学校が900mはなれていることはあり得る。

 

 ――――― けんた君の家―――――小学校

   ←400m→←―200m―→←300m→

 

 したがって、答えはア~オのすべて

 

---------------------------------------------------

 

【9月:算数】

 問題文は「C君が、確実に不正解であるといえる問題が1題あります」という命題が真であると認めている。これを利用する。

 たとえば、問4と問8に対する3人の解答を見てみると、

 

     1 2 3 5 6 7 910

 A君 ○○×××○○×○×

 B君 ×○××××××

 C君 ○○○×○○○×○○

 

 どちらも×○×という組み合わせである。したがって、問4と問8はこの問題の答えではない。なぜなら、もし問4と問8のいずれか一方がこの問題の答えだとすると、もう一方もこの問題の答えでなくてはならず、「この問題の答えは1つ」と認めていた問題文の事実と矛盾するからである。

 同様に、問1と問6と問7と問9も、この問題の答えではない(3人の解答はどれも○×○)。

 同じく、問3と問5と問10も、この問題の答えではない(3人の解答はどれも××○)。

 したがって、この問題の答えは、残った問2

 

 (この問題、問題文の「1題」という箇所が完全に余計ですね。)

 

---------------------------------------------------

 

 大人げないよ、とツッコミを食らいそうです。


 最後に、このような解答に気が付いてから思ったのは、

 あらかじめ敷かれた思考の道すじをうまくたどれることが、良くも悪くも、入試でマルをもらう近道なのだなあ

 ということです。

2005年09月17日

タイトル少し変えました

 アメーバブログには、各ジャンルごとに、人気のあるブログのランキング集計を行っています。

 

 ランキング


 (クリックして拡大)

 

 なんとなくこのランキング上位の一覧を見ているうちに、ふと、あることを発見しました。

 どうやらこれら上位のブログには、共通したとある特徴が潜んでいるようなのです。

 それは、

 

 タイトル名称の頭7文字だけ見れば、そのブログの特徴が類推できる。

 

 それは本当なのか?

 実際の上位ランク入りしているブログから、タイトル名称の頭7文字を抜き出してみました。

 

1位 コロコロザイー

2位 ドクター鈴木・めぶろ研究室

3位 eラーニングで豊かになった私の人生 -eラーニングで夢を持つことができた私-

4位 神戸ではたらくウーマンのblog

5位 数楽者のボヤキ・ツブヤキ・ササヤキ

6位 教育制度あれこ

7位 特許の基礎知識

8位 コリアンライフスタイルーその実状は?!-

9位 明治のフウケイ

10位 dreamtale日記

11位 大学という斜陽産業

12位 岡田真奈美のお天娘ブログ

13位 私たちの哲学 ~読まねば死ぬ~

14位 白衣の天使にはなれません?

15位 学校へ行かないということ。

16位 ザ・コーチ ~夫育て日記~

17位 窓際大学院生のたまには真面目に生きよう。

18位 ザツガクナビー

19位 *私の医療事務記録帳*

20位 ☆独断教育日記 Z

21位 自由の女神になりたくて。(ニューヨークの果てに・・・)

22位 NHK「ドラマで楽しむ英会話」で楽しむ

23位 ROAD TO 国家公務員

24位 研究室の青いバ

25位 kadamの東大受験日記

26位 奇跡の情報起業成功戦略研究所

27位 教師をしながら弁護士になる

28位 公務員試験応援ブログ by 喜治塾・五十嵐

29位 雑学大典

30位 41歳から始めるファイナンシャルプランナーの資格試験への奮闘記

 

 ・・・どうでしょう?

 全部が全部そうだと言うわけではないですが、頭7文字だけ見れば、そのブログのだいたいの内容は推測できるんじゃないでしょうか?

 

 なぜこんなふうに推測できるかというと、こうしたブログが、自身を特徴付けるフレーズ(たとえば主眼のテーマや、作者の職業など)を、前の方に配置しているからです。

 

 では、なぜ」文字なのか?

 これは、アメーバブログの、新着記事一覧をみると分かります。

 

 新着記事一覧


 (クリックして拡大)

 

 新着記事一覧とは、だれがが新規に記事を書いたとき、自動的にそのブログへのリンクが掲載されるトップ上のスペースのことです。人の出入りが非常に多いので、多くの人がここに掲載されたリンクを目にすることになります。

 

 ・・・分かりますか? ブログ名称が 頭の7文字で打ち切られている ことが分かると思います。


 

 つまり、新着記事一覧を目にした閲覧者は、この7文字だけでそのブログを見るか否かを決定しているのです。だからこの部分が中身の薄い単語だったりすると、閲覧者は「なんかピンと来ない」と、クリックしないことを選んでしまうわけです。

 

 というわけで、結論。

 ブログのタイトルは意外と重要。最初の7文字でブログの特徴をしめすと効果的かも。

 


 

(補足1:ブログ名称が8or9文字の場合は、7文字ルールは適用されずにフルの名称が表示されるようです。)

(補足2:というわけで当ブログも、内容の薄い「週報」を後ろに移し、全体も9文字に収めました。)

2005年10月15日

評論文ふうのパズル

 ふうっとした拍子に、謎解きクイズを思いつきました。

 現代文の試験問題のような雰囲気のパズルです。

 本文を読んで、下記の問に答えてください。

 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

【本文】:

 かれは苦渋のなかにいて、始終、それがはらむ二重苦について、それほどの重視をしていなかったのである。自由という句は、その後も、氏が産したというアイデアにきわめて似かよったままだった。その(  )については、あらためてこれまでの例をあげるまでもない。

 

【問】:


 本文中のカッコにあてはまる最も適当な語句を、漢字2字で答えよ。

 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

 簡単だったらごめんなさい。

 分かったという方は、コメント欄まで、ぜひどうぞ。

 「分かったよ」というコメントだけでも大歓迎です。

2005年11月04日

生命科学をコンピュータにたとえて説明する試み


? 生命科学の用語を、コンピュータにたとえて説明できないものかな、という思いつきです。

 

 コンピュータの入門の書籍を見ていると、コンピュータの各部分を、僕たちの身の回りのものにたとえて説明していることが多いです。たとえば、メモリの量=仕事机の広さ や、CPUのクロック数=頭の回転のはやさ という具合ですね。つまり、読者にとって馴染みのある物の知識と比較させることで、理解をスムーズにしようとしているわけです。

 

 これと同じようにして、コンピュータの知識がある人を対象にして、生命科学の用語をうまくコンピュータ用語にたとえて説明できないものかな? と思いました。

 

 たとえば、染色体、遺伝子、DNA、ゲノムなど。あまりによく耳にするこれらのキーワードですが、はたしてこれらの言葉の意味をきちんと把握できているでしょうか?

 

 そういうわけで、説明の試みということでチャレンジしてみます。とはいうものの、僕自身もこれらの用語を付け焼き刃で学習したこともあって、誤解を含んだ説明文になっている可能性が大いにあります。あるいは、たとえの宿命のためか、僕の表現能力のなさのためか、明らかなウソが紛れているかも。その場合はぜひお知らせください。

 

---------------------------------------------------

 

HDD
■ 細胞の核をHDDにたとえてみる

 

 コンピュータにとってハードディスクドライブ(HDD)は、コンピュータがさまざまな仕事をするのに必要な情報がたくわえられた、とても重要な装置です。

 

 同様に、人間や他の生物にとって、さまざまな生命活動をする上で必要な情報がたくわえられた物体は、細胞の「」がそれにあたります。核の中には、生命の設計図ともいえる遺伝情報が含まれており、生物にとってとても重要な物体です。

 

 今回、生命科学を考える上で欠かせない、核や染色体といった用語を、コンピュータのHDDに例えて説明することにしてみましょう。

 

DNA
? ■ 染色体と塩基

 

 HDDを分解してみたことがある人はあまりいないかもしれません。コンピュータのHDDは、通常、頑丈な金属のケースで覆われています。ドライバーでねじを外して中身を見てみると、中には金属製の円盤があります。この円盤は「プラッタ」と呼ばれています。たいてい、パソコン用のHDDには、1~4枚のプラッタが入っています。コンピュータにとって大事な情報は、このプラッタに書き込まれています。

 

 細胞の核の中にも、プラッタと同じような物体があります。細胞にとってのそれは「染色体」と呼ばれます。プラッタの形は円盤状でしたが、染色体は、アルファベットのX(エックス)のような形をしています。1つの核のなかに、23個の染色体が入っています。

 

 プラッタの話に戻りましょう。先に述べたように、プラッタにはたくさんの重要な情報が記録されています。いったいどのように情報を記録しているのでしょうか? 実はプラッタは、ものすごく小さな磁石をたくさん持っています。磁石にはS極とN極がありますね。このS極とN極がどういう順番で並んでいるかによって、プラッタは情報を表現しているのです。

 

 では染色体の場合はどうやって情報を記録しているでしょうか。染色体を詳しく分解してみると、染色体は、「DNA(デオキシリボ核酸)」と呼ばれる細長い分子と、ヒストンなどのタンパク質からできています。このDNAは、糖やリン酸のほか、「塩基」と呼ばれる物質をすごくたくさん持っています。塩基の種類は4種類。アデニン(A)、チミン(T)、グアニン(G)、シトシン(C)です。さっきのプラッタの場合ではS・Nの2つの極の並びで情報を表現していましたが、DNAの場合は、A・T・G・Cの4つの塩基の並びで情報を表しているのです。染色体には、これらの文字が全部で約30億個も並んでいるとされています。

 

■ ゲノムと遺伝子

 

 最後に、ゲノムという言葉についてです。ゲノムというと最近よく耳にする反面、すごく難しそうな言葉に聞こえます。ですが、ゲノムという言葉は、単純に、「HDDの全データ」という言葉とそっくり置き換えてしまってもよいかもしれません。30億個すべての文字の並びが表す情報のことを指してゲノムと呼びます。

 

 ゲノムの中には、生物の親から子へ受け継がれていく、遺伝的な特徴を表した部分があります。この部分を「遺伝子」と呼んでいます。これはコンピュータに例えるのが難しいですが、HDDのデータの中でも特にそのコンピュータの特徴を表す部分、たとえばブートレコード(パーティション情報などを示す部分)や、ブートセクタ(OSの呼び出し方などを示す部分)に相当する部分、と言えるかもしれません。ちょっとこの辺は例えが破綻してきています。ごめんなさい。

 

 そういえば、2003年に、国際チームが「ヒトゲノムの配列を完全解読した」という宣言を出しました。これを、コンピュータのたとえ話で見てみると、なんか得体の知れないHDDがあったけど、その中身を解析してみて、ようやく全部の0と1の並び方が分かったよ、というようなことを言ってるわけです。でももちろん、それだけではそのコンピュータがどんな仕事をするのかを理解できたとは到底言えないわけです。どの部分がどんな機能を持つのか。そしてさらに国際チームの結果によれば、ヒトのゲノムのうち遺伝子の部分は2~3%程度だということが分かったそうだけど、じゃあ遺伝子のそれぞれはどんな役割があるのか? それ以外の部分は? などなど、いろんな疑問が湧き上がってきています。

 

---------------------------------------------------

 

 ちょっと最後は苦しい感じになってきていますが。。こんな感じで説明できるかな? という試みということで。

 いくらなんでもその説明はまずいだろう、みたいな点を見つけた方はぜひお教えください。

 

2005年12月04日

ブロック状のパズル

←

 

・

 

→

 

 

 あなたには感じることができましたか?

 

 感じた! という方は、コメント欄まで、ぜひどうぞ。

2005年12月20日

科学ニュースサイト RSS リンク集

 つい先日に Thunderbirdというメーラを導入して以来、RSS リーダの機能に惚れこんでばかりです。
 
 ひとまず僕はニュースサイトの閲覧用にこの機能を使っているのですが、これにかぎらず、たとえば、毎日あちこちのブログを更新チェックするのが面倒、などという方にはぜひ導入をおすすめです。
 
     Thunderbird
     (クリックで拡大)
 
 更新があったサイトの記事を、まるで新着メールを開くような感覚で閲覧することができるのですね。
 
 RSS リーダ機能の使い方は Thunderbird のヘルプを参照していただくとして、ここでは様々な科学ニュースサイトの RSS を一覧にしてご紹介です。あるいは自分用のメモとして。
 
【国内サイト】
 
● Nature Publishing Group Highlights
 http://www.natureasia.com/japan/rss.rdf
● WIRED NEWS
 http://hotwired.goo.ne.jp/news/index.rdf
 
【海外サイト】
 
Scientific American(サイエンティフィク・アメリカン誌)
 - Official RSS Feed
 http://www.sciam.com/xml/sciam.xml

Science online(サイエンス誌)
 - ScienceNOW
 http://sciencenow.sciencemag.org/rss/current.xml

nature.com(ネイチャー誌)
 - Nature Publishing Group RSS Newsfeed
 http://www.nature.com/news/rss.rdf

New Scientist(ニュー・サイエンティスト誌)
 - Latest Headlines
 http://www.newscientist.com/feed.ns?index=online-news&type=rdf

BBC News(英国放送協会)
 - Science/Nature
 http://newsrss.bbc.co.uk/rss/newsonline_world_edition/science/nature/rss.xml
 - Technology
 http://newsrss.bbc.co.uk/rss/newsonline_world_edition/technology/rss.xml

CNN.com
 - Science and Space
 http://rss.cnn.com/rss/edition_space.rss
 - Technology
 http://rss.cnn.com/rss/edition_technology.rss

ABC News
 - Health
 http://my.abcnews.go.com/rsspublic/health_rss20.xml
 - Technology
 http://my.abcnews.go.com/rsspublic/scitech_rss20.xml

Popular Science(ポピュラー・サイエンス誌)
 - topstories Channel
 http://rss.popsci.com/web/popsci/rss/topstories/index.xml

Science A GoGo
 - Science News And Reseach
 http://www.scienceagogo.com/science_news.xml

ABC Science Online(オーストラリア放送協会)
 - News in Science
 http://www.abc.net.au/science/news/xml/abc_news_in_science.xml

PhysOrg.com
 - The latest physics and technology news
 http://www.physorg.com/physorg.xml

Reuters(ロイター)
 - Science
 http://feeds.feedburner.com/reuters/scienceNews/
 - Technology
 http://feeds.feedburner.com/reuters/technologyNews/
 - Health
 http://feeds.feedburner.com/reuters/healthNews/

 

2006年01月04日

紙の上の確率の問題

 お正月のあいだ、とある問題を実家のこたつの中で思いつき、そのまましばらく考えていたものの、結局答えが出せずギブアップしました。

 

 

【問題1】

 正方形の紙を用意する。この紙の上に、ランダムに2箇所の点を選び、これらを線分で結ぶ。このような線分を2本作るとき、これらが交差しない確率はいくらか?

 

【問題2】

 今度は、正方形の紙の上に、ランダムに3箇所の点を選び、これらを線分で結ぶ。このようにしてできた三角形が鋭角三角形となる確率はいくらか?

 

 

 問題1のほうは、シミュレーションを組んでみた結果、およそ 0.75 前後の値であることが分かったものの、1も2も、厳密な答えの導出はちいともできる気配がありません。

 

 こうしたらいいんじゃないか、という方や、類似問題を知っている、という方は、ぜひコメント頂けると幸いです。

2006年01月14日

老人と5人の男のクイズ

 5人の男たちが、老人のもとを訪れた。

 

---------------------------------------------------

 

老人 「遠い国からよく来た。私は、過去に秩序をもたない者しか選ばない。お前たちから私に言葉を与えよ。」

 

「その前に座ってもよいでしょうか。」

「それよりまず水を飲ませてくれ。あとそれと食べるものも。」

 

老人 「ああ、よい。お前たちはちゃんと知っているな。」

 

「あなたは何かを隠していると思うんだが・・・。」

「俺もそう思う。だがそれは何を意味しているんだ?」

 

老人 「素晴らしい。お前たちも理解したようだな。」

 

「あなたはいつもこんなふうに、訪れた者を試しているのだろう?」

 

老人 「・・・だめだ。お前からは何も感じない。早くここから去れ!」

 

---------------------------------------------------

 

 さて、なぜEだけが老人から拒否されたのだろう?

 理由を考えてください。


 


 分かった!という方は、コメント欄へ、ぜひどうぞ。


 「分かったよ」というコメントだけでも大歓迎です。

2006年02月11日

アメブロの全記事を一括表示するスクリプト

 綺麗山さんのところのブログで、「過去のブログの記事を検索用に一括表示したい」ということが書かれてありました。(しんりの手 fc2【ブログの実験】検索用として過去の文章を一括表示

 

 これは僕も困ってた問題でした。というのも、アメブロの検索機能があまりにイケてなくて、期待したページがちゃんと拾えていなかったのです。

 

 そこで作ってみました。アメブロの全記事を一括表示するスクリプト

 アメブロIDを入力すると、ブログ内のすべての記事を取得・表示します。

 

 このページ
に行って、ダウンロード・解凍してできた「ameblo.html」を、Internet Explorer 6 のウィンドウの上にドラッグ&ドロップ。

 コンテンツ表示を許可した後、テキストボックスに、一括表示したいブログのアメブロIDを入力し「取得」を押す。

 コンテンツを許可

 コンテンツを許可(クリックで拡大)

 アメブロIDを入力

 アメブロIDを入力して「取得」

 

 全記事を一括表示

 全記事を一括表示

 

 適当なフォルダに保存した後で、ショートカットをお気に入りに登録しておくと、けっこう便利です。


 表示されない or エラーが出たなどあったらごめんなさい。改良点・追加要望などあれば、ぜひコメントいただけるとうれしいです。

2006年03月09日

熟語たちのクイズ

 ある規則にしたがって、熟語が下に並んでいます。

 さて、□□には、どんな言葉があてはまるでしょうか?

熟語たち ?

 (↑クリックで拡大)

 

 □□にあてはまる熟語はたくさんあります。

 「わかったよ!」という方は、そのうちの一つを、コメント欄までぜひどうぞ。

 

2006年08月01日

ブログオフ会に行ってきたよ

? この記事を雑念レポートのテーマに分類してしまうことをお詫びしつつ。

 この前の日曜日に開催された、異業種オフ会に参加してきました。

 平素からお世話になっている心理学院生の綺麗山さん
の主催。夏休みということでアメリカから日本へ戻っていらっしゃっていたのでした。ありがたい機会に浴することができてたいへん感謝です。:)

 

 参加者はほか、獣医学生、僕の元同僚の統計解析院生、さらに僕(IT研究開発)と妻の計5人ということで、それはもう様々なジャンルの方々との集まりになったのでした。

 

 というわけで、色んな方向に話題も移りつつ、とても刺激的で楽しい時間を過ごすことができました。動物の解剖の仕方、統計解析のレクチャー、脳の話、見やすいウェブページ、グーグル、英語と日本語の変換、・・・と、すべてを書き上げようとすると大変な労力が必要になりそうな勢いです。

 

 印象的だったのは、海外在住経験者とそうでない人との間で、トークへの関わり方が違って見えたのが面白かったなあ。僕みたいな典型的日本人タイプだと、うんうんと聞きながら時々言葉を差し挟むという感じだけど、ぽんぽんと言葉を投げかけるようなスタイルに意識して少しシフトしてみるのも面白いなあ、と思ったよ。

 

 僕個人としては、言葉や話題の選びかたなど、後になってから反省するところもあり、酔った勢いに免じて水に流して下さることを切に願っています;

 

 幹事の綺麗山さんと皆様に感謝しつつ、またこんな機会があれば喜んで首を突っ込みたいなあと強く感じたのでした。

2006年10月13日

アメブロからのお引越し検討中

青  現在、アメーバブログからのお引越しを考えています。

 

 理由はわりと単純です。リニューアルのたびに、ブログ本体や管理者メニューのレイアウトが半強制的に変化させられてしまうというのが主な理由です。たとえば、管理者メニューの構成が変わっていたり、記事投稿画面に新しいボタンがついていたり。もちろん、管理者メニュー程度なら、そのたびに変わった内容を管理者のほうで頭に入れておけば問題ないのですが、ブログそのもののレイアウトも勝手に変えられてしまうというのがかなり困ります。いちおう、設定の変更で元に戻せるのですが・・・管理者メニューのGUIからは無理で、CSSファイルの手打ち修正でしか変更できないというのも厄介な点です。

 

 今回、強制的に表示させられることになったのは、管理者のプロフィール写真や、アメーバブログのユーザ同士の読者登録ボタンなど。何が何でもユーザ同士でコミュニケーションしてもらうぞ、というアメーバブログの意思が強く感じられます。あからさまにユーザの囲い込みを狙ってるわけで、そのためには強制的なレイアウト変更もやむをえない、と言ってるかのように感じます。

  

 というわけで、アメーバブログから引っ越して別の場所に移ろうと思い立ったのですが・・・、ここで、過去の古い記事はどうするのか?という問題に直面してしまいました。

 

 A案 : 旧ブログの内容を新ブログにコピーし、旧ブログは全削除。

 B案 : 旧ブログの内容を新ブログにコピーし、旧ブログはそのまま残しておく。

 C案 : 旧ブログはそのまま残しておき、今後の記事のみを新ブログに書く。

 D案 : 旧ブログの内容を新ブログにコピーし、旧ブログの内容を新ブログへの誘導リンクに書き換える。

 

 当ブログの各記事にリンクを貼って下さっている他ページのことを考えるとA案はナシ。記事を二重化するB案は悪くはないけど、たとえば旧ページの内容を修正したいときに新旧両方のページを更新しないといけなくなり、これもできれば避けたい。C案はよさげだけど、過去と現在の記事が複数のブログに分断されることになり、記事検索などでやや不便。

 

 となると残りはD案。

 もちろん、手作業で記事をひとつひとつコピーペーストしていくのは耐えられないので、これよりはマシな方法をとりたいです。ブログのフォーマットとして標準的な MovableType の形式でエクスポート(書き出し)してくれたら嬉しかったのですが、アメーバブログはその機能をサポートせず(当然)。そういうわけで、ここしばらくは、お引越し方法の検討のために更新が稀になるかと思いますが、何卒ご容赦ください。m--m

 

 あと、過去に作った「アメブロの全記事を一括表示するスクリプト」をちょこっと手直ししたのでダウンロード先を再掲しておきます。全記事表示の完了後、右クリック→「ソースの表示」で、記事の保存ができるようになりました。このスクリプトをベースに、お引越し用のが書けたらいいな。

?

■ アメブロの全記事を一括表示するスクリプト

 http://liver.ld.infoseek.co.jp/ameblo/index.html

 ?

2006年11月18日

商標ふうの暗号パズル

ふうっとした拍子に暗号パズルを思いついたので出題です。
下記に挙げた英語名は、一見するとどこかの商標か何かのように見えますが、実はすべてある法則に沿っています。

・FOOT-PLAN
・EAGLE-BAY
・COW-LUCK
・GOLD-SHORE
・SILVER-ENGINEER
・NEW-LION
・HALF-BRIDGE
・BOOK-□□□□

その法則に従うならば、最後の空欄にあてはまる英単語とは一体何でしょうか?

分かったよ! と言う方はコメント欄へぜひ回答をどうぞ。
「分かったよ」だけでももちろん大歓迎です。

2007年11月04日

三人の追っ手


 私を追うのは三人の男。
 みな近くまで迫っていた。
 私は逃げ続け、南の果てまで来ていた。
 もう終わりにしたい。西に送られるなんて真っぴらだ。
 
 彼らにはこれが最後のチャンス。
 私が望んだのは普通の平和だったのに。
 こんなときに限って鳥は川を流れない。
 まして竹を四本も待つなんて愚かしい。
 
 瞬間、何が起きたのか分からなかった。
 気づいた時には私は彼らの一人に銃を打っていた。
 まん丸い一つの弾はそいつの頭の片方に当たって刻まれた。
 そいつは短い叫び声をあげた。
 そいつは私の親だった。
 そいつは跳ねて笑っていた。
 
 もう西にすら行くことはできない。
 私は多くを失った。
 

 
 
 
 あなたに問いたい。
 そのときそいつが何て叫んだのか、分かるかい?

2009年08月11日

プロジェクトオイラーを遊び倒すガイド(導入編)


 ここしばらく更新が滞り気味でごめんなさい。更新が少なかったのは、数ヶ月ほど前にプロジェクトオイラー(Project Euler)なるサイトの存在を知り、すっかり病みついてしまったためです。そこで今回は趣向を変えて、プロジェクトオイラーの面白さを4回に渡って紹介したいと思います。

プロジェクト・オイラーとは何か?

プロジェクトオイラーとは、プログラミングで解く数学の問題集のサイトです。

出される問題はいずれも、単に数学の知識だけでは解けないようになっています。コンピュータを使ってプログラミングすることで初めて答が得られるようになっています。数学的な素養とプログラミング技術の両方が要求されます。

問題は現時点で252問あり、現在も週1のペースで増えています(ただし8月末まで休み)。参加者はユーザ登録すると、問題リスト(難易度の順番に並んでいます)の好きな問題から解くことができます。プログラミング言語に制約はありません。答さえ出せれば、どんな方法を使って解いてもかまいません。

サイトには参加者のランキング(こちら)が掲載されています。ランキングは正解数で決まります。同数なら早い者順です。

上位陣はみなもちろん全問正解しています。毎週末に新作問題が発表されると、1番乗りを目指して静かな戦いが繰り広げられるという感じです。

やってみよう

参加はメールアドレスを登録するだけと簡単です。国と使用するプログラミング言語を自己申告します。日本人の参加者は600名ほど。使用言語は C/C++ が最も多く、Python、Java がその次に多いです。

問題はすべて英語ですが、有志による 日本語訳 wiki で内容は分かると思います。

始めのうちは、手の付けようのなさに戸惑うこともありますが、問題を重ねるうちに、プログラミングの基本や数学的な思考法が自然と身についてきます。夏休みの頭のトレーニングに、プログラミングの勉強に、ぜひ取り組んでみてはいかがでしょうか。

次の記事(初級編)では、どんなふうに問題を解いていけばよいのか、実際を模したオリジナル問題をつかって見ていきたいと思います。

【参考リンク】
濃縮還元オレンジニュース::数学の問題を好きなプログラミング言語で解く「Project Euler」

2009年08月12日

プロジェクトオイラーを遊び倒すガイド(初級編)


前回の導入編では、プロジェクトオイラー(Project Euler)の概要を紹介しました。本記事では、実際にどんなふうに問題を解いていくか、その様子を述べてみようと思います。

それではさっそく問題にトライしてみましょう。本来なら、実際の問題を使うところなのですが、ネタバレはできるだけ書きたくないので、実物を模したオリジナル問題を3つ(初級、中級、上級)作ってみました。これを題材に、プロジェクトオイラーへの取り組み方を見ていきましょう。

初級編はこんな問題です。

【初級問題】 よく知られているように、2は1番目の素数であり、3は2番目、5は3番目、7は4番目の素数である。 n 番目の素数 p に対し、n もまた素数である場合に、p を「素数番目の素数」と呼ぶことにしよう。 3と5は素数番目の素数だが、2と7はそうではない。 100万以下の素数番目の素数の総和を求めよ。

素数をテーマにした問題です。プロジェクトオイラーでは、素数をあつかう問題がとてもよく出されます。

初級編を解いてみよう

さて、この問題はどうすれば解けるでしょうか? ぱっと考える感じ、条件に合う素数をすべて見つけて、順に足し算してやればよさそうです。そこでまずは100万以下の素数をすべて求めて、何番目かを先頭からチェックしていく、というアプローチで進めてみましょう。

100万以下の素数をすべて求めるにはどうすればよいでしょうか? 素数のリストを求めるアルゴリズムとしてよく知られた「エラトステネスのふるい」が有効そうです。これを使って求めてみましょう。

エラトステネスのふるいについてはウィキペディアの記事(これ)を参照して下さい。まず100万以下の整数を羅列して、2の倍数をすべて消す、3の倍数をすべて消す、4の倍数をすべて消す・・・という作業を1000まで繰り返します。最後までやると、素数のみが消えずに残るというしくみです。

こうして得られた素数のリストを、n の値を1ずつ増やしながら順にたどり、n が素数であれば和に加えます。n が素数かどうかの判定には、いま作ったふるいがそのまま利用できます。

結果は次の通りです。

結果、3475059124 という答が得られました。実際にはこのあと、問題ページにあるテキストボックスに回答を入力し、正解かどうかをチェックします。みごと合っていれば、正解アイコンが現れます。

初級編はわりと単純な問題でした。次の中級編では、ひと工夫が必要な、より難度の高い問題にトライしていきます。

2009年08月13日

プロジェクトオイラーを遊び倒すガイド(中級編)


今回は、初級編からさらに一歩進んだ難度の問題を解いてみます。中級編の問題はこれです。

【中級問題】 344 という数は面白い性質を持っている。 344 の平方根を小数表示した √344 = 18.547236990・・・ は、小数点を無視すると、先頭の9桁に1から9までの数字がちょうど一度ずつ現れる。344 はこのような性質を持つもっとも小さな整数である。 31078 もこの性質を持つ。√31078 = 176.28953457・・・である。31078 はこの性質を持つ10番目に小さな整数である。 この性質を持つ160万番目に小さな整数を求めよ。

初級編と比べて、すこし複雑になりました。うまく解くにはいくらか工夫が必要になります。

単純なアプローチではうまくいかない

さて、この問題はどのように解けばよいでしょうか?

単純に考えると、344 以上の数について、片っぱしから、条件を満たすかどうか調べるやり方が思いつきます。まずはこの方法でやってみることにしましょう。

条件を満たしているかのチェックには少しプログラミングの腕が必要です。ここでは、C 標準関数の sqrt() を使って平方根の小数表示を得たあとで、整数部分が9桁になるまで小数点を右に移動させ、それを unsigned int 型にキャストして小数部分を落とします。次に1~9の各数字が使われたかを記録する bool 型の配列を用意して、各桁が他と重複していないか調べます。どれも重複していなければ、条件を満たしていると判定します。

以上の手順をコードに書きました。is_root_pandigital() という関数で、平方根が条件を満たすかのチェックを行っています。また、count という変数で、見つかった個数をカウントしています。count が 10000 増えるごとに進捗状況を出力させています。

#include <stdio.h>
#include <math.h>
#define N 1600000

bool is_root_pandigital(unsigned int n)
{
  double r = sqrt((double)n);
  while (r < 100000000.0) r *= 10.0;
  unsigned int m = (unsigned int)r;
  bool b[10];
  b[0] = true;  // ゼロは現れてはならない
  for (int i = 1; i < 10; i ++) b[i] = false;
  for (int i = 1; i < 10; i ++) {
    if (b[m % 10]) return false;
    b[m % 10] = true;
    m /= 10;
  }
  return true;
}

int main(int argc, char* argv[])
{
  int count = 0;
  for (unsigned int n = 1; ; n ++) {
    if (is_root_pandigital(n)) {
      count ++;
      if (count % 10000 == 0) printf("%d %u\n", count, n);
      if (count == N) {
        printf("%u\n", n);
        break;
      }
    }
  }
  return 0;
}

さて、コードを実行してみましょう。

3分後の出力が上です。見ての通り、たった17万個しか見つかっていません。このペースだと、160万番目が見つかるのは約半時間後ということになってしまいます。

ここで、プロジェクトオイラーのもう一つの重要なルール、「1分ルール」について説明します。1分ルールというのは、「工夫したプログラムを書けば、たとえ低速なマシンでも1分以内の実行時間で正答を得ることができる」という原則のことです。プロジェクトオイラーで出題される問題は、すべてこの原則にもとづいて作成されています。

つまり、上のような何十分もかかるプログラムは、出題者の期待するレベルに達していないということです。

ではどうすればよいか? 一つは、ひたすらプログラムの完了を待つというものです。もちろん、これでも正答を得ることは可能ですし、こうしたやり方が禁止されているわけではありません。ですが今回はせっかくですので、1分ルールを満たすようにプログラムを改良してみましょう。

改良:固定する数を変える

とは言っても、一体どこをどう改良すればよいのでしょうか? 整数をしらみつぶしに探すというさきほどのアプローチは非効率すぎたわけです。発想を変えましょう。整数を選ぶのではなく、「先頭に1~9が一度ずつ現れる数をまず固定する」と考えてみましょう。

どういうことか? 17923.4658 という数を例にとります。これは先頭の9桁に1~9が一度ずつ現れる数です。ここで、「平方根が 17923.4658・・・ となるような整数は何か?」と考えるのがこのアイデアのポイントです。このような整数を探すのは容易です。17923.4658 ≦ √n < 17923.4659 を満たすような整数 n を探せばよいわけです。各辺を2乗すれば 321250626.28376964 ≦ n < 321250629.86846281 ですから、そのような n は 321250627、321250628、321250629 の3つだと分かります。

つまり、先頭に1~9が一度ずつ現れる数を小さい順に生成し、それぞれに上の手続きを使って n を求めればよいということです。

以上の内容をプログラミングしました。1~9が一度ずつ現れる数を小さい順に生成するのは少し大変ですが、順列生成としてよく知られた手順ですので、自作したり、うまくネット上のコード(ここなど)を再利用したりして下さい。下記では STL の next_permtation() を使いました。

また、同じ数を重複カウントしてしまわないように、未カウントの最小の整数を n_next に記録しました。

#include <algorithm>
#include <stdio.h>
#define N 1600000

int main(int argc, char* argv[])
{
  int count = 0;
  for (int d = 100000000; d > 0; d /= 10) {
    char c[] = "123456789";
    unsigned int n_next = 1;
    do {
      int m = atoi(c);
      double d0 = (double)m / d;
      double d1 = (double)(m + 1) / d;
      unsigned int n0 = (unsigned int)(d0 * d0) + 1;
      unsigned int n1 = (unsigned int)(d1 * d1);
      if (n0 < n_next) n0 = n_next;
      for (unsigned int n = n0; n <= n1; n ++) {
        count ++;
        if (count % 10000 == 0) printf("%d %u\n", count, n);
        if (count == N) {
          printf("%u\n", n);
          goto end;
        }
        n_next = n + 1;
      }
    } while (std::next_permutation(c, c + 9));
  }
end:
  return 0;
}

実行結果は次のとおりです。

一瞬で答え 3951343689 が得られました。

と、発想を変えるだけで、圧倒的に早く答を得られるようになったことが分かると思います。プロジェクトオイラーでは、素朴なアプローチではうまくいかず、高速化が必要になる問題が出てきます。すでに正解した問題でも、1分ルールを満たすようにアプローチを変えたり、より高速になるようプログラムを改良したりするのも面白いですね。

なお、プロジェクトオイラーでは、正解者専用の掲示板が各問ごとに設けられています。他の参加者の優れたアイデアを学んだり、自分のプログラムを披露したりするのも楽しいでしょう。

以上で中級編の説明を終わります。次回は、さらに難度が上がり、ぱっと見ただけではアプローチが思い浮かばない上級編に取り組んでいきます。

2009年08月14日

プロジェクトオイラーを遊び倒すガイド(上級編)


これまで、初級編中級編の2問を題材に説明してきました。最後は、さらに難度の上がった問題を解きます。上級編の問題はこれです。

【上級問題】 6枚のタイルが横1列に並んでいる。 いま、左端のタイル(S)上に1匹のバッタがいる。バッタは次のルールにしたがってジャンプを繰り返し、右端のタイル(G)に向かう。
・バッタは右または左方向にジャンプする。任意の枚数のタイルを飛び越え、他のタイルに着地する。
・バッタはジャンプすると、次はその反対方向にジャンプする。
・バッタはGに到着する前に、他のすべてのタイルにちょうど一度ずつ着地する。Sは始めから着地済みとみなす。
このようにGへ到着する仕方は、全部で5通りある。
20枚のタイルが横1列に並ぶとき、Gへ到着する仕方は何通りあるか?

前の2問とかなり雰囲気が異なる問題です。こうしたいわゆる数え上げの問題も、プロジェクトオイラーではよく出題されます。

さて、どうすれば解けるでしょうか。とりあえず、紙にペンで20個のタイルを書いてみるわけですが、膨大なパターンを数えないといけないことに気付きます。どう数えたらよいか、途方に暮れる人もいるのではないでしょうか。

問題をサイズダウンする

そんなときに有効な考え方として、「大きすぎる問題を小さな問題に分割する」やり方を試してみましょう。問題のサイズを一回り小さくすることによって、再帰的にパターン数を表せないか考えるわけです。

問題サイズを小さくするというのは、この場合は途中経過の様子を思い浮かべることを意味します。こうしたことを考えながら、しばらく図を眺めてみると、ある事実に気がつきます。結局のところ、Gへ着くパターン数は、「バッタの左側にある未訪問のタイル数と、右側にある未訪問のタイル数」のみによって決まっているのです。下の2つの例(訪問済みのタイルを水色で示しています)のように、バッタの左と右にある未訪問のタイル数さえ一緒なら、このあとGに着くパターン数は同じになるのです。

この事実に気が付けば、バッタの左と右の未訪問タイル数が left と right のときのパターン数を求める get_count(left, right) という関数を作ればよいと分かります。関数内では、次の一手によって場合分けして、それぞれ対応する引数で get_count を再帰的に呼んでやります。

コードは以下です。

#include <stdio.h>
#define N 20

long long get_count(int left, int right)
{
  long long count = 0;
  if (left == 0 && right == 0) return 1;
  if ((left + right) % 2 == 0) {  // 右にジャンプする
    for (int i = 0; i < right; i ++) {
      count += get_count(left + i, right - 1 - i);
    }
  } else {  // 左にジャンプする
    for (int i = 0; i < left; i ++) {
      count += get_count(i, left + right - 1 - i);
    }
  }
  return count;
}

int main(int argc, char* argv[])
{
  long long count = get_count(0, N - 2);
  printf("%I64u\n", count);
  return 0;
}

しかしながら、実行しても、何時間経っても一向に終了しません。どうやらさらにもう一ひねりが要るようです。

メモ化探索による改良

そもそも上のプログラムは、バッタの次の可能な行き先ごとに get_count を繰り返し呼びます。その先では、さらにその次の可能な行き先ごとに呼びます。つまり、計算を進めるごとに、関数を呼ぶ回数が爆発的に増えてしまうのです。これが、いつまで経っても終わらない理由です。

そこで、「メモ化探索(メモイズ)」というプログラミングのテクニックを使うことにしましょう。メモ化探索とは、過去に行った計算結果をキャッシュしておいて 同じ引数の計算に対して高速化を計ることを言います。

ある left と right の組み合わせのときの関数の結果を覚えておく2次元配列 memo を用意しました。始めに要素を -1 で初期化しておき、get_count() の先頭でキャッシュが計算済みかを調べます。改良後のコードは次の通りです。

#include <stdio.h>
#define N 20
#define UNDEF ((long long)(-1))
long long memo[N][N];

long long get_count(int left, int right)
{
  if (memo[left][right] != UNDEF) return memo[left][right];
  memo[left][right] = 0;
  if (left == 0 && right == 0) return 1;
  if ((left + right) % 2 == 0) {  // 右にジャンプする
    for (int i = 0; i < right; i ++) {
      memo[left][right] += get_count(left + i, right - 1 - i);
    }
  } else {  // 左にジャンプする
    for (int i = 0; i < left; i ++) {
      memo[left][right] += get_count(i, left + right - 1 - i);
    }
  }
  return memo[left][right];
}

int main(int argc, char* argv[])
{
  for (int i = 0; i < N; i ++)
    for (int j = 0; j < N; j ++)
      memo[i][j] = UNDEF;  // キャッシュの初期化
  long long count = get_count(0, N - 2);
  printf("%I64u\n", count);
  return 0;
}

さて、結果はどうでしょうか。

すぐに答え 2404879675441 が得られました。

さらに優れた洞察

もしあなたが、「結局これって、オイラー数(通称ジグザグ数)を求めればいいだけじゃないの?」と気づいたのであれば、さらにずっと短い手順で答にたどり着くことができます。詳しくはこちらなどを参照して下さい。

以上、3つの例題を使ってプロジェクトオイラーの問題を解いてみました。実際の問題は、これよりもずっと複雑なコーディングや、難しい数学の知識を必要とするものが多く出題されてます。ランキングの上位を狙うもよし、素晴らしいアイデアをフォーラムに投稿するもよし、いろんな遊び方を試してみてください。

最後に僕自身の思いを。プロジェクトオイラーのよいところは、解くのに制限時間が設けられていない点だと思っています。急いで答えを出すプレッシャーがなく、リラックスして問題に挑めるし、また電車内や待ち時間にぼんやりと解法を練ってもよいです。また、複雑なプログラムを細かくデバッグして、やっと正解が得られたときの満足感は、テレビゲームよりもずっと高いと思ってます。全問正解にはまだ何十問か足りませんが、いずれ世界トップにこれたらいいなあ。

(20151022追記:コードのコメントの誤りを修正しました。)

2010年07月18日

マッチ棒の並べ方パズル

 以前にこのブログにて、プログラミングで解く数学の問題集のサイト「プロジェクトオイラー」をご紹介しました。(参考:「プロジェクトオイラーを遊び倒すガイド」 導入編初級編中級編上級編

 さて、今回、出された問題を解くだけでは飽き足らず、オリジナル問題を作ってみました。興味のある方はぜひチャレンジしてみて下さい。

---
【問】
正の整数 W, H に対し、長さ 1 のマッチ棒を 2*W*H+W+H 本ならべて、横 W × 縦 H の格子状の図形を作る。
各マッチ棒の頭の向きに応じて様々な並べ方が可能である。
W=3, H=2 の場合、並べ方は全部で 22*3*2+3+2 = 131072 通りある(図形全体の回転や反転は考慮しない)。このうちの 2 つを下に示す。

ここで、次の条件を満たす並べ方に着目する:すべての格子点は、少なくとも 1 個のマッチ棒の頭を含む。
左の例は、12 個の格子点の全てが少なくとも 1 個のマッチ棒の頭を含んでおり条件を満たしているが、右の例は、青丸で囲った格子点が頭を含んでおらず条件を満たしていない。

N(W, H) をこの条件を満たす並べ方の数とする。
例えば、N(1,1)=2、N(2,1)=14, N(3,2)=7618 である。
N(120,12) mod 108 を求めよ。
---

 回答は こちら(受付終了しました)のページに行って、テキストボックスに答の8桁の数字を入力してから「回答」を押して下さい。正解なら専用の掲示板ページに飛びます。不正解なら 404 Not Found が表示されます。

 チャレンジをお待ちしています!

2010年07月30日

接点と円と三角形のパズル

 前回に引き続き、ふたたびオリジナル問題を作ってみました。今回は前回よりすこし数学寄りです。ぜひチャレンジしてみて下さい!

---
【問】
xy 平面上で、原点 O を中心とする整数の半径 r>0 をもつ円に対し、正の整数の座標をもつ円の外部の2点 X(a, b), Y(b, a) (0<a<b) から接線を引く。2点ずつできる接点のうち、x 座標の小さい方をそれぞれ A, B とする。

a2+b2<n のとき、三角形 OAB の面積が整数となる3数の組 (a,b,r) の個数を M(n) とする。
例えば、M(102)=3, M(104)=1043 である。
M(108) を求めよ。
---

 回答はこちら(受付終了しました)のページに行って、テキストボックスに答の数字を入力し「回答」を押して下さい。正解なら専用の掲示板ページに飛びます。不正解なら Not Found が表示されます。

 ふたたび、ご回答をお待ちしています!

2010年08月02日

マッチ棒の並べ方パズル(解答編)

 以前に出題したマッチ棒の並べ方パズルの解答編です。

 この問題は N(120,12) を 108 で割った余り、つまり下8桁を求める問題です。ちょっと考えれば分かりますが、いわゆる単純な総当りでは決して解けません。並べ方は全部で 22*120*12+120+12 ≒ 5×10906 通りもありますので、これらを全て列挙して数えるというのはあまりに非現実的です。

 ではどうするか? プロジェクトオイラーを遊び倒すガイド(上級編)で説明した、大きすぎる問題を小さな問題に分割するアプローチが必要になります。今回の場合は、一回り小さいサイズの問題を考えることで目的のパターン数が表せないかを考えます。

 W=3, H=2 の場合を例にします。これより一回りサイズの小さい問題、2×2 の図形に対し、下図のように、右側にヨの形の数本のマッチ棒を足してやれば、新たに 3×2 の図形を得ることができます。このとき、もし 2×2 が条件を満たしているとすると、くっつけるマッチ棒の向きを適切に選んでやれば、3×2 でも条件を満たすことが可能になります。ですので、2×2 でのパターン数が既に分かっているならば、そこに可能なヨ型のパターン数を掛け合わせることで 3×2 のパターン数が分かるのではと期待されます。さらにこの手順を繰り返せば、4×2、5×2、・・・ のパターン数も分かるのではと期待されます。

 しかし、この考えはうまくいきません。下の例を見てください。2×2 から 3×2 を作る例を示していますが、もともとの 2×2 は、右列に頭のない格子点(青丸)があり、条件を満たしていません。ですが、ここに適切なマッチ棒を足せば、条件を満たす 3×2 を作ることが可能です。このように、条件を満たす並べ方だけに着目したのでは、うまく計算できません。

 ではどうすればいいか。条件を満たす並べ方だけを追うのでなく、頭のない格子点を右列に含む並べ方も一緒に求めるという考え方が必要になってきます。右列の格子点の頭のあるなしを1つの状態とみなして、可能な状態をすべて列挙します。右列以外の格子点はすべて条件を満たします。H=2 の場合、可能な状態は下記の5つです。なお H=2 なら手書きで十分列挙できますが、H=20 の場合は、列挙の手続きもプログラミングして自動化する必要があります。

 状態の列挙ができれば、次は、横 W-1 における各状態のパターン数が与えられたもとでの、横 W における各状態のパターン数を計算します。別の言い方をすると、横 W-1 における状態1~5のパターン数を P(W-1,状態1),・・・, P(W-1,状態5) と書くとき、これらの値から P(W,状態1),・・・, P(W,状態5) を得る変換行列を考え、この各要素の値を計算します。

 この行列が作られたら、あとは初期状態に相当する P(0,状態1),・・・, P(0,状態5) を別の手段で求めて、ここに行列を W 回作用させることで、P(W,状態1),・・・, P(W,状態5) が得られます。

 以上の手続きをまとめます。

1.可能な状態を列挙する。
2.W-1 に対する各状態のパターン数から W に対する各状態のパターン数を得る変換行列を計算する。
3.W=0 に対する各状態のパターン数を計算する。
4.3に2の行列を W 回作用させる。

 この後、右列のすべての格子点が頭を含む状態の値を見れば、それが求めるべき N(W,H) の値になります。

 以下、各ステップの処理を少し詳しく見ていきます。

 可能な状態というのは、もういちど書くと、W×H のうち右列以外の格子点がすべて頭を含む状態です。右列の頭のあるなしに応じて、状態を分類します。

 実際に紙に書いてみると容易にわかりますが、隣り合う2点は必ず少なくとも一方が頭を含むため、可能な状態の数はそれほど多くはありません下記のコードでは EnumerateState() 関数で、再帰的に計算しています。なお本コードでは、各状態を表現するために、右列の書く格子点の頭のあるなしを、std::bitset を用いて上から順に1または0で表しています。もちろん好きなデータ構造で表現して構いません。

 横 W-1 の各状態から横 W の各状態へ推移するパターン数を求めます。これは少々プログラミングが複雑です。頭を含まない格子点にくっつくマッチ棒は、向きが一意に定まりますが、そうでないマッチ棒は、どちらの向きでも構わないため、可能なパターン数は増えます。下記のコードでは GetNext() 関数で計算しています。詳細は省きますが、再帰呼び出しを用いて、上から下へ、推移の前後の bitset の並びを見比べながら可能なパターン数を計算していきます。可能なマッチ棒の向きは直前に置いたマッチ棒の向きに依存するため、この情報を下位に伝えるためのフラグ f を設けています。また、計算時間の節約のため、いちど算出した数値をキャッシュしておいて再利用しています。これをすべての状態×状態の組み合わせについて行います。

 初期状態、すなわち W=0 における並び方を調べます。W=0 というのはつまりは H 本のマッチ棒が縦1列に並んだ形です。本問の H=20 の場合、総数は 220≒106 にすぎないので、すべての並び方を網羅して対応する状態のカウントを1ずつ増やすやり方で十分です。

 最後に、初期状態に対し、2で求めた行列を作用させます。これはちょうどベクトルに行列を掛け算するのに等しいです。

 先に挙げた H=2 を再び例にします。5つの各状態から各状態へ推移するパターン数は次の通り表されます。横 W に置ける状態iのパターン数を P(W,状態i) と表しています。初期状態は状態1~4がそれぞれ1つずつですので、ベクトル (1,1,1,1,0) に下の行列を繰り返し作用させると任意の W に対する各状態のパターン数が分かります。実際 W=3 では (1977,4603,3031,4603,7618) になります。状態5の数がたしかに 7618 になっていることが分かります。

 以上の処理を書いたコードをこちらに示します。走らせると、数秒程度で正解の 59942368 が出てきます。もちろんコードの書き方やアルゴリズムの組み方は人それぞれですし、今回紹介したものよりずっと簡潔な方法があるかもしれません。今回の解き方はあくまで一例いうことで。。。

 ちなみに完全な形の答えは N(120,12) =
17268157720477448259243004642083272767058997861064539380548157646
33971465843490790094653847489451623670371334807715010826881954216
81518396262143363955934295105735894303039445053069663558074250869
71127010260826397810760477040616285745335811808026930999091677122
36805752608974117681035771110869541626782209001481564264373963313
39838762704623389687564055706386321430111296854386558533084209538
14340043982473734048668990820611548322915560216458700736569321496
70391027855602024022416850165800817096410887071327241158229355795
83929217390134709480431524138275991128496503121774907338471997857
24138028609176030496280078858249167414757118968829723052086617843
77839890128387810174960169017474650667064878746786424853688716591
77929646402110533795992955207959809188783443567703722824428780526
9494241230319482006866744324939170288791240823607240834559942368 です。

 なお、本問は xsd さんと niino さんのお二人に正答いただきました。出題した翌日には正解という早さでした。多謝!

 

2010年08月06日

接点と円と三角形のパズル(解答編)

 接点と円と三角形のパズルの解答編です。

 この問題では、まず、三角形 OAB の面積 S を a, b, r を使って表します。

 A の x, y 座標をそれぞれ Ax, Ay とおきます。円の接線の方程式は公式としてよく知られており(ここなど)、これが (a,b) を通過することから下記の関係がいえます。

 また、A は円上にあるため、

 がいえます。この2つを連立して解くと Ax, Ay が求められます。

 また、B の x, y 座標をそれぞれ Bx, By とすると、同様にして、

 が得られます。さらにここに三角形の面積の公式を使い、整理すると、

 となります。つまり、本問は、S が整数となるような a,b,r の組は何個かを求めることになります。

 (追記) もっとスマートな導出法をコメント欄にて教えてもらいました。△AOB と △XOY はいずれも二等辺三角形で、かつ ∠AOB=∠XOY なので相似です。その面積比は、相似比を2乗した r2:a2+b2 となります。さらに △XOY の面積は公式を使って (b2-a2)/2 となりますので、結果、上記と同じ結果が得られます。

 さて、簡単に思いつく計算方法は、すべての a,b,r の組について、分子が分母を割り切るかをチェックし、割り切るものを数え上げるというやり方です。ですが、a2+b2<108 の条件ではチェックすべき範囲が大きすぎて莫大な時間がかかってしまいます。効率よく計算するにはし工夫が必要です。

 そこで計算量の節減のため、a,b についてのみ列挙を行います。S の式をよく見ると、a,b の値を1組固定すれば、S は (分数)×r2 の形で表すことができます。したがって、この分母を約分しきるような最小の r の値が計算できれば、この r を定数倍したものをすべて条件を満たす組としてカウントすることができます。1つ1つ r の値をチェックせずに済むのです。

 そのような r を求めるにはどうすればよいでしょうか。素直に考えれば、r2 が分母を割り切ればよいので、いったん分母を素因数分解し、各素因数のべき指数を半分にして(端数切り上げ)やればOKです。ですが、素因数分解はたいへん時間のかかる処理のため、結局長い時間がかかってしまいます。

 そこでさらにいくつかの改良を施します。まず、S の形をじっと見れば分かるように、a と b が公約数をもつ場合、公約数は分母と分子で約分し合います。ですので、a と b が互いに素の場合に限って r の計算を行い、公約数をもつケースをそのときにまとめて計算するようにすれば処理が省けます。また、a,b が互いに素であれば、b2+a2 と b2-a2 の公約数は、a, b がいずれも奇数のとき 2、それ以外のとき 1 になりますので、約分の計算が簡単化できます。

 さらに、分母を約分するような r の値を、あらかじめ様々な分母の値に対して計算しておきます。値を覚えておくために1で初期化した配列を用意し、各素数の1乗、3乗、5乗、・・・のそれぞれの整数倍に対しその素数を乗じていきます。

 以上のコードをこちらに記します。コードでは、上記の改良に加え、フェルマーの 4n+1 定理(参考)により、分母の b2+a2 の部分が必ず 4n+1 の形になる点に着目し、必要な配列のサイズを4分の1にコンパクト化しています。

 実行させると、答えの 14898922 が得られます。実行時間は、マシンの種類にもよりますが、例えば僕の5年前のマシンで約30秒。出題者の工夫ではこれが限界でしたが、もしかするとさらにずっと優れた方法があるかもしれません。もし見つかればコメント欄などで教えて頂けると大変うれしいです。

 なお、本問の正解者は、順に niino さん、kozima さん、chaemon さん、xsd さんでした。Project Euler の上位の常連の方々ですね。ありがとうございます!

2011年05月29日

デスクトップアプリケーション「ニコツイート」

 デスクトップアプリケーション「ニコツイート」を作成しました。
 ツイッターのハッシュタグの検索結果を、ニコニコ動画っぽくデスクトップに表示するソフトです。

 

 たとえば次のような使い方ができます。

  • 自宅の PC で、実況系のハッシュタグを流してぼんやり眺めてみる。
  • 勉強会やセミナーで、スライド発表にかぶせて勉強会専用のハッシュタグを流しておくと、聴講者がリアルタイムでコメントを入れられる。


特徴

  • 指定されたハッシュタグの検索を定期的に実行します。
  • 検索した結果を、流れるテロップとしてデスクトップに表示します。
  • テロップの色や大きさ、表示時間などは選択が可能です。

動作環境

 「Microsoft .NET Framework Version 2.0 再頒布可能パッケージ (x86) 」が必要です。
 PC の性能を要求します。
 動作を確認した環境: Windows 7(32bit)

ダウンロード

 ニコツイート Ver.1.1 (2011/6/3)

その他

 バグ報告など歓迎します。

2011年09月25日

割り算と桁数のパズル

 久しぶりに、プロジェクトオイラーふうの問題を作ってみました。難易度は標準的です。ぜひトライしてみて下さい!

---
【問】
整数 N, D に対し、A÷B の小数点以下の桁数がちょうど D 桁となるような N 以下の正の整数の組 (A, B) の個数を C(N, D) と定義する。

例えば C(10, 2) = 8 である。小数点以下がちょうど 2 桁になるのは次の 8 通りである。

1÷4=0.25
2÷8=0.25
3÷4=0.75
5÷4=1.25
6÷8=0.75
7÷4=1.75
9÷4=2.25
10÷8=1.25

また、C(100, 3) = 216, C(10000, 4) = 137366 であることが確かめられる。
C(1012, 12) を求めよ。
---

 回答はこちら(回答終了しました)のページに行って、テキストボックスに答の数字を入力し「回答」を押して下さい。正解なら専用の掲示板ページに飛びます。不正解なら Not Found が表示されます。

 ご回答をお待ちしています!

2011年09月30日

割り算と桁数のパズル(解答編)

 割り算と桁数のパズルの解答編です。

 真っ先に思いつくのは、A, B の組を一つ一つ選んで桁数を調べるという O(N2) のやり方です。しかし、A, B の組は全部で 1012 × 1012 = 1024 通りあるので、これを一つ一つ割り算してたしかめていくというのは到底不可能です。そこで、「A, B が一体どういう条件を満たしていれば小数点以下が D 桁になるか?」という条件を考えていきます。

■ O(N2) から O(N) へのアプローチ

 ポイントは、分数 A/B を約分したときの分母の形に注目することです。「約分後の分母に 2 または 5 以外の因数が含まれないこと」がまず必須の条件であることが分かります。もしそのような因数があれば A÷B は循環小数になってしまうからです。さらに、D の値は、「2 と 5 のべき指数のうち大きいほうの値」に一致することも分かります。すなわち、A÷B の小数点以下がちょうど D 桁となるための必要十分条件とは、「約分後の分母が 2p × 5q の形で書け、かつ max(p, q) = D」であるといえます。

 つまり、条件を満たす A と B は、約分後の分子を m、最大公約数を g とおいて、それぞれ次のように表せます。
 
 (ただし m と2p × 5q は互いに素で、かつ max(p, q) = D)

 結局のところ、本問は、上の条件を満たす4整数の組 (g, m, p, q) の個数を求めることと同値であるといえます。

 そのような組を数えるアルゴリズムを考えます。始めに p と q の値を固定し、次に m の値を固定するという順番で考えます。ある p, q を選んだとき、m はどのような値でしょうか。3通りに場合分けして考えます。① p = D, q = 0 の場合、m は 2 で割り切れない任意の数です。② p = 0, q = D の場合、m は 5 で割り切れない任意の数です。③ それ以外(p ≧ 1, q = D または p = D, q ≧ 1)の場合、m は 2 でも 5 でも割り切れない任意の数です。m を決めた後の g の選び方は単純です。ベクトル (m, 2p × 5q) を整数 g 倍したすべての組は上の条件を満たします。ですのでそのような g の個数は、N を m と 2p × 5q の大きい方で割れば求められます。

 公式化すると次のようになります。割り算は端数を落としていることに注意して下さい。これを単純に実装すれば、O(N) のプログラムができます。
 
 

■ O(N) から O(√N) へのアプローチ

 さて、本問は N = 1012 です。O(N) ではまだ時間がかかりすぎます。さらに計算時間を下げる必要があります。

 いちばん時間がかかっているのが、m に関する繰り返し計算です。ここを高速化します。max の大小で式を分解すると、前半部分は、シグマの中身が m の値に依存しないので、単純な掛け算で計算可能です。ただ m の値は 2 または 5 で割り切れない制約があるため、そうした数を除外します。

 後半部分は、単純化すると、m に対する ∑ ((定数) / m) を計算する問題です。これは一つ一つ計算すると時間がかかりますが、ある程度 m が大きいと (定数) / m は同じ値が続くという事実に着目すると、一気にオーダを落とせます。つまり、ある整数 k に対し、(定数) / m = k となるような m は何個存在するかを考えるということです。そのような m は (定数)/k - (定数)/(k+1) 個存在します。つまり、始めは m をだんだんと大きくしながら m に対する ∑ ((定数) / m) を繰り返し計算し、ある程度 m が大きくなったところで、ループ変数を m から k に切り替えて、∑ k × ((定数)/k - (定数)/(k+1)) を計算します。なお前半部分と同様、2 または 5 で割り切れない場合を除外しましょう(詳細は省略します)。
 
 m と k を切り替えるタイミングは m が √N に等しくなったときがベストです。これによりアルゴリズムは O(√N) になります。

 以上のコードをこちらに記します。上の説明では省いた細かなケースのバグを除去しています。

 実行させると、答えの 83566672035424 が得られます。実行時間は上のコードで1秒を切るはずです。

 なお、本問の正解者は、順に有為さん、triceps さん、stqn さんでした。Project Euler の Fastest Solvers によく登場する方々ですね。ありがとうございます!

2015年03月19日

連絡用ページ

 こちらのブログへの今後の新規エントリの投稿はありません。
 
 Kawazoeへのご連絡は、riverplus@gmail.com にメールして下さい。

 CodeIQでコード公開された方からのご連絡については、コードの公開について をご覧下さい。