パズルの国のアリス

交差しない弾道(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 ジャックに伝えられた方法自体は少しも難しいものではない。当然だが,上から見たときの弾道は直線である。従って,標的の設定で弾道が交差しているようであれば,その交差をほどくように各自の標的を単純に交換していくのだ。

 例えば,エースはエース,2は2を狙うと決めてあれば,下図のように弾道のいくつかは交差しているかもしれない(簡単にするため,兵士はハート,スペードとも5人にした)。

 この場合は,オレンジ色で示した弾道2つ(♠A→♥Aと♠2→♥2)が交差しているので,スペードのAと2は標的を交換する。そうするとその交差は解消する(下図,青の弾道)。

 この処理を弾道の交差がなくなるまで,次々と繰り返せばよいのである。もちろん,その当の交差が解消しても,他のところに別の交差ができないとは限らない。場合によっては,この処理によって交差の数が増えてしまうことだってある。では,何ゆえに,この処理を続けることで交差がやがて消えてしまうと断言できるのだろうか?

 実は,その問いに対する答えは,弾道の長さの総和を考えることにある。上の2つの図を見比べると,違いはオレンジ色と青の弾道だけであるから,その長さの総和も,オレンジ色の弾道と青の弾道の分だけ異なる。三角形の2辺の和は1辺より長いから,オレンジ色の弾道の長さの和は明らかに青の弾道の長さの和より大きい。従って,交差している弾道を先のようにほどいていくと,交差箇所が減っていくという保証はないが,弾道長の総和は確実に小さくなっていくのである。

 1人が1人ずつを狙う場合,一般にn人の兵士に対する標的の指示の仕方はn!通りあるが,この数はしょせん有限だから,弾道長の総和がそれ以上小さくならない狙い方がある。この狙い方が交差する弾道を含まないことは言うまでもない。

 上の例で挙げた5人ずつの兵士配置の場合,手順によっては別の結果になることもあるが,例えば下図のような狙い方をすれば,弾道は交差しない。

 しかしながら,一般にランダムに配置されたハート兵士とスペード兵士がn人ずつの場合,弾道が交差しないように標的を設定するという問題は,解くのに相当に手間がかかりそうである。各兵士の標的が与えられたとき,その弾道が交差するか否かは多項式時間で判定できるので,いわゆるNP問題であるのは明らかだが,NP完全なのか,それともユークリッド平面幾何の性質をうまく使って,多項式時間くらいで簡単に解ける問題なのか,興味深いところである。ご存知の読者がおられれば,是非,お教えいただきたい。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです