スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:-- 】
| スポンサー広告 | コメント(-) | トラックバック(-) |
中学受験問題を無理やり解く

yyasuda ブログ「ECONO斬り!!」に灘中学校の数学入試問題が紹介されていた.「数列 207, 2007, 20007, 200007, ... の要素のうち 27 で割れて 81 で割れない最初の数を見つけよ」とのこと.

蛇足.なるほど 2007 年の今年にふさわしい問題だ.来年 2008 年にちなんだ似たような問題はできないかな.それにしても中学受験かぁ.ボクのときはすぐ近所にある公立に通う楽さを思えばどこも受験する気にならなかった.で,入学した公立には徒歩で通ったんだが,墓地のすぐそばにある池の横を通う日々だった.ときどきとても長いヘビがいて,それを避けながら歩こうとすると,ちがうヘビが出て来たりすることもしばしば.季節によるが,雨の日には近くの道路は潰れた平面カエルでいっぱいになって臭かった.そういえば最近水不足の香川は,発電用水や農業用水の水を水道に回すことにしたとか.ため池の水とかだろうか.ううむ,ヘビはまだいいとして,ため池のそばには古いお墓も多い (たぶん) のを考えると,あまり気持ちよくないな.じゃあ話を戻そう.

で,ボクがこの問題をみて最初に思ったのは,あたりまえだが素因数分解 (素数の積に直す) すればできるということ.(素因数分解ってのは「小学生の知らない高度な技」かも.それと,素因数分解というのは暗号にも使われていることから分かるように,なかなか計算するのがたいへん.) その際,まじめに素因素分解する必要はなくて,とりあえず 3 で何回割れるかを調べればいい.具体的には,207, 2007, 20007, 200007, ... をそれぞれ 3 で割って 69, 669, 6669, 66669, ... を得る.さらに 3 で割って 23, 223, 2223, 22223, ... を得る.これをまた 3 で割ると 7 余り 2; 74 余り 1; 741 余り 0; 7407余り 2; 74074 余り 1; 740741 余り 0;... を得る. このとき 222 が 3 で割り切れることを使うと少し楽になる. (下に引用する yyasuda ブログのコメント 7 とたぶん同様のやり方.)

以上のようにして正解を出すことは無理ではないが,yyasuda さんの言う「5分以内を目標に」はむずかしいかな.彼 (正解はこちら) やその友人の指摘するように,3 の倍数や 9 の倍数のある性質を利用することにより,以上の手続きはもっと簡単になる.特に最初に 9 で割ることが鍵で,それは中学受験経験がないとなかなか思いつかないという.どうだろう.むしろ 23, 223, 2223, ... のところから先にすすむとき 3 の倍数の性質を知っていれば有利だとは思うが.倍数のそういう性質を知っているという「特殊技能」よりも,「数列の各要素を一括して操作する」(数列全体に気を配りながら変換する) といった視点の方が鍵かもしれない.そして中学受験経験者は,特に「特殊技能」でもない後者の視点において優れている---ということかもしれない.

だとしたら,「特殊な知識に依存する」という,この試験問題にたいする批判はあまり的を得ていないかも.

さて,ボクはこの問題を無理やり解いてみることにした.そのため,去年少しかじった (その後も関連 web をちょくちょく覗いたりしている) Java でプログラミングの習作をしてみた.ソースコードはこちら: Nada2007Prob.java ファイル (テキストエンコーディングは日本語 Shift JIS).

テクニカルなリマーク.html の pre タグを使ってプログラムをここに載せたいところ.でも,pre タグをこのブログで使うと一部ブラウザで表示が崩れることが過去にあったので,別ファイルでしめす.最初,変数 a の型を int にしたところ javac でコンパイルしたとき「精度が落ちている可能性」のエラーが出た.Java の数値型には気をつけなければいけないらしいが,実のところどういうときにどの型を使うべきかボクはよく理解していない.(まさに「特殊技能」と言えないか.) 何回かの失敗を経て,よく分からないが変数 a の型を double にしてみたら,なんとかまともな結果が出た.ちなみに Math.pow というベキ乗を表す関数は入力も出力も double 型となっている.

