■Google入社問題

 先日、NHKスペシャル「Google革命の衝撃」が放送された。その中で、Googleの人材募集の広告が紹介されていた。人材募集なのに「Google」の文字は、どこにもなく、「{eの値で、最初に出てくる10桁の素数}.com」とあるだけの広告だ。

 ネットで調べてみると、これは、数年前の出来事らしい。そういえば、そんなことがあったかも知れないと、かすかに記憶が甦ってきたが、たぶん、当時は「へえぇ」という感じでスルーしていたのだろう。

 で、「コマネチ大学数学科」が始まるまでの間、この問題をあらためて考えてみた。自然対数の底「e」の値といったら「ネイピア数」だ。

■たけしの誰でもピカソ:ネイピア数e相性診断
 2億桁のネイピア数の中から、ふたりの誕生日が何桁目に登場するかを調べてくれる。しかし、自分の誕生日4桁と相手の誕生日4桁で、8桁にしかならない。しかも、月は12、日は31までと、入力できない数が多すぎる。これでは役に立たない;;

 しょうがないので、「エクセル」で作ろうと思ったが、エクセルのMOD関数は、10桁の数値には対応していない;; VBAを使えば、なんとかなりそうな気がするが、なんか面倒なことになりそうで気後れする。手軽に出来るのは、FlashのActionScriptだ。ネイピア数は、ひとまず置いといて、問題を簡単にするため、適当な文字列「222215722222」の先頭から順に3文字ずつ抜き取って、それが素数であるかどうかをチェックする、FlashのAction Scriptを書いてみる。

20070125_01

20070125_02

 動作チェックをすると、確かに「222215722222」の文字列から「157」を抜き出し、それが「素数」であることを判断している。白状すると、素数かどうかのチェックは「Wikipedia」の「素数判定」の項目から、引用させてもらった。

 ここまでくれば、あとは簡単。最初の文字列に「自然対数の底e」の値(ネイピア数)を入れ、抜き出す文字列の数を「10」にするだけだ。

自然対数の底「e」の値は、以下のサイトでも入手可能……。

■eの値
 しかし、500億桁もいらないんですけど^^; 最初の1億桁だけでも、55MBもある。解凍すると、117MBのテキストファイル;;「エクセル」では、全部を読み込めなかった。

■自然対数の底
 こちらは、指定した桁数の「自然対数の底」の値を表示することができるので、便利だ。とりあえず、250桁を表示してコピーし、それを、FlashのActionScriptに貼り付ける。

20070125_03

20070125_04

 「なぬ~っ!」動作チェックでは、うまく動いてくれたのに、「False」だとぉ~;; あれこれ悩んでみたが、うまい解決策が思いつかない。たぶん、どこかでオーバーフローしているのだろう。いつも「結果が出ればいいや」と、コマ大数学研究会ばりの体当たりプログラミングをしているから、こういうことになる。やはり、基礎ができてないと、こういうところでボロが出る。付け焼刃の数学の知識ではダメらしい。「アホなことやっているなぁ」と思った方は、迷える酔っ払いの爺に愛の手を!

(1月26日追記:ループ数が10のままだぁ^^;;)

(1月27日追記:偶数を除外していなかった;;やっと正解に!)

 数年前の問題なので、ネットで調べれば、正解はわかる。正解は「7427466391」。

2.718281828459045235360287471352662497757247093699959

5749669676277240766303535475945713821785251664274274

6639193200305992181741359662904357290033429526059563

0738132328627943490763233829880753195251019011573834

 で「7427466391.com」へアクセスすると、次の問題が提示される。
《以下、引用》
Congratulations. You’ve made it to level 2.
Go to www.Linux.org and enter Bobsyouruncle as the login
and the answer to this equation as the password.

f(1)= 7182818284
f(2)= 8182845904
f(3)= 8747135266
f(4)= 7427466391
f(5)= __________

《引用終わり》
 こちらの問題は、f(1)~f(4)の数値が10桁で、すべての数値を足すと「49」になることに気が付けば、さほど、難しくはない。これなら「エクセル」でも、解けるぞ。

