このクイズは面白い！
面白いぞーーーーー！！！
問題
1〜5の番号が書かれた5つの箱がある。
箱は1,2,3,4,5の順で一列に並んでいる。
ネコはこの箱のどれか1つに隠れており、夜になると必ずひとつだけ隣の箱に移動する。
朝になった時、幼女は1つだけ箱を調べて、そこにネコがいるかどうか確認できる。
さて、いつか幼女はネコを見つけられるだろうか？
さあ、解いてみよう！
無理難題感。
ネコは1日1回移動するのに、調べられる箱は1日1つだけ。
そんな……順々に調べたとしても、昨日調べた箱にネコが入れ違いで移動してくる可能性とか、まだ調べてない候補をずっと往復している可能性とか。
考え出したらキリがない。
どうすれば解けるのでしょう？
ヒントはなし。
少し下にスクロールすると答えがあります。
正解
できる。
最適な行動を行えば、遅くとも6日目にはネコを発見できる。
解説
なぜ解けるのか
ネコは毎晩ひとつ隣の箱に移動する。
毎朝、確認できる箱は1つだけ。
少し考えてみても相当に厄介な問題です。
これを解く鍵は、「移動するネコ」と「確認する幼女」の非対称性にあります。
両者が移動・確認するのはともに「1つの箱」ですが、その選択肢には大きな差異が存在します。
ネコが移動するのは「今いる場所の隣の箱」に限られますが、幼女は「どの箱」でも調べられる。
これが突破口になります。
シンプルな場合
簡単な例で考えてみましょう。
「3つしか箱がない場合」はどうなるのか？
最適なのは、1日目に「2」の箱を確認することです。
ネコが見つからない場合、ネコは「1」「3」のどちらかの箱に隠れています。
なので、2日目も「2」の箱を確認すれば必ずネコを見つけることができます。
キーポイント
「箱を調べたがネコはいなかった」
ということ自体が非常に大きな情報になります。
「ネコがいる可能性のある箱」を限定できたわけですから。
そうです。
実は、見かけよりも「ネコの動き」はかなり限定的です。
最初からネコのいる位置を当てようとするのではなく、「ネコがいる可能性のある箱」を少しずつ排除していくような戦略をとれば最終的に必ずネコを見つけられます。
着目点
1〜5の数字が書かれた一列に並ぶ箱。
ネコは必ず1日1回だけ隣に移動する。
つまり1日ごとにネコは必ず「偶数の箱」から「奇数の箱」へ、あるいは「奇数の箱」から「偶数の箱」へ移動します。
箱の偶奇に注目することが最初の一歩です。
さて、複雑な問題に対処するときの方法は大きく分けて3つ。
「仮定」
「単純化」
そして「場合分け」
ネコの初期位置が「偶数の箱」か「奇数の箱」かで場合分けして考えていきましょう！
1日目にネコが「2」「4」の箱にいる場合
1日目：
「2」の箱を調べます。
「2」にネコがいる場合、ここで終了です。
「2」にネコがいない場合、「4」にネコが隠れています。
2日目：
「3」の箱を調べます。
ネコが「4」から「3」に移動した場合、ここでネコを発見できます。
しかしネコが「4」から「5」に移動した場合、当然ですがネコは見つかりません。
3日目：
「4」の箱を調べます。
2日目でもネコが見つからなかった場合、ネコは必ず3日目には「4」の箱にいます。
これでネコを見つけられました！
まとめましょう。
ネコが1日目に「2」「4」の箱に隠れている場合、
「2」→「3」→「4」
の順で箱を調べることで、遅くとも3日目にはネコを発見できる。
1日目にネコが「1」「3」「5」の箱にいる場合
さて、初日にネコが奇数番目の箱にいる場合を考えてみましょう。
といっても複雑な考察はいりません。
1日目にネコが「1」「3」「5」にいる場合、2日目にネコは「2」「4」のどちらかにいます。
ということは、上記の「ネコが「2」「4」の箱にいる場合」と同じ戦略が使えるはずです。
1日目「2」
2日目「3」
3日目「4」
の順で箱を調べてネコが見つからなかった場合、ネコが1日目に隠れていたのは「1」「3」「5」のいずれかだと分かります。
そして、この時点（3日目の朝の確認終了時）でネコが隠れているのも「1」「3」「5」のいずれかです。
ネコは「1日目夜」と「2日目夜」の2回だけ移動しているはずなので。
ということは、4日目の朝のネコは「2」「4」のどちらかに隠れています。
ここから1〜3日目と同様に、
4日目「2」
5日目「3」
6日目「4」
と調べることで、遅くとも6日目には確実にネコを見つけることができます。
一般化
「2」→「3」→「4」→「2」→「3」→「4」
このように調べることで、ネコの初期位置がどこであっても最大6日で必ず見つけられることが分かりました。
5つの箱は対称的です。
「2」→「3」→「4」という順序は逆でも問題ないため「4」→「3」→「2」という順も成り立ちます。
それを考慮すると、ネコを最短で見つけるための探索手順は以下の4通りです。
「2」→「3」→「4」→「2」→「3」→「4」
「2」→「3」→「4」→「4」→「3」→「2」
「4」→「3」→「2」→「2」→「3」→「4」
「4」→「3」→「2」→「4」→「3」→「2」
視覚化
文字だけでは少し分かりづらいかもしれません。
最後に、「ネコの動き」と「確認手順」を表にして見てみましょう。
| 箱1 | 箱2 | 箱3 | 箱4 | 箱5 | |
| 1日目 | ◯ | 確認 | ◯ | ◯ | ◯ |
| 2日目 | × | ◯ | 確認 | ◯ | ◯ |
| 3日目 | ◯ | × | ◯ | 確認 | ◯ |
| 4日目 | × | ◯ | × | 確認 | × |
| 5日目 | ◯ | × | 確認 | × | × |
| 6日目 | × | 確認 | × | × | × |
「◯」は「ネコが存在する可能性がある」
「×」は「ネコが存在する可能性がない」
「確認」は「その日の朝にネコの存在を確認した」
ということをそれぞれ示しています。
日が進むごとに「ネコが存在する可能性のある箱」がどんどん限定されていくことに注目してください。
6日目、「確認する箱」以外の箱においてネコは存在できないことからも、これまでの手順が正しいことが分かります。
まとめ
とても面白い問題でしたね！
この問題は、Google・Microsoftといった世界的IT企業の就職採用面接の時にも使われているそうです。
世界は論理的思考能力を求めている……。
実に面白い。
参考
Can You Solve The Hiding Cat Puzzle? Tech Interview Question
Can You Solve The Cat In The Box Logic Puzzle?