上記プログラムを実行したアウトプットは以下の通り:

207は 27 でも割れないのでダメ
2007は 27 でも割れないのでダメ
20007は 81 で割れてしまう
200007は 27 でも割れないのでダメ
2000007は 27 でも割れないのでダメ
20000007は 27 で割れるが 81じゃ割れない.正解候補!
200000007は 27 でも割れないのでダメ
2000000007は 27 でも割れないのでダメ
20000000007は 27 で割れるが 81じゃ割れない.正解候補!
200000000007は 27 でも割れないのでダメ
2000000000007は 27 でも割れないのでダメ
20000000000007は 81 で割れてしまう
200000000000007は 27 でも割れないのでダメ
2000000000000007は 27 でも割れないのでダメ

追記 (6/27/2007; テクニカル). 上のプログラムでは数列の第 i 項を b_i=2*10^{i+1}+7 と,ベキ乗を使って表現した.そのため数値型を浮動小数点数の double にする必要があった.ベキ乗を使うのにこだわったのは,ベキ乗をつかいつつエラーをさける方法を探りたかったからだ.稚拙なプログラムになっているのはそういう事情もある.

しかし問題の趣旨から言えば,a_i=b_i-7 を項とする数列 200, 2000, 20000, ... が,10 を公比とする等比数列になっていると考えるほうが自然だ.(数列を文字列の列と考えて,文字 0 が毎回挿入されているとするほうがさらに自然だが.) そうすると a_i=a_{i-1} * 10 という具合に繰り返し処理のひとつ前の結果を使うことができる (プログラム中では単に a=a * 10 でいい).プログラムとしても毎回ベキ乗を計算する無駄をやらなくて済むので望ましい (?) のかもしれない.その方針でやってみたところ,たしかに数値型は整数型の long で通すことができた.もちろん long の保持できる桁数の 19 桁を超えるとうまくいかなくなるが.

さて,本職プログラマであれば 2分とかからずに紙に書き出せるようなこのプログラムだが,最近話題になっている記事によれば,(アメリカでは) プログラマ職に応募してくる人間のほとんどが,これと同じレベルのプログラムを書けないという.だから稚拙だって笑わないでくれ~.「習作」なんで.

スポンサーサイト
【2007/06/24 01:15 】
| | コメント(0) | トラックバック(1) |
仲介者による囚人のジレンマ解決法

「囚人のジレンマ」については聞いたことがあるだろう.

もし「囚人のジレンマ」や戦略形ゲームの表の読み方を知らなければ検索するといい.すぐ見つかるはずだ.たとえば三原麗珠「権利論への数理的アプローチ: レクチャー・ノート」のセクション 1.1.2 を参照.三原の例では数値がちがっているが,大小関係だけに注目すれば同じこと.

「囚人のジレンマ」とは以下の表のような戦略ゲームであり,相手が戦略 C (「協力」) を選ぼうと D (「非協力」) を選ぼうと,自分としては戦略 D を選んだ方が利得が高い.よってペア (D, D) が均衡 (支配戦略均衡) になる.その均衡からひとりだけが外れたところでそのひとの利得は上がらないので,もちろんこの均衡はナッシュ均衡でもある.問題は,均衡 (D, D) からふたりがそろって外れると協力のペア (C, C) が実現し,利得ペアが (1, 1) から (4, 4) へと,両者にとって改善することだ.「この協力時の利得 (4, 4) をうまく実現する方法はあるか?」という《ジレンマ解消》の問題はゲーム理論のひとつの関心事である.

C D
C (4, 4) (0, 6)
D (6, 0) (1, 1)

