 |
 |
|
|
|
|
|
|
6 × 6 のマス目上でプレーする試合を想像してほしい。足の速い選手（ランナー）が北のマス目をスタートし，相手チーム３人の選手（ディフェンダー）を巧みにかわして南のゴールへ走り抜けようとしている。
このゲームでは選手は決められた方向にしか動けない。ランナーは自分が今いるマス目から前か斜め前へ動く（南，南東，南西）。足がとても速いので，自分の番のときに２マス進める（前か斜めに２マス進んでもよいし，桂馬跳びでもよい）。ディフェンダーは足が遅く，自分の番のとき１マスしか進めないが，それぞれが今いるマス目の隣ならどの方向に動いてもいい。同じマスに留まることもできる。 |
|
 |
|
ランナーが最南列にたどりつけば，ランナーの勝ち。ディフェンダーに前３方向（南，南東，南西）の隣マスすべてを占有され，ランナーが動けなくなったら，ディフェンダーの勝ちだ。
ランナーは最北列のどのマス目から出発してもよいとしよう。３人のディフェンダーは，ランナーの出発点を見きわめてから，自分の最初の位置を決めることができるが，そのマス目は，ランナーから３マス以上離れていなくてはならない。 |
|
右上図に，初期配置の１例を示した。この状態からランナーがまず２マス進む。次にディフェンダーたちがそれぞれ１マス進む。次はまたランナーの番という具合にゲームは続く。
ランナーまたはディフェンダーのどちら側に必勝法があるだろうか？そして，その方法は？ |
|
| 次はルールを少し変えてみよう。ディフェンダーたちは３人とも最南列から出発しなければならないとする。その場合の初期配置の例を右下図に示す。この条件では，どちらの側に必勝法があるだろうか？ |
|
 |
|
 |
|
訳者 坂井公（さかい・こう）
筑波大学数学系助教授，理学博士。専門は計算機科学。 |
著者 Dennis E. Shasha
ニューヨーク大学クーラント研究所教授。専門は計算機科学。 |
|
|
|
 |
|
| |