20070125_05

セルA1に、先ほどの「自然数の底」サイトからコピーした数値を貼り付ける(セルの書式設定は文字列にしておく)。MID関数を使って、1文字ずつ、移動させながら10文字分を抜き出す。オートフィルの連続入力をするため、行番号を求める、ROW関数を使って、抜き出す文字列の開始位置を求めている。さらに、抜き出した文字列を1文字ずつ分解して数値に換え、「=VALUE(MID(A3,$B$2,1))」その合計を出す。合計が「49」になる行を見ると、f(1)~f(4)の値になることを確認できる。

20070125_06

5番目の数値は、129行目に出現する。ネイピア数の小数点以下、127桁目だ。

 結局、「コマネチ大学数学科」が始まるまでの小手調べのつもりだったが、番組が始まっても、こちらの問題に気をとられたまま、酔いが限界に達している。なんとしても、この記事をアップしてから、眠りにつこう。今回の「コマネチ大学数学科」の問題は、かなり難しいという印象……。

今回、参考にした素数についてのサイト

■a prime number
 1から2147483647までの素数を計算する。残念;;10桁だが、「9999999999」まで表示できないと、今回の問題には対応できない;;

■ゆいのホームページ:ソフトウェア&小技メモ
 341,550,071,728,321以下の素数(15桁)を、1個当り数秒で求める。短時間で素数を判定するアルゴリズムのキーワードは「2,7,61」? このサイトを利用すれば、10桁の素数表を作成することができるが、素数表とネイピア数とのマッチングを試みる方法は、いささか、現実的でないような気がする。

■AjaxによるRSAアルゴリズム体験
 360桁の素数でも一瞬で表示する。なんで、こんなに速く素数を生成できるの? 素数生成のアルゴリズムは、いくつかあって、それが素数であるかどうかを検証することのほうが難しいのか……。いわゆる、因数分解するほうが大変という「N≠NP」問題なのかな?

■コマネチ大学数学科マス1グランプリ

 昨年末の「M-1グランプリ」は「チュートリアル」が獲ったけれど、もう一つの「M-1」、「マス1グランプリ」は誰の手にと楽しみにしていた「コマネチ大学数学科マス1グランプリ」。期待に違わず、かなり楽しめた。しかし、「いいちこ」漬けの頭では、リアルタイムに参戦できるわけもなく、録画した番組であらためて問題を振りかえってみた。

●ROUND1 計算問題

M1_round1_01

計算すれば答えは出るのだけれど、いかに式を簡単にするのかがポイント。私がパッと答えることができたのは、問9だけだった;;

●ROUND2 最速図形バトル

計算問題で出遅れたマス北野だったが、さすがに図形問題では最速。しかも、上のFlashで紹介している解法は、ハサミを4回入れなければならないが、マス北野は、たった2回ハサミを入れるだけで、正解した。じつは、2番目に速かったのは、西本さん。しかし、思考速度は速いものの、不器用ぶりを発揮し、図形を並び替えることに手間どり、東大生チームに先を越されてしまった。ツッコミどころも満載の西本さんであった。

●FINAL ROUND 一騎打ちバトルロイヤル
マス北野と数学オリンピックの2年連続チャンピオン、西本さんとの一騎打ちとなった。
M1_round3_01_1

問題は「1000本の棒を使って正四面体を作り、積んでいくと、何段になるでしょう?」というもの。ひとつの正四面体を作るには、6本の棒が必要。これを1000本以内で、図のように積み上げていくと、何段作ることができるかということ。

M1_round3_02

1段目は正四面体が1個。2段目は3個。3段目は6個……と続く。関係ないが、「Shade」で正四面体を描くことが、こんなに大変だとは思わなかった。で、1つの正四面体を描いたなら、あとは、コピーして貼り付けるだけなのだが、これも、意外とめんどうくさい。2段目で挫折……。それを考えると、コマ大数学研究会のがんばりは、スゴイ!と思う。

M1_round3_03