囚人のジレンマの解消法として有名なのは,無限回繰り返し (繰り返しゲーム) だろう.これは協力の繰り返しも均衡になるけど,その他「ほぼなんでも」均衡になることが知られている (フォーク定理).また「社会契約」などと呼ばれる,「強制装置の導入」による解決法も知られている.単なる強制では説得力がないので,ある強制装置に参加するとの協定あるいは契約を個人の自由意思にもとづいて結ぶと考えるのが普通だ.たとえば「非協力な行動をとったばあいは罰金を支払います」といった約束を考えることができる.こちらは個人がその約束どおりに行動するとはかぎらないという問題がある.

最近ボクが目にした Monderer and Tennenholtz (2006) による解消法は「仲介者」(mediator) を考えたものだ.上記の囚人のジレンマに仲介者を導入したゲームを以下にしめす (戦略 M の列と行が追加されている).読者は仲介者がどういう役割を果たしているか,その意味を考えると同時にこのゲームの均衡を求めるといい (演習問題).

M C D
M (4, 4) (6, 0) (1, 1)
C (0, 6) (4, 4) (0, 6)
D (1, 1) (6, 0) (1, 1)

時間稼ぎの蛇足.今回の記事に唐突に囚人のジレンマを持ち出したことに深い意味はない.我田引水のためのなにかの伏線と思う読者もいるだろうが,いまのところ種明かしのようなものは考えていない.囚人のジレンマはそれ自体有名だから,その解消法に関心を持つ読者は少なくないだろうという判断だ.

さて「演習問題」を少しは考えてくれただろうか? 答の解説に進もう.

まず (D, D) は以前と同じくナッシュ均衡になっており,(1, 1) の利得を実現する.そのほかに (M, M) もナッシュ均衡になっており,利得 (4, 4) を実現することがわかる.で,(M, M) の強みはそれが「強均衡」と呼ばれる均衡になっていることだ.これはその戦略の組合せから (ひとりとはかぎらない) 何人かのひとびとが戦略を変えたところで,彼らすべての利得が改善することはないような戦略ペアのことである.つまり,(M, M) を離れてたとえばふたりが (D, C) にうつれば利得は (4, 4) から (6, 0) と変わるが,ひとりの利得は下がっている.ほかにどこに移ろうとも,両者の利得が同時に改善することはない.一方で,もうひとつのナッシュ均衡 (D, D) からはふたりが (C, C) なり (M, M) なりにうつれば両方の利得が上がる.つまり (D, D) は強均衡ではない.「強均衡」という概念に絞り込めば,(M, M) だけが該当するわけであり,囚人のジレンマの解消になっている. (もとのゲーム自体のではなく,仲介者を導入したゲームの強均衡なので "strong mediated equilibrium"と彼らはよぶ.)

問題は上の拡張したゲームの意味だ.これは仲介者がプレーヤーたちに以下の提案をすると理解すればいい:「もし両方のプレーヤーが自分を仲介者として利用することに同意してくれれば,自分はそれぞれのプレーヤーに代わって C をプレイする.もしひとりだけが自分を仲介者として利用することに同意してくれれば,自分はそのプレーヤーに代わって D をプレイする.」すなわち戦略 M は仲介者の利用に同意することと考えれば,上のゲームが出来上がる.もちろん仲介者を利用しない自由はプレーヤーに確保されている.(ただ,他人による「代理プレイ」が効くような戦略でないとこの解決は無理だろう.)

