« ビデオテープの経年劣化 | メイン | 講義の日 »

解の数え上げ

数学、ピアノ、チェスプロブレムのすべての分野において天賦の才を発揮しているNoam Elkiesという数学者がいることは、以前にもふれた。そのElkies氏が2005年に発表した論文 "New directions in enumerative chess problems" (The electronic journal of combinatorics, 11(2)) がちょっと面白いので紹介しよう。

チェスプロブレムであれ、フェアリー系を含めた詰将棋であれ、解となる手順は完全に一意的に定まっていなければならない。ああ指してもこう指しても詰むというのでは問題にならないからだ。ただプルーフゲームやシリーズヘルプメイトなどのように、問題の形式によっては「指し手の順番に違いがあるだけで、手順自体は本質的に一つ」ということがよく起こり得る。普通はこれも不完全やキズもの扱いを受けてしまうが、ここで見方を変えて、その手順前後解が全部でいくつあるかを数えてみたらどうだろうか。これがこの論文で提起されている問題である。

Bonsdorff-Vaisanen.png例としてElkiesがあげているのが、1983年のBonsdorff-Väisänenによる14手のシリーズヘルプメイトである(出典はSuomen Tehtäväniekat)。シリーズヘルプメイトというのは、まず指定された手数だけ連続して黒が指し、白が黒を1手で詰ませることができるような局面を作ることを求める問題のこと。つまりここでは黒が14手続けて指し、自らが1手で詰まされるような局面にしなければいけない。白が指せるのは最後の1手だけで、チェックをかけられる駒はb6のポーンだけであるから、このポーンを動かしたらその瞬間に黒のキングがメイトになるような手順を求めよということである。なお最後の局面も含め、黒が指し続けている間、黒は白にチェックをかけてはならない。

Bonsdorff-Vaisanen-solution.pngちょっと考えるとすぐに分かるが、目的を達成するためには左のような局面にするしかない。つまり、2つの黒のポーンを両方ともビショップに昇格させ、a7とb8に配置するのである。手数を勘定してみると、1つ目のポーンが
(a5-)a4-a3-a2-a1-e5-b8-a7
で7手、もう1つのポーンが
(a6-)a5-a4-a3-a2-a1-e5-b8
で7手となり、ちょうど14手である。かくして白が最後にポーンをb7と進めてメイトとなる。

さてこの問題、ポーンをビショップに変えて決まった経路で移動させるしかないから、解は本質的には1つである。しかし手順の順番はかなり可能性がある。最初のポーンをビショップに昇格させ、a7まで持って行ってから2つ目を動かし始めてもいいし、2つのポーンをつかず離れず動かしていってもよい。では全部でいくつあるだろうか?正解は、この手の数え上げの問題でしばしば登場する、カタラン数と呼ばれる数になる。今の場合、それぞれのポーンが所定の位置に収まるまでに7手ずつ要しているので、答えは C7=14!/7!8!=429となる。

こんな調子で、Elkies氏はいろんな問題に対して解の個数を数え上げてみせる。中には解の個数がフィボナッチ数だったり、ちょうど100万だったり、論文が発表された年と同じ2005だったりする問題もある。創作に長けてくると、望んだ数だけ解を持つ問題を創ることもできてしまうようだ。実際、この論文は大数学者Richard Stanleyの60歳を記念して書かれたものだが、ちゃんと60個解があるプロブレムもElkies氏は創ってみせている。やはり天才というしかない。

SeriesHelp9-2.pngSeriesHelp9-1.pngさて、同じことを将棋で考えてみよう。去年の今頃、たくぼんさんのページで「実戦初形より後手が連続して指し、先手から1手詰の局面を創れ」というお題が出されたことがあった。すなわち、初形からのシリーズヘルプメイトである。右図はそのときに出た解の詰め上がり局面で、いずれもまず後手が連続して9手指し、次に先手が1手指して詰んでいる(後手が指し続けている間、どちらかの玉に王手がかかるような手は指してはいけない)。解は一意ではないが、どちらも違うのは手順前後の分だけだ。さてそれぞれ、解は全部でいくつあるだろうか?

トラックバック

このエントリーのトラックバックURL:
http://monsieur.ddo.jp/cgi-bin/mt_3/mt-tb.cgi/380

コメント

さすがエルキース…

面白いとは思いますけど、むしろ、これを組合せ論の雑誌の、しかもスタンレイみたいな大物の記念論文に投稿するところが凄いし、accept した編集の茶目っ気が偉いです。

まあ確かに、普通の数学の論文ではないですからね。
「数学者はいつもこんなふうに具体的な問題と具体的な数字を相手にしているのか」と、
外の世界の人に実情とやや異なるイメージを持たれてしまうかもという気もします。

こんばんは。
ずっと前、プロブレムの世界大会がクロアチアであったとき、晩餐会が異様に盛り上がり、Elkiesが自作をピアノ演奏したことがあります。そのときには、彼のピアノのことを知らなかったので、ぶったまげた記憶あり。

これはわかしまさん、コメントをありがとうございます。
Elkiesのピアノ演奏は、本人のホームページに録音が
置いてあったのを聴きましたが、完全にプロの腕前ですね。
「天は二物を与えず」どころか、三物を持っているんだからいやになってしまいます。

コメントを投稿