というわけで、エクセルで表にしてみた。段ごとの正四面体の数は、1段目からその段までの数を足したものになる。セルB4に「=SUM($A$3:A4)」として、オートフィルで以下の行を連続入力する。合計の欄も同じく、セルC4に「=SUM($B$3:B4)」とする。この合計に6を掛ければ、棒の数が出る。9段目で990本になり、10段目では1000本を超えてしまう。

これは、マス北野の方法と同じだ。西本さんは、最速ですぐにこの問題を解く公式を導き出した。ただ、番組では説明の部分がカットされていたのが残念だ。

美しき数学の時間では、竹内薫センセが解説。この問題、パスカルの三角形を用いても解くことが可能とのこと。

M1_round3_04

正四面体の合計数が表れているではないか。しかも上から数えてみると、9段目が「165」になる。まるで、手品で「引いたカードをあらかじめ予言しておきました」みたいな、パスカルの三角形。パスカル、あんたはスゴイ! ふと、今、思いついたのだけれど「同じ大きさの鏡餅を3つ並べて、その上に1個置く。このような形で10段の鏡餅を作るには、鏡餅は何個必要ですか?」という、お正月らしい問題ならば、コマ大数学研究会は、これほど苦労しなかったはず……あ、これじゃ、番組として成り立たないのか^^;
でも、段ごとに必要な正四面体の数を考えるとき、鏡餅で考えると、わかりやすいかもよ。

■コマネチ大学数学科30講:ディオファントス

テレビドラマ「僕の歩く道」のオープニングで毎回、草ナギ剛君が自転車に乗っているシーンが流れるんだけど、草ナギ君が「ムラタセイサク君」に見えてしまうのは、私だけ……?「たけしのコマネチ大学数学科」第30講:ディオファントス。

20061215_01 今回の問題は「立方体で直方体を作り、外側の面に色をつけたとき、色がついた面とついていない面の数が同じになるのは、どのような直方体か答えなさい」。

図に提示してある、横幅(X)2、高さ(Y)2、奥行(Z)2の場合も、色のついた面と色のついていない面の数が同じになる。問題はこれ以外の組み合わせを答えることになる。

20061215_02

コマ大数学研究会のように豆腐やサイコロステーキで検証するのは大変なので、エクセルの表を作成した。「Excel」がインストールされているパソコンならば「comaneci30.xls」をクリックして「開く」ボタンを押してほしい。

「ディオファントス」は、古代ギリシャの数学者。未知数が2以上ある方程式の整数解を求めるものを「ディオファントス方程式」と呼ぶらしい。

20061215_03

答えは、2通りある。コマ大数学研究会は、残念ながら1通りの答えしか見つけられなかった。東大生、マス北野とも正解。コマネチフィールズ賞は、マス北野が辞退し、東大生コンビが受賞した。

「ディオファントスの墓碑」問題(引用:Wikipedia)

ディオファントスの人生は、6分の1が少年期、12分の1が青年期であり、その後に人生の7分の1が経って結婚し、結婚して5年で子供に恵まれた。ところがその子はディオファントスの一生の半分しか生きずに世を去った。自分の子を失って4年後にディオファントスも亡くなった。

ディオファントスがχ歳に亡くなったとすると、
20061215_04

これを解くと、χ=84となる。結局、ディオファントスは84歳で亡くなったらしい。

■コマネチ大学数学科29講:カタラン数(補習)

 頭の中でカタラン数が「カタラン、ワカラン」と音を立てている。仕事をしなければならないのだが、このままでは気になってしょうがない。そこで、頭の中を整理する意味で、エクセルの表にしてみた。

20061211_01

 EXCELがインストールされているパソコンならば、「comaneci29.xls」をクリックし、「開く」を実行してみてほしい。

 問題を解くためには、できるだけ問題を単純化して、それを一般化する手法を取る。

20061211_02

20061211_03

 「P」とか「C」とか、わからない記号が出てきたが、これは数学のお約束ごと。数学が難しく感じたり、理解不能と思えるのは、誰かに教えてもらわないと一生わからない記号(お約束)が多いことなんだよね。

 その点、この問題を解くのに参考にした、結城 浩さんの「プログラマの数学」という本は、数学が苦手な人にも、きちんと記号の意味を説明をしてくれている。優しさは(理解の)易しさにもつながるのだ。

 これで、エクセルの表の「人数」に「10」と入力すれば、正解が出るのだけれど、今回のテーマは「カタラン数」なので、カタラン数とはどういうものか……。