以上紹介した Monderer and Tennenholtz (2006) による解消法と似た方法として,現在ではほとんど忘れられてしまった「メタゲーム」による解消法というのがある (たしか彼らは言及していない).ゲーム理論の専門家でも若い世代は知らないかもしれない.したがって自分もほとんど知らないわけであるが,これはたしか自分の戦略を相手の戦略に依存させ,たとえば「キミが協力するならボクも協力,キミが非協力ならボクも非協力」といった戦略を考えたと思う.ここで問題になるのは,もとの囚人のジレンマが互いに相手の戦略を見ずに自分の戦略を決めるという,「同時決定」のゲームであったことだ.「メタゲーム」の類いの戦略の依存性を持ち出すとどうしても暗黙的に「時間」の要素が入ってきて「同時決定」から離れることになるんではないか.ゲームを拡張しているわけなので時間が入ること自体はまちがいではない (繰り返しゲームでも時間が入るし) が, できれば同時決定の設定は変えずにジレンマを解消したいものだ. (←若輩ゆえこの段落はまともな知識や資料なしで議論しているのであまり信用しないほうがいい.)

蛇足.メタゲームはほとんど忘れられてしまったというのは経済学にかんするかぎりウソではないが,死滅したわけではない.わが平成香川大学の経済学部は10年ほど前に「コンフリクト解析」の分野で理論家を公募して採用したことがある.その分野こそがメタゲーム理論の別名 (あるいは発展形?) である.経済学部の採用は特定の候補者を想定しているわけでもないのに,しばしばかなり (きわめて?) マイナーな分野というか,ひじょうに限定された分野を指定することがあった.たとえば「社会学」ならず「社会ネットワーク分析」で公募したりした.(近年ポピュラーになってきているとはいえ,日本語の分かる「社会ネットワーク分析」専門家がいったい何人いるんだ?) こちらは古いというよりは新しすぎてマイナーな例かもしれない.

さいわい Monderer and Tennenholtz (2006) の解消法は同時決定ゲームから外れるものではないと思う.仲介者は提供するサービスをそれぞれのプレーヤーが利用してくれたかどうかを知ったうえで行動することから時間は暗黙的には入っているといえるかもしれない.しかしふたりのプレーヤーに注目すれば,べつに相手が仲介サービスを利用しているかどうかを確認した上でこちらの戦略を決めているわけではないため,同時決定のゲームと考えてよいだろう.また,「仲介者」といっても「仲裁」とか「調停」のような積極的なことをするわけではない.まったく受動的に行動するだけの「媒介」にすぎないコンピュータープログラムだったりするわけだから,「仲介者」をプレーヤーから外すことも正当化できるだろう.

以上のように考えると「新しい」解消法と言えると思うんだが,なんかなじみがあるような気がして仕方ない.

参考文献. Dov Monderer and Moshe Tennenholtz. Strong mediated equilibrium. In Proceedings of AAAI 6, 2006.

【2007/06/18 01:54 】
| 社会科学 | コメント(0) | トラックバック(1) |
豊稔池ダムのゆる抜きとかジュースとか

論文をいちおう完成して共著者に送った今週は,オフィスの引っ越し準備なんかをして過ごした.引っ越しのせいか,あるいは遠路はるばる訪れた元女子学生相手に激しく腰を使う作業をやりすぎたせいかは知らないが,腰の状態がかなり悪化してしまった.

6月13日は GSM (地域マネジメント研究科) の教員らしく,地元の公共事業と企業経営の調査に出かけてみた.高松から国道32号線を辿り (とちゅう山越うどん店の経営状況を視察し),琴平に寄って街のさびれ具合を視察し,(はじめて通る) 377号線を辿って大野原町の豊稔池ダムを目指した.ところが知らないあいだに 377 号線を外れてしまい,観音寺佐野線に入るところをミスしてしまった.そういえば一昨年もこのあたりで迷った覚えがある.この地域の道路案内はこれ以外にも分かりにくいものがあった.というか,案内があるべきところにないことが多かった.地域マネジャーとして,関係者に改善を勧告しておきたい.

