論理クイズ「幼女と草原の風」が言いようのない面白さ

問題文は短くて、分かりやすく明快。

答えにたどり着くのも難しくはない。

しかしそれを証明しようとすると……とたんに難解になります。

正しい方向性を立てて挑んでください。

問題

草原に幼女たちが立っている。
人数は奇数。

幼女間の距離はすべてバラバラである。

幼女たちは、自分から一番近い幼女だけをずっと見ているように言いつけられている。

このとき、誰からも見られていない幼女が必ず1人はいるらしいのだが本当だろうか。

本当でも嘘でも、論理的に証明してほしい。

さあ、解いてみよう!

はい。

「問題文も短いし楽勝だ」と思ってると手こずります。

ヒントはなし。

強いて言うなら、「最終文を除いて全文章が極めて大きなヒント」です。

少し下にスクロールすると答えがあります。

 

 

 

 

正解

本当。

この条件では、誰からも見られていない幼女が必ず1人は存在する。(証明は後述)

解説

導入

分かるような分からないような結論ですね。

これから「誰からも見られていない幼女が1人はいる」ことを証明してみましょう。

「幼女の人数は奇数」ということも大きなポイントになってきます。

「最短距離の幼女2人」で考える

まず、「幼女間の距離がもっとも短い2人の幼女AB」に着目します。

「幼女たちは自分から一番近い幼女だけを見る」という前提から、この2人(AB)は互いにずっと相手を見ています。

ですが、もし他にもABのうち1人を見ている幼女がいれば、1人の幼女が2人以上の人から見られていることになります。

「1人が2人以上から見られている」

この時点で誰からも見られていない幼女がどこかにいることになります。

もう少し踏み込んでみましょう。

もしここで、「誰からも見られていない幼女はいない」と仮定すると、互いの距離がもっとも短い幼女ABは他の誰からも見られていないことになります。

そして、ABが他の誰からも見られていないのであれば、他の幼女たちの事情に何の変化も及ぼしていないことになり、ABを考慮から除外することができます。

こうして2人ずつ除外していくことをずっと繰り返していく(次の最短距離間の幼女2人に着目していく)と、幼女の人数は奇数なので、最後に幼女が1人だけ残ります。

その幼女は当然、誰からも見られていません。(互いを見ている幼女2人を除外していったから)

これは途中で出てきた「誰からも見られていない幼女はいない」という仮定と矛盾します。

よって、誰からも見られていない幼女がどこかに必ず存在するわけです。

まとめ

ぱっと見は簡単そうなのですが、しっかり証明しようとすると数学的発想が必要になる問題です。

それもそのはず、この問題の初出は1966年の第6回全ロシア数学オリンピックの第1問。

きちんと解けた方は数学の実力があります。

少女の数学クイズ」とかやってみると面白いかもしれませんね!!!!!

参考

6th ASU 1966 problems

解説はPeter Winkler 『MATHEMATICAL PUZZLES』より一部抜粋

140字以内の問題文

草原に幼女たちが立っている
人数は奇数
幼女間の距離はすべてバラバラ
幼女たちは、自分から一番近い幼女だけをずっと見ているように言いつけられている
このとき、「誰からも見られていない幼女が必ず1人はいる」ということを証明してほしい