20061211_04_2

2007年3月9日追記:図の間違いを修正;;

 パスカルの三角形を半分にしたような形なのだが、この表に表れる「1、1、2、5、14」という数の並びが「カタラン数」と言うらしい。今回の問題の2人、4人、6人、8人の場合のカップル(握手成立)数になっているのだ。

 マス北野が短時間で正解に辿り着いたのは、(2+5)の2倍が、次の数字「14」になることに気づいたからだ。
つまり、(2+5+14)×2が、10人の場合の答えになると考えた。マス北野のこういった法則を見つける能力というか、数学的な直観力は「さすが」だよね。

■パスカルの三角形

 「コマネチ大学数学科」の竹内薫センセの解説によると「パスカルの三角形」は小学校の教科書に出ているとのことだけど、ホントなの? いやぁ、驚きだなぁ。現在の教科書がどうなっているのか知らないけれど、少なくとも、私は小学校で習った覚えがない;;

 で「パスカルの三角形」については、ひとつ前のエントリ「カタラン数」のFlashムービーの中でも、ちょこっと触れたけれど、ひとつ上の階層の隣合うセルの和が下の階層のセルの答えになっているもの。たとえば、こんな具合に……。

20061209_01

 この表は、Excelで作成したもの。これを「セルの条件付き書式」で偶数と奇数で色分けしてみる。すると、こんなふうになる……。

20061209_02

 おお、シェルピンスキーのギャスケットと同じになるではないか。これぞ「美しき数学」の奥深さを感じさせるよね。

《参考》
■「プログラマの数学」結城 浩/著

■WIKIMEDIA CINNIBS : Sierpinski triangle
http://commons.wikimedia.org/wiki/Sierpinski_triangle?uselang=ja

プログラマの数学
プログラマの数学

著者:結城 浩,結城 浩
販売元:ソフトバンククリエイティブ


■コマネチ大学数学研究会「誕生日」

今日は「たけしのコマネチ大学数学科」は休講。代わりに弾さんが11月22日の記事「直感的な定理の反直感的な帰結」で問題を出してくれたので、考えてみよう。

最後に問題。妻と私は誕生日が同じなのだが、カップルどおしの集まりにおいて、何組以上のカップルがいれば我々のようなカップルが一組以上含まれるでしょう?

この問題を解く前に、竹内薫センセの「頭がよみがえる算数練習帳」で出されている問題を考えてみてほしい。

30人のクラスの中で、ふたりの誕生日が同じになる確率はどのくらいでしょう?

誕生日が一致する確率は、1(100%)から誕生日が一致しない確率を引いたものと考えることができる。
つまり「=1-(364/365)」、3人なら「=1-(364/365)×(363/365)」。30人の場合は……。

20061123_00_1
こんな計算をすることを考えただけで、脳のブレーカーが落ちて、真っ暗闇の脳停止状態に陥ってしまう。そこで、コマ大数学研究会らしく、あれこれ考えず、まず体を動かしてみよう。

20061123_01_2

エクセルのA列1行目に「364」と入力し、2行目に「363」と入力。この2行分を選択して、オートフィルで29行目まで連続入力する。

20061123_02_1

30行目に1行から29行までの数値を掛け合わせる関数、「=PRODUCT(A1:A29)」と入力する。B列の30行目には「=365^29」(365を29回掛けた数)と入力。どちらも、あまりに大きな数なので、表示できず、指数形式で表示される。ちなみに「5.94803E+73」とは、「5.9…」を約「6」とすると、その後ろに「0」が73個つく数だ。こうなると読み上げることも難しい。

話を戻すと、A列は「分子」、B列は「分母」に分けて積を計算したので「=A30/B30」とすると約「0.3」つまり、誕生日が一致しない確率は、約30%。誕生日が一致する確率は「=1-A30/B30」で約70%ということになる。