さて,40分ほどさまよった末に観音寺佐野線に入っら,豊稔池方面の入り口が見えた.そこに進入したら,なぜか対向車線にクルマが多い.「ゆるぬきでもあったんだろうか.まさかこんな早い時期にはやらないだろうけど……」現場に着いてみると,勢い良く水が放流していた.居合わせたおじさんがゆる抜きだったと教えてくれえた.(四国新聞によれば,普通の年よりひと月半くらい早いらしい.池を管理する豊稔池土地改良区の村上明秋理事長は「少なくともここ30年間で、6月にゆるを抜いた記憶はない」という.) 写真をいくつか掲載しておこう.クリックすれば拡大する.

古城の風格
古城の風格

水はいっぱい
水はいっぱい

放水口ふたつ
放水口ふたつ

吹き出す水
吹き出す水

近づいてみる
近づいてみる

奥から見ると
奥から見ると

見上げれば
見上げれば

最後にゆる抜きの状況が把握できる図
最後にゆる抜きの状況が把握できる図

オマケ: 豊稔池の写真検索

帰りは国道11号線をたどって丸亀城を経由し,海に近い道路を走って高松へ向かった.本日の市場調査・経営調査先はこの春できた「イオン高松ショッピングセンター」だ.大きな建物で,中身はアメリカのモールみたいな感じだった.最近郊外にできるショッピングセンターはこういう感じのが多いのだろう.ついついペットシティに寄って,トイプードルの子供はぬいぐるみみたいだなと感心したり,三毛猫の子供が噛み合うのを応援したり.

だがここに来た本当の目的は (日本にない) Jamba Juice のようなジュース屋が高松で成り立つかどうか下見することだ.試しに 3階のヒッチングポストで300 円のフルーツミックスジュースを飲む.その隣のデザート王国のジュースも試そうと思ったが,今回はやめた.もひとつ試しに一階のジャスコ付近で見つけた店で 400 円の濃厚なまんごジュースを飲む.生のフルーツをとりだして目の前でミキサーするパフォーマンスはなし.この量でこの値段だから,ジャンバジュースがアメリカのサイズで出すとすれば,もっと高くなるんだろうか.ジュース (スムージー) 一杯に500円?600円?700円? ううむ,やはり日本で Jamba 方式の店を展開するのは厳しいんだろうか.

【2007/06/16 16:40 】
| | コメント(0) | トラックバック(0) |
米国有名大学に今すぐ行く方法

Google Maps の Street View (ストリート・ビュー) でちょっとバーチャル旅行をしてみた.ほんとは以前住んだ街を歩いてみたかったのだが,いまのところ載っていない.かわりに以前ひとりで訪れたことのある大学に行ってみた.当時は時間が余ったついででいったので,下調べはできていなかった.

空港に荷物を置いて出発.たぶんまちがったバスに乗ったのかな.乗り換えたバスで降りたのはこちらのショッピングセンター付近だった.高松郊外のショッピングセンターとあんまりちがわない気もする.

そこから歩いて30分ほど歩いてキャンパスに到着.路上で出会ったアジア人女性に「Hoover Tower はどちら?」と英語で尋ねた.けっこう大きなキャンパスなので,ひとりで歩くのはたいへんだった.もう少し来る方法なんかを調べておけばよかったと思った.言うまでもキャンパスは美しかったけど.見どころもたいして把握していなかったボクはとりあえず大学内の教会や本屋に行ってみた.日本人風のかわいい女の子が Stanford University T シャツを買っていた.帰りの交通手段もよく分からなかったのでその子に尋ねてみようかと思い立たったのか,なにか別の理由があったのか,記憶は定かではないが,その子を追いかけて行った.でも彼女は自分のクルマに乗って行ってしまった.

おそらく帰りはこの広場前のバス停でバスに乗って,最寄りの駅から電車に乗って (電車が写ってる!),サンフランシスコのチャイナタウンに (ラーメン食べに) 向かったと思う.

地図も写真もドラッグできる.じっさいに旅行するより楽じゃん.

【2007/06/03 08:17 】
| 大学 | コメント(0) | トラックバック(0) |
| ホーム |
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。