昨日のパズル の解答。 不可能であることが、以下のようにパリティ(偶奇性)を用いて簡単に証明できる。
チェス盤の市松模様に注目し、二つの石が同色のマスにある場合を「偶配置」、 異なる色のマスにある場合を「奇配置」と呼ぶことにする。 異なるマスに黒石一つ、白石一つを置く方法は 64 かける 63 通りあるが、 このうち、偶配置は 64 かける 31 通り、奇配置は 64 かける 32 通りあって、後者の方が 64 通り多い。 一方、ある配置からどちらかの石を上下左右のどのマスに動かしても、 偶配置は奇配置に、奇配置は偶配置に変わることに注意せよ。 よって、この動かし方を続ける限り、 辿った配置における偶配置と奇配置の数の差は 0 か 1 にしかならない。 しかし、全ての配置では奇配置の方が 64 多いのだった。 ゆえに、全配置を一度ずつ辿ることはできない。
この問題の出典は、2001 年のモスクワ数学オリンピックだそうだ(その割にはちょっと易しめ？)。 私は Futility Closet で知った。
今日も蒸し暑い……。 鶏そぼろとレタス炒め丼のお弁当を作って出勤。 午前、午後と粛々とプログラミング。 昼頃まではいつもの蒸し暑さだったが、 午後から雲が増えてきた。 気象情報によれば、夕方以降、激しい雷雨の注意とのことだったので、 早めに退社。
帰宅して夕食の支度。御飯を炊いている間に、 トマトと胡瓜と茹で卵のサラダ、大和芋の短冊で、冷酒を五勺。 のち、納豆に茗荷、茄子の糠漬、 鯖の中骨と切干し大根で船場汁、御飯。 夜の読書は 「『ユリシーズ』の謎を歩く」（結城英雄著/集英社）など。
昨日の
「√２の√２乗の√２乗」問題
の解答。
一般に x の y 乗の z 乗は x の「y かける z」乗に等しいことに注意すれば、
√２の√２乗の√２乗は√２の 2 乗だから、答は 2。
これより、無理数の無理数乗が有理数になりうることが分かる。
なぜならば、√２の√２乗は有理数か無理数のどちらかだが、
もし有理数ならばこれがその例であり、
もし無理数ならばこの√２乗が 2 になることがその例である。
簡単だけれども、はっとする証明だ。
蛇足ながら、
この証明からは√２の√２乗が有理数か無理数か分からないことに注意。
出典は
Futility Closet "A Simple Proof"。
今日もまだそれほど暑くない。 珈琲、果物、ヨーグルトののち、 納豆、焼き海苔、蕪の糠漬、浅蜊の味噌汁、御飯の朝食をとり、 お弁当を詰めて出勤。 昼食の持参のお弁当。茄子とピーマンと鶏肉のレッドカレー。 茄子が余っていたので、つい使ってしまったが、 レッドカレーの味にあわないし、色も悪くなるなあ。 夕方退社して帰宅。 夕食は、目刺しを焼いて、冷奴(茗荷と生姜)、玉葱のピクルス、 じゃがいもと若布の味噌汁、大和芋のとろろ御飯（大葉と自家製ポン酢）。 食後の散歩がてら、近所の図書館まで本を借りに行く。 帰宅してお風呂に入り、湯上がりにグレープフルーツを半分。
昨日の
「二つの卵」パズルの解答。
答は 14 回。
まず、14 階の窓から卵を一つ落とす。もし、割れてしまったら、
もう一つの卵を使って、一階から 13 階まで順番に試していく(最悪の場合で 1 + 13 = 14 回)。
もし、割れなかったら、さらに 14 - 1 = 13 階分上がって 27 階から卵を落とす。
もし、割れてしまったら、もう一つの卵を使って、15 階から 26 階まで順に試す
(最悪の場合で 1 + 1 + 12 = 14 回)。
もし、割れなかったら、さらに 13 - 1 = 12 階分上がって……、
と以下、これを繰り返す。どの場合でも最悪は 14 回で卵の強さが判明する。
実際、最後まで卵が割れない場合でも、
14 + 13 + 12 + ... + 1 = 105 > 100 なので、OK。
卵が三つ、あるいは一般に n 個の場合を解く鍵は （卵が二つの時もそうなのだが）、 このパズルの本質が「再帰」であると気付くことにある。 つまり、上の解答をよくよく見直してみると、 まず最初の階で卵を落とし、 もし割れなかったら、 その階より上の階に対して、同じパズルを解くことになり、 もし割れたら、 その階より下の階に対して、卵が一つ少ない同じパズルを解くことになる。 つまり、このパズルを解くには、一段階小さな、このパズルを解けばよいわけで、 それを解くには、さらに一段階小さな、このパズルを解けばよいわけで、 さらにそれを解くには……と、どんどん遡って行くと、 最終的には卵が一つでビルが一階建ての場合に帰着し、答が得られる。
このパズルは IT 業界で人気があるようだ。 gxxgle 社やMS 社の面接試験に出たという都市伝説があるが、 本当かどうか定かでない。 このパズルの面白く詳しい解説として、 blog 記事 "The Two Egg Problem"(英文)がある。 また最近翻訳された、 「続・とっておきの数学パズル」(P.ウィンクラー著/坂井公・他訳/日本評論社) にも紹介されており、その記述によれば、初出は "Which Way Did the Bicycle Go"(D.E.Konhauser, D.Velleman, S.Wagon, 1996)という本かも知れない。
昨日の
「最も難しい論理パズル」の解答と解説。
色々な考え方と答があるが、おそらく以下が最もエレガントだろう。
まず、尋ねる妖精が正直でも嘘吐きでも、妖精語の「ジャー／ダー」が「はい／いいえ」
のどちらでも、答が知りたい質問Ｘが正しければ「ジャー」、
正しくなければ「ダー」という答が返ってくるような、
質問Ｘを埋め込んだ質問Ｘ’を作成する。
次に、この質問Ｘ’を使って、「ランダム妖精」でない妖精を同定する。
そして、その妖精に対して質問Ｘ’を使い、各妖精の種類を確定する。
「はい／いいえ」で答える二者択一の質問Ｘに対して、 「もしＸと尋ねたら、あなたは『ジャー』と答えますか？」 という質問Ｘ’を考えよう。 すると、この質問に対しては、 尋ねられたのが「正直妖精」でも「嘘吐き妖精」でも、 妖精語の「ダー／ジャー」が「はい／いいえ」のどちらであっても、 埋め込まれた質問Ｘが正しければ「ジャー」、正しくなければ「ダー」と答える。 俄に信じ難いが本当なので、是非ご自分で確認していただきたい。 もし、「ランダム妖精」の意味が、気分次第でその質問に対して正直になったり、嘘吐きになったりする、 ということならば、これで全ての問題が解決したことになる。 三人それぞれに、誰がどの妖精かという質問Ｘを埋め込んで、質問Ｘ’を訊けば良い。
しかし、「ランダム妖精」の定義が、質問を無視して、でたらめに （例えば、コイン投げの結果に応じて）「ジャー」か「ダー」を答える、 ということならば、上のトリックは通用しない。 そこでもう一つアイデアが必要になる。 妖精をＡ，Ｂ，Ｃとして、そのＡに、 「Ｂは『ランダム妖精』ですかと尋ねたら、あなたは『ジャー』と答えますか？」 と尋ねるのだ。 もしＡが「ランダム妖精」でないならば、上のトリックが効いて、 答が「ジャー」ならＢは「ランダム妖精」、「ダー」ならば「ランダム妖精」ではない。 しかし、Ａ自身が「ランダム妖精」ならば、上のトリックは効かないので、 何の情報も得られない……ように思われるが、そうではない。 なぜならば、この場合、Ａが「ランダム妖精」なので、Ｂは（そしてＣも）「ランダム妖精」ではない。 よって、答が「ジャー」ならば、Ｂが「ランダム妖精」であるか、Ａ自身が「ランダム妖精」であり、 いずれにせよＣは「ランダム妖精」ではない。 また、答が「ダー」ならば、Ｂが「ランダム妖精」ではないか、Ａ自身が「ランダム妖精」であり、 いずれにせよＢは「ランダム妖精」ではない。 これによって、「ランダム妖精」ではない妖精が同定できる。
そして、「ランダム妖精」ではない妖精に対して、妖精の種類を確定する質問Ｘ’をすればよい。 例えば、「あなたは『嘘吐き妖精』ですかと尋ねたら、あなたは『ジャー』と答えますか？」と、 「Ｃは『ランダム妖精』ですかと尋ねたら、あなたは『ジャー』」と答えますか？」など。 （もし、質問は各妖精に対し一つずつに限る、という条件を付けると、答はないと（私は）思う。 微妙に異なるバージョンについて、「一人一つ」の場合に解があるかどうか、 あるいは、「全部で二回」の場合に解があるかについて、 いくつか議論と結果があることまでは調べたが、 このバージョンではどうなのか自分で詰め切れなかった。もし分かったら教えて下さい。）
このパズルには微妙に設定の違う（or 設定の曖昧な）バージョンが色々あるのだが、 おそらく起源は論理学者の R.スマリヤンによるもので、 「この本の名は？」(R.Smullyan: "What is the Name of This Book?", (1978))に登場している。 その後、計算機科学者の J.マッカーシーが「ジャー／ダー」が「はい／いいえ」 のどちらか分からないバージョンに拡張したらしい。 それを哲学者で論理学者の G.Boolos が論文 "The Hardest Logic Puzzle Ever"(Harvard Review of Philosophy, No.6, pp.62-65,(1996)) でとりあげて、「最も難しい論理パズル」と呼ばれるようになった。 これが、このパズルを最初に曖昧さのない形で定式化した論文と思われる。 私がこのパズルを知ったのは最近、「最も難しい論理パズルがさらに難しく」 というプレプリントが arXiv に出ていたから ("The hardest logic puzzle ever becomes even tougher")。 この問題に興味を持たれた方は、とりあえず、 Wikipedia 項目 "The Hardest Logic Puzzle Ever" から始めるとよいと思う。
この blog を読んで下さっている方は非常に知的であるようで、 紹介するパズルが高度であればあるほどアクセス数が多い、 という統計が得られている。 今回も最高難易度にチャレンジしてみましたが、どうでしょう？
また良く眠れ過ぎて寝坊した。 珈琲、苺ジャム入りヨーグルト、バナナだけの朝食を済ませ、 お弁当を詰めて慌てて出勤。 昼食は持参のお弁当。塩豚ごはんと、蕪の糠漬。 いつもの如く、ナンバクランチングをしたり、 「テスト」と称して Twitter など SNS を見たり、つぶやいたり。 夕方退社して、帰宅。 夕食は、鰤の漬け焼き、焼き茄子に生姜醤油、冷奴、蕪の味噌汁、御飯。 食べるときになって、全部醤油味だよ、と気付いた。修行が足りんなあ。 風呂上がりに、ライチを 3 粒。
昨日の
「キューブをたどる」パズルの解答。
26 個のキューブを面で接した隣へとたどることで一度ずつ訪れることは不可能。
最も簡単な証明方法は、こういった問題の常套手段「パリティ・チェック」を使うことだろう。
このルービックキューブが黒と白の市松模様に塗られているとしよう（隅が黒としておく）。
すると、26 個のキューブの色は 14 個が黒、12個が白である。
面で接した隣へ隣へと移動すると、キューブの色は黒と白が交互に変わっていくのだから、
もし可能であればキューブの色は半々、つまり 13 個ずつでなければならない。
しかし実際は 14 個と 12 個なので、それは不可能。
この問題は Futility Closet で知ったが、パリティ（偶奇性）が決め手になる類似のパズルは沢山ある。 例えば、非常に有名なものとしては、 8x8 のチェス盤の右上と左下の 2 マスを除いた 62 マスに、 1x2 のドミノを敷き詰めることができるか、という問題。 パズルではなくて、シリアスな数学の問題でも、 パリティに注目したとたんに不可能性が分かる、ということは良くあるので、 数学者にとってパリティはツールボックスの中の愛用の道具の一つだろう。
昨日の
「行列マジック」
パズルの解答。
数学には「よくよく考えてみると当たり前なんだけれども、やっぱり不思議」
ということがあるもので、これはその典型例。つまり明らかだけれど、トリヴィアルではない。
2 行 2 列から試すのが筋で、しばらくすると（多分、4 x 4 あたりで）悟りが開けるのだが、
一般的な証明にチャレンジしてみよう。しかも、
数学記号を使わないと却って分かり難いところを、あえて、普通の言葉で説明してみる。
よーく考えると、「アーハー！」体験できること間違いなし。
すでに各行の中では大きい順に並び換え終わったとしよう。 どれでもいいのだが、一つの行について考える。 3 番目の行としておこうか。 さらにその行のどこでもいいから、二つの場所に注目する。 5 番目と 8 番目としておこう(5 番目の数の方が大きい)。 ここで、第 5 列、8 列それぞれの中で、大きい順に並び換えたあとでも、 この二箇所にある数の大小関係が変わらないことを示せばよい。 列の中で並び換えると、この二つの場所には各列で 3 番目に大きい数が入る。 列で並び変える前は、5 列目の数それぞれは同じ行の 8 列目の数より大きかった。 すると、第 8 列の数の中で、3 行目 5 番目の数 X より大きい可能性があるのは、高々 3 - 1 = 2 つしかない。 なぜなら、他の数は全て、X より小さいか(列で並び換える前に X と同じ行にあった）、 X より小さい数より小さい（X より小さい数と同じ行にあった）。 一方、現在 8 列目 3 行目にある数は 8 列目の中で大きさで 3 番目なのだから、 X より小さい。証明終わり。
説明するとややこしいが、分かってしまうと、どうにも明らかである。でも不思議。 もちろん、この性質は正方行列に限らず、 全く一般のどんなサイズの行列でも、どんな成分でも(順序づけ可能なら)、成り立つ。 衝撃的な性質の割にあまり知られていないが、古典的な定理である。 D.Knuth の "The Art of Programming" によれば、「Boerner の定理」らしい。
昨夜も二峰性睡眠だったのだが、6 時間寝たあとさらに 3 時間寝たので、 二峰性と言うよりは単なる「二度寝」なのかも知れない。 珈琲、梅ジャム入りヨーグルト、バナナで目を覚ます。 いただきものの手製の梅ジャムは今日で終了。ありがとうございました。 いつもの通り、目刺し、胡瓜と人参の糠漬、納豆、菠薐草と油揚げの味噌汁、御飯の朝食のあと出勤。 今日はお弁当作りはなし。 昼食は近所のインド料理屋にて。 夕方、退社。 帰宅して夕食の支度。 ポトフの残りと、鶏笹身と胡瓜の梅肉和え、高野豆腐、菠薐草のおひたし。 米が明日の朝食とお弁当用の分くらいしか残っていなかったので、今夜は素麺。
昨日の
「少女自身の本」パズルの解答。
夫が 45 歳、妻が 15 歳。
問題の意味は、「結婚したとき夫の歳は妻の歳の 3 倍でしたが、その 15 年後には 2 倍になりました。結婚した時点ではそれぞれ何歳だったでしょう」。
この問題の他、雑多なパズルやクイズが沢山掲載されていたこの "Girl's Own Book" は、アメリカではけっこう有名な本らしくて、 ご高齢の女性の方々に一種の郷愁を抱かせる類の本のようだ。 初版は 1834 年、 小説家でもあり奴隷制度廃止と女性の権利拡大の活動家でもあった Lydia Marie Child が著者。 多くの版を重ねて広く出版され、最近でも再版されたことがあるとか。 検索すると google eBook の形などで無料閲覧することもできるので、 興味を持たれた方はご覧あれ。
朝から外が暗く、肌寒い。今日は雨の一日になるようだ。 珈琲、キウィとヨーグルトで目を覚ましてから朝食の支度。 目刺し、納豆、茄子の糠漬、しめじと若布の味噌汁、御飯。 お弁当を適当に詰めて出勤。 昼食は持参のお弁当。 豚肉の味噌焼き、キャベツ千切り、酢大豆玉葱、えのき茸の塩蒸し、御飯。 夕方退社。 冷たい雨の中を帰宅して、まずお風呂に入って身体を温めてから、夕食の支度。 安物の日本酒を冷やで五勺ほどで冷奴、えのき茸の塩蒸し、母の手製の筍と蕗の煮物。 そのあと、出来合いの鰻の蒲焼で櫃まぶし、しめじと若布の味噌汁、茄子の糠漬。
昨日の
「壊れた数字錠」
パズルの解答。
必要かつ十分なトライの回数は 32 回。
数学的な問題を考える方法は人によって色々だが、
私自身はとりあえず幾何的な直観に頼るタイプだ。
鍵の可能性は 8x8x8 で 512 通りある。
これを角砂糖のような小さなキューブを 8 行 8 列 8 段に積んだ立方体で考えよう。
つまり x 行目の y 列目の z 段目にあるキューブを"xyz"という鍵だと思う。
このとき、ある鍵をチェックすると、錠が壊れていることから、
その鍵に対応するキューブの他、
そのキューブの左右、前後、上下方向にある 7 個ずつの 21 個のキューブも調べたことになる。
よって問題は、できるだけ少ないキューブをチェックすることで立方体全体を調べなさい、
という幾何的な問題に言い換えられる。
このイメージを用いるとすぐに、立方体全体ではなくて、
手前の角の 4x4x4 の小さな立方体とその対角の向こう側にある小さな立方体の中だけ考えれば十分なことに気付く。
さらに対称性より、手前だけ調べれば向こう側も同じだ。
これなら簡単な試行錯誤で、チェックすべき 16 個のキューブが発見できる。
結局、全体で 32 個チェックすれば十分。ここまでは易しい。
あとは「31 個以下ではどうしてもカバーできない」ことを証明しなければならない。 これをきっちり論理的に詰めるのが難しい。 このパズルの難易度が高いのは、このパートをきちんと示すのに数学的な証明能力が必要だからである。 とは言え、幾何的な直観が役立つのは同じ。 例えば、「鳩箱論法」の類似より、 31 個でカバーできたとしたらどこかの段には 3 個以下しかチェックすべきキューブがない。 この 3 個がある段は一番下の段だと仮定しても一般性を失わない。 さらにこの 3 個はこの位置にあると仮定してもよい……という感じで、 状態を絞り込んでおいてから、カバーしているキューブの個数を勘定すれば良いのだが、詳しくは省略。
"Mathematical Mind-Bender"(P.Winkler著/A K Peters)によれば、 このパズルは 1988 年に東ドイツで開催された数学オリンピックに初出とのこと。
今朝は雨。 珈琲、果物、ヨーグルトなどで目を覚ましたあと、いつもの目刺し納豆定食。 お弁当を詰めて出勤。 昼食は持参のお弁当。蒸し鶏、茹で新じゃが、玉葱ピクルス、牛蒡と人参のきんぴら、御飯。 夕方退社。 雨で外が結構寒かったので、帰宅してまずお風呂。 湯船で 「ほろにが菜時記」（塚本邦雄著/ウェッジ選書） を読む。 お風呂からあがって夕食は、冷奴（生姜と木の芽）、新じゃがのポテトサラダ、蒸し鶏のスープで作った汁麺（具は小松菜のみ）。
「信頼できる友人と三つの茶碗」問題の解答。
答は 75 パーセント。
条件付き確率、またはベイズ確率の考え方による確率的判断によれば、こうなるだろう。
理由は下の図形を見ていただければ、明白だと思う。
全体の 10 分の 1 を占める右の黄色い部分が友人の証言が嘘だった場合、
左の赤緑青の部分はそれぞれ、友人の証言が正しくて茶碗の下に指環があり、
それが一つめの茶碗、二つめの茶碗、三つめの茶碗である場合で、
それぞれ全体の 10 分の 3 ずつを占めている。
今、赤と緑の場合は消えたから、
残りの黄色と青のエリアに対する青のエリアの面積比が答の 75 パーセントである。
この問題の面白いところは、多くの人がなぜか、「30 パーセント」と答えることだ。
こういった設定での確率的判断の問題は主観が入りうるので、
いや、それは私の考え方や信念とは違う、という反論もなくはないだろうが、
いくらなんでも 30 パーセントという答はおかしい。
ちなみに、この問題は作り物めいているようでも、 思いがけなくも高度な実験物理学の方面で議論になったりする。 つまり、「信用できる友人」とは現状で説得力を持っている仮説または理論、例えば超対称性理論であり、 「茶碗の下を確認する」ことはある実験、例えば粒子加速器実験の結果を知ることである。 興味のある方には、こちらの blog の記事 "Bayes and SUSY" が面白いと思う。
今日もいい天気だ。 珈琲、梅ジャム入りヨーグルト、バナナのち、 ししゃも、木の芽入り納豆、キャベツの酢漬け、大根と油揚と木の芽の味噌汁。 朝食の支度の合間に糠床を返す。手を入れるとちょっと温かい。 発酵が始まったのかも。捨て漬けの野菜はまだ塩が立って、酸味を感じない。 お弁当を作って、出勤。 昼食は持参のお弁当。新じゃがとチーズ入りのオムレツ、新玉葱と二十日大根のピクルス、 昆布の佃煮、御飯。 夕方退社。 帰宅して夕食の支度。 玉葱と二十日大根と胡瓜のサラダ、新じゃがとチーズ入りのオムレツの残り、アーリオオーリオ。 食後に美生柑を一つ。
昨日の
「正三角形の庭」
パズルの解答。
このパズルに正面からアタックして、
木の間の距離の最小値の最大値を与える配置を構成的に求めようとすると大変なことになってしまう。
簡単に解くポイントは、言わゆる「鳩箱論法」（別名「ひきだし論法」、「ディリクレ原理」、etc.）。
正三角形の各辺の中点を結んで、庭を 4 つの小さな正三角形に分けよう。
4 つの（小）三角形に 5 本の木を植えるのだから、どのように植えたところで、
どこかの三角形の中には 2 本以上の木を植えざるをえない。
したがって、この小さな三角形の中で 2 本の木を最大に離した距離、
つまり小さな三角形の辺の長さより、全ての木の間の間隔を離すことはできない。
一方、元の大きな正三角形の頂点と各辺の中点のうちの 5 つに木を植えれば、
これは上の最大の距離間隔の限界を満たす例になっている。
よってこれが答である。
（この類似のパズルは良く知られているが、このヴァージョンは
"Elbow Room"(from "Futility Closet")
を私が少し変形したもの）
この「鳩箱論法」はシリアスな数学でも良く使われるテクニックで、 単純ながら、時に非常に強力に働く。 今、10 個の鳩箱があって、そこに 11 匹以上の鳩を納めるなら、 どのように入れようが、どこか一つの箱には二匹以上の鳩が入らざるえない。 その箱がどこかは分からないし、 一匹も鳩がいない箱があるかも知れないし、 鳩が大勢入っている箱があるかも知れないが、 兎に角、二匹以上入っている箱が存在することだけは間違いない。 これが「鳩箱論法」である。 全く当たり前の事実だが、 これが思いがけなくも、複雑な問題を一刀両断に解く鍵になることがある。
今朝は晴天。切干し大根が良く乾きそうだ。 紅茶、梅ジャム入りヨーグルト、バナナで目を覚まして朝食の支度。 目刺し、キャベツの炒めもの、納豆、菠薐草と油揚の味噌汁、御飯。 お弁当を適当に詰めて出勤。 昼食は持参のお弁当。 韮玉、茹で新じゅが、若竹煮、二十日大根のピクルス、梅干し、御飯。 昼休みに神保町を散歩して、 「わたしの台所」(沢村貞子著/光文社文庫) と「暮しの手帖」の 4-5 月号を買う。 「暮しの手帖」に言われるまでもなく、確かにこの時期は糠漬を始めようかと思うんだよなあ……
夕方退社して、帰宅。 先にお風呂。湯船で「わたしの台所」を読み、雑な生活態度を反省。 夕食の支度。 新じゃがと絹莢の大蒜炒め、菠薐草のおひたし、木の芽入りのだし巻き、そして今年初の素麺。 ちゃんと素麺つゆを作るのが面倒だったので、だしを薄口醤油と味醂で割った八方地。 食後にオレンジを一つ。
昨日の 「１８世紀イギリスの女性雑誌より」 パズルの解答。 答の二つの数字は符号の違いを入れて 4 組あるが、 具体的な答合わせは問題から明らかなので省略。 この問題に隠れている「ある特別な数」とは黄金比。 答は黄金比とその二乗になっている。 二つの数の積と二乗の差が等しい、ということは、 x 対 y が (x + y) 対 x に等しい、という黄金分割の関係に他ならない。 また、二つの数の積と三乗の比が等しいことより、 片方が一方の平方になっている。
朝カレーにしてみた。食後にパパイヤのヨーグルト和え。 朝風呂に入ってのち、読書と昼寝。 昼食は菠薐草と油揚のアーリオオーリオ。食後にオレンジ一つ。 午後、西方から宅急便。 昨日、いい筍があるから送りましょうか、と声をかけていただいて、 「ぜひ」と返事しておいたら、筍の他、大量の野菜が届いた。 無駄にしないように計画的に消費するなり、保存食化しないと。 とりあえず筍を下茹で。 その間に、ミントを生け、春キャベツの半分と二十日大根の全部を酢漬けにした。 夕食は早速、筍御飯。 筍、油揚、木の芽でシンプルに。 鯖の梅干し煮、菠薐草のおひたし、三つ葉の澄まし。 食後にミントティ。 夜は、料理の仕込みの他、読書など。 「ウォッチ・メイカー （上・下）」（J.ディーヴァー著/池田真紀子訳/文春文庫）、 読了。ディーヴァーは何を読んでも安定して面白い。 今日も静かな良い一日だった。
昨日の
「大富豪と仲の悪い子供たち」
のパズルの解答。
色々と方法はあるが、以下のものがもっともエレガントだと思う。
「遺産を隠した地点を中心に秘密の円を描いて、
その円周上の 5 点をランダムに選び、その一つずつを各子供に教える」。
協力した三人は、自分たちの三点から秘密の円を特定でき、その円の中心に遺産がある。
二つ以下の点では円周を定めることはできないが、
三つの点があれば円周が一つ決まる。
そしてこの三点は五つの内のどれでもよい。
このパズルは、分散コンピューティングに現れる問題とその解法の一つを題材にしたもの。 （例えば、 "What scientific concept would improve everybody's cognitive toolkit?" より、計算機科学者 J.Kleinberg の回答 "E Pluribus Unum" の中に例として挙げられてる。） 原理的には、上のパズルの解答を使えば、 一つのデータを 5 つに分散して、そのうちの 2 つまでは失われても大丈夫で、 しかも、2 つまでの秘密が漏洩しても安全であるようにできる。 「クラウド」と呼ばれる分散コンピューティングの背後では、 一つのデータを分散しながらもそれが一つのデータであるかのように振る舞わせつつ、 安全性と秘密を守るために、巧妙な数学的アルゴリズムが色々と使われています。
昨日の
「百人の囚人の賭け」
パズルの解答。
まず、囚人たち全員で各人に各名札を割り当てる。
名札に書かれた名前と混乱するので、「担当」という言葉を使おう。
例えば、一列に並んでいる名札に対して、
一番左の名札は囚人Ａの「担当」、次の名札は囚人Ｂの「担当」、
というように各人への名札の割り当てを約束する。
この割り当ては全員で一つ決めさえすれば何でも良い。
各囚人は部屋に入ったらまず自分の「担当の」名札を調べる。
そして、その名札に書いてある名前の囚人の「担当の」名札を調べる。
さらに、その名札に書いてある名前の囚人の「担当の」名札を調べる、
という手順を自分の名前に当たるか、五十個を調べるまで続ける。
これが、答の戦略である。
今、初めてこの答を知った人は、よほど数学的直観に優れた方でない限り、
「はあ？そうしたところで確率はほぼゼロのまま変わらないでしょう？」
と思ったことだろう。その気持ちは良く分かる。
最近の私は老境に至ったせいか、自分の愚かさをフランクに直視できるようになってきたので、
正直に認めてしまうが、私も答を知ってしばらくの間、その意味が分からなかった。
何故、これで囚人全員ともが釈放される確率が 30 パーセント以上にもなるのか？
以下で、ちょっとくどいくらいに説明してみよう。
数学の言葉で言えば、「ランダム置換のサイクル長の分布の性質による」、 ということなのだが、とりあえず小さな例で具体的に説明する。 数学が得意な方は次の段落を飛ばして下さい。最後の段落に一般的な説明と文献情報があります。
では、囚人が 4 人で、2 回以内に自分の名札をひけば釈放、というケースでやってみよう。 囚人の名前を A, B, C, D とする。 まずは例として、テーブルの名札は左から D, C, B, A の順に並んでいるとしよう。 もちろん、囚人たちはこのことを知らない。 まず名札の担当者を打ち合わせる。左から A, B, C, D と決めたとしよう。 囚人 A は部屋に入ると、自分の担当の名札、つまり一番左の名札を確認する。 その名札には D の名前が書いてあるから、次は D の担当の名札、つまり 4 番目の名札を確認する。 そこには A の名前が書いてあるので「当たり」。 囚人B, C, D についても同様に、全員 2 回で「当たり」をひけることが分かる。 では、別の例でやってみる。 名札が B, C, D, A と並んでいるとしよう。今回は、 囚人 A は 1 番目の名札を調べ、2 番目の名札を調べ、3 番目の名札を調べ、ようやく最後の 4 番目で自分の名札に当たる。 残りの囚人たちも同じく、自分の名札に行き着くのに 4 回かかってしまう。 この二つの場合の違いは何だろうか。 それは、自分の担当の名札から始まって、そこに戻ってくるまでの「輪」の長さである。 一つ目の例では、A と D の輪、B と C の輪になっていて、長さ 2 の輪が二つある。 一方、二つ目の例では、A, B, C, D が輪になっていて、長さ 4 の輪が一つある。 これが違いだ。 ポイントはこの輪の長さが短いケースがけっこう多いことである。 実際、数学的事実として、全ての輪が全体の長さの半分以下であるケースが30パーセントを越す。 この 4 つの名札の場合で考えてみると、名札の並べ方は全部で 24 通りあるが、 そのうちで、長さ 2 以下の輪しか含まない並べ方が 10 通りある。 確率で言えば、そのような並べ方にあたる確率は 10/24 であって、これはもちろん 30 パーセントより大きい。
ここでこの問題の本質をまとめれば、こういうことだろう。 囚人たちは、並び換えの中の「輪」という隠された構造に注目することで、 名札の並びの「美味しいところ」を調べることができ、 しかも、 内在的な性質を用いているが故に、それを指し示すだけで、つまり、 事前に了解しあっておくだけで、そのことが可能なのである。
では、数学が得意な方向けの説明。 結局、100 個の要素の置換に対して、自分の名前を含む巡回(サイクル)の長さが、 50 以下ならば「当たり」ということになるので、 その置換の中にある巡回の長さが全て 50 以下ならば全員が釈放される。 2n 要素の置換の中にある長さ k のサイクルの個数を数えることは、 組合せ論の易しいエクセサイズに過ぎない。ランダムな置換に対して、 長さが丁度 k (> n) のサイクルを含む確率が 1/k であることが分かるので、 囚人全員が「当たり」を引く確率は、 1 から 1/51 + 1/52 + ... + 1/100 を引いたものになり、31.18 パーセントを越える。 さらに言えば、囚人の数が無限大の極限では 1 - log 2 になる。 数学的な興味としては、この戦略は最善なのか、という疑問が当然浮かぶが、 その答はイエスであることが次の最近の論文で証明されている。 E.Curtin and M.Warshauer: "The Locker Puzzle", The Math. Intelligencer 28:1, 28--31 (2006). なお、最初にこのパズルの概念が現れたのは、情報科学系の論文 A.Gal and P.B.Mitersen: "The Cell Probe Complexity of Succinct Data Structures", Lec.Note in Comp.Sci 2719, Springer, 332--344 (2003)で、 著者たちも執筆時点ではこのような戦略があるとは思っていなかったそうだ。 以上の文献情報は、"Mathematical Mind-Benders" (P.Winkler 著/ AK Peters, Ltd.)で知った。
さらに註(28 Apr. 2012):
読者の方から指摘があり、
最後の段落で、「少なくとも一つ長さが丁度 k のサイクルを含む確率が 1/k」とおかしなことを書いていたのを訂正。
正しくは、k が置換の長さの半分より大きいとき、長さが丁度 k のサイクルを含む確率が 1/k。
k が全体の半分より長いのが味噌で、数えるのが易しい。
全体の長さを 2n とすると、長さ k のサイクルの要素を選ぶ方法が 2n 個から k 個選ぶ組合せの数
(2n)!/((2n - k)!k!) だけあり、
その要素の並び換えが (k - 1)! 通りあり、選ばなかった要素の並び換えが (2n - k)! 通りあるから、
長さ k のサイクルを含む置換はこれらの積をとって (2n)!/k 通りある。
置換の方法は全部で (2n)! 通りあるから、これらを一様として、求める確率は 1/k。
今日はちょっと気温が下がったようだ。 いつもの朝食のあと、襟巻をして出勤。 昼食は持参のお弁当。タイ風の炒めものかけ御飯。 夕方退社して、スーパーで買い物をして帰宅。 塩鮭を焼いて、他にだし巻き、蕪の漬物、菠薐草の味噌汁、御飯。 今日はだしがうまく引けたし、だし巻きも良い出来だった。 食後にペリカンマンゴーを一つ。 湯船の読書は、 「回想のシャーロック・ホームズ」（A.C.ドイル著/深町眞理子訳/創元推理文庫）より「海軍条約事件」。
昨日の 二本の釘に一本のひもパズルの解答。 雑すぎる絵ですが、分かってはいただけるかと。 このなかなかに小粋なパズルを、 私は "Mathematical Mind-Benders" (P.Winkler著/ A.K.Peters,Ltd./ 2007)で知った。 その Winkler 自身はダートマス大学数学科の院生 G.Genovese 氏から教わったそうで、 G 氏はヨーロッパのあちこちでこのパズルを耳にしたとのことだ。
今日も良い天気だ。 いつもの朝食のあと、適当にお弁当を詰めて出勤。 昼食は持参のお弁当。塩鮭、鶉卵の燻製、隠元の胡麻和え、蕪の漬物、御飯。 休憩時間の読書は、 "The Information Diet" (C.A.Johnson 著/ O'Reilly)など。 夕方退社して、近くの中華料理屋にて夕食。皮蛋と砂肝大蒜揚げを肴にビールを飲みつつ、 「回想のシャーロック・ホームズ」（A.C.ドイル著/深町眞理子訳/創元推理文庫）より 「〈シルヴァー・ブレーズ〉号の失踪」を読む。 子供の頃に最初に読んだ翻訳では馬の名前が「銀星号」となっていたので、 いまだに、「ああ、銀星号事件ね」と思ってしまう。 さらに水餃子を食べて、うらぶれたサラリーマン情緒を満喫して帰る。
昨日の
「婚約指輪のプロトコル」
パズルの解答。
B 君が A さんに指輪を送りたいとしよう。
まず、B 君が箱に指輪を入れ自分の南京錠をつけて鍵をかけ、A さんに郵送する。
A さんは箱が届き次第、その箱にさらに自分の南京錠もつけて鍵をかけ、B 君に送り返す。
B 君はその箱が届き次第、その箱から自分の鍵で自分の南京錠だけを外し、A さんの南京錠をつけたまま A さんに送り返す。
今回 A さんに届いた箱には、自分の鍵で開けられる自分の南京錠がついているだけなので、
無事に B 君からの贈り物を取り出せる。
ついでに言えば、A さんは箱が最初に届いた時点で、
プロポーズにイエスなら自分の錠前をつけて送り返し、
ノーならばそのまま送り返す、ということもできるので、なかなかよろしいプロトコルである。
昨日ほどではないが今日も温かい。流石にもう春なのだろう。 いつもの朝食のあと、お弁当を適当に詰めて出勤。 昼食は持参のお弁当。塩鮭、里芋の煮物、隠元の胡麻和え、菠薐草のおひたし、御飯。 夕方退社。 帰宅して夕食の支度。 肉骨茶、菠薐草と卵の炒飯。食後にグレープフルーツ。
昨日の 三叉路の島 パズルの解答。 まず、おおざっぱな「証明」。 いつまでも出発点に戻って来ないとすれば、 どこかでループが生じて同じところをぐるぐる回っているということだが、 そのループに入り込む道があるならば、 その交差点と次の交差点で「右、右」か「左、左」と曲がることになってしまうので、 このループが出発点自体を含まざるを得ない。 よって、必ず出発点に戻ってくる。
もう少し数学的な証明の格好をつけると、以下のようになるだろう。 道を歩いている状態は、どの道を、どちらの方向に歩いていて、 次に左右のどちらに曲がることになっているか、の三つで完全に決まる。 島には有限個の道しかないので、この状態も有限個しかなく、 ゆえに、いつか必ず同じ状態の繰り返しが生じる。 この繰り返しが初めて生じるところが出発点に他ならない。 なぜならば、ある状態から一つ手前の状態は唯一つに決まるので、 もしそこが出発点でないならば、 その一つ手前の状態も繰り返しであるはずで、 それは繰り返しが「初めて」生じたという仮定に反する。