1クラス30人の中で、誰かと誰かさんの誕生日が一致する確率は、予想(直感)に反して意外にも大きい……というのが、この問題の趣旨だ。

そこで、冒頭の弾さんの問題に戻る。これを確率の問題としてとらえると、カップルのふたりの誕生日が一致する確率は「1/365」であることは明白(うるう年は考慮外)。同じ結果を導くのに、わざわざ式を「=1-(364/365)」などと複雑にする必要はない。つまり、どのカップルも誕生日が一致する確率は、1/365なので、365組のカップルを集めたら、そのうちの1組くらいは、同じ誕生日のカップルがいると考えてもいいんじゃないの。弾さん夫妻と同じ誕生日のカップルとは、一言も言っていないので、どんな誕生日だろうが、とにかく誕生日が同じカップルがいればいいのだから。

で、もしも、これを確率の問題として捉えないとどうなるか。「サイコロを振って『1』の目が出る確率は?」と聞かれれば「1/6」だが、「サイコロを何回振ったら『1』の目が出るでしょう?」と聞かれたら、予想や直感に反しても「実際、やってみないと、わからない」と答えるしかない。

■コマネチ大学数学科25:和算

今回は江戸時代の数学書「塵劫記」に出てくる「百五減算」という算術の問題。

ある人の年齢を 3、5、7 でそれぞれ割った余りがそれぞれ 1、2、3 になるとき、その人の年齢はいくつでしょうか?

で、さっそく私も「エクセル」で「百五減算」を作ってみた。「塵劫記」や「百五減算」は、Wikipediaに詳しい解説が載っているので、そちらを参照してほしい。

20061103_01

※ガダルカナル・タカさんの場合

ポイントは、3、5、7の最小公倍数が105になること。エクセルでは「=LCM(3,5,7)」とすれば、簡単に求めることができる。もっとも、3、5、7は素数なので、3×5×7=105ということだ。

で、105をそれぞれ3、5、7で割ると、35、21、15になる。求める数(年齢)を「n」とし、3、5、7それぞれの数で割った余りを、a、b、cとすると、
百五減算の公式は、
n=70a+21b+15c-105k となる。(kは、nが105よりも大きいとき、何回が引くという意味)

番組を見ていて、一番ひっかかったのは、なぜ「35」だけを2倍して「70」にするかだろう。ちゃんと竹内センセは解説をしてくれているのだが、こちらの理解力が足らず、モヤモヤした感じが残った。

これは実際に「=mod(35,3)」としてみるとわかる。「35」を「3」で割ると、余りが「2」になる。

つまり、こーゆーことだ。
70は、5と7で割り切れるが、3で割ると1余る数
21は、3と7で割り切れるが、5で割ると1余る数
15は、3と5で割り切れるが、7で割ると1余る数
105は、3でも5でも7でも割り切れる数(最小公倍数)

番組では、全員が正解した。しかし、納得がいかないのは「コマネチ・フィールズ賞」をコマ大数学研究会が取ったこと。東大生チームは、ちゃんと数式を立てて解き、条件を満たす数として、52、157、262を出した。そこで、コマ大のロケで問題と同じ余りが「1、2、3」になった番組プロデューサの「吉田さん」が、157歳や、262歳はありえないから、「52歳」という答えだった。これを「最終的には見た目」と判断されたが、これが現実的な答えだ。百五減算だって、江戸時代105歳を超える長寿の人はいなかったろうから、105を引いているわけで、その点では同じだと思う。

私はコマ大数学研究会を応援しているが、今回の竹内裁定には疑問が残る。マス北野も「こういう情けが番組の視聴率を下げる」と発言していた。

でも、今回は全員正解の引き分けなので、オープニングの
ダンカン「倍数の例を挙げてください」
ガンビーノ小林「9は3の倍数」
〆さばアタル「25は5の倍数」
無法松「501はリーバイス」
という、久々のヒットで「フィールズ賞」をもらったと考えれば納得。コマ大、ファイト、ファイト、ファイト!!

「500円でわかる活用技エクセル」発売

Excel_book これまでの学研「500円でわかる」シリーズにハンディーなコンパクトサイズ(B5版)の新シリーズが登場。10月19日発売なので、もう書店には並んでいるはず。146ページ、オールカラーで500円(税別)は、お買い得だと思う。本屋さんで見かけたら手に取って、そのままレジへ進んでください(^^;

 

 

■セブンアンドワイ
http://www.7andy.jp/books/detail?accd=R0217076

■アマゾン
http://www.amazon.co.jp/gp/product/4056045798

500円でわかる活用技エクセル

 今日は、五反田にある学研の編集部で「500円でわかる活用技エクセル」の校正。別の仕事で来ていた、イラストレーターの「森きのこ」さんと会う。つい最近まで、森きのこさんのお兄さんが「森チャック」さんであることを知らなかったんだよね(^^;

 で、私が書いた「500円でわかる活用技エクセル」は、これまでのA4変形版ではなく、B5のハンディ版。発売日は10月19日だけど、もう「7&Y」や「Amazon」で予約を受け付けているみたいだ。

セブンアンドワイ

Amazon.co.jp

六芒星のパズル

 このブログにトラックバックを送ってくれた「Atelier-T.T ゲームプログラミング工房」で「六芒星(ろくぼうせい)」のパズルをプログラミングで解くというおもしろい試みをしている。

Tr_011  パズルのルールを確認しておくと、図の○の部分に1~12までの数字を入れ、各列の合計がすべて同じになるようにする(数字は重複使用してはならない)。

 私は「C++」を持っていないし、使ったこともないので、公開しているプログラムを試してみることはできないのだが、「エクセル」で挑戦してみようという気になった。

 もしも、この問題を「コマ大数学研究会」のように体を張り、ひとつひとつ数字を入れて確かめる方法をとったならば、どれくらいの組み合わせが考えられるのだろうか。

Tr_012  一度使った数字は使えないので「=12×11×10……×1」とエクセルで計算すると「479001600」通りとなった。これは「12の階乗」だ。掛け算をいくつも並べるのは面倒なので、「エクセル」にも関数が用意されていて「=FACT(12)」とすれば、答えが出る。

 4億7900万通りをすべて調べるわけにもいかない。「エクセル」でこの問題を解くのは無理っぽい。そこで、いくつかの仮説を立てる。まず、1列の4つの数字を足した合計がいくつになるか。1~12までを全部足すと「78」、これを12で割ると、ひとつの○に入る数字の平均は「6.5」、それが4つで「26」だ。

Tr_012b 仮説1:列の合計は「26」
仮説1が正しければ、1列には偶数2個、奇数2個が入る(もしくは、偶数4個、奇数4個の組み合わせも考えられる)。
辺の頂点、交差するところで数字は2回使われるので、ひとつの列を考えると、前半部分だけを決定すれば、後半部分は他の列によって自動的に決まる。

Tr_013  こうして「六芒星パズル」を解くための(あくまで補助するだけの(^^;」表を作成した。数字はとりあえず便宜的に入れたもの。列(3)と列(4)は、入力する必要はなく、他の列をセル参照している。そして、答えのチェックの意味で列の合計を表示している。これだけでも、図を紙に描いて、数字を書いては消すよりは、ずっとラクちんだ。

Tr_014 Tr_015  まず、A列の「1」と「2」を残して考えてみる。すると、仮説では、列の合計が「26」になるはずなので、残りの後半は、「11」と「12」だ。ここでF列を考えると、すでに「2」があるので、次に大きい「9」と「10」を使う。すると、B列(1)は「5」となる。

Tr_016  同様に列Eは、すでに後半部分に「10」と「1」が入っているので、「7」と「8」を入れると、うまく「26」になる。試行錯誤を繰り返し、完成したのが、この表。なんとかすべての数字を入れることができた。

Tr_017  前出の「Atelier-T.T ゲームプログラミング工房」によると、解は「960」通り。このうち、回転、鏡像による重複は、6×2で12通り。すべての解に対して12通りの重複があるので、この「六芒星パズル」には、80通りの解があることになる(らしい……99.9%の仮説)。