YONのドバトブログ

YONの土鳩ブログ

ゲーム好きの鳩"YON"がツイッターでは言い切れないことについて書き連ねるブログ

「ハリーポッターと賢者の石」の論理パズルは、書籍中の情報だけで解けるか【数学・Python】

書籍「ハリーポッターと賢者の石」(1999)には、以下のような論理パズルが登場する。

 

テーブルに横1列に並んだ7本のビンと紙が置かれており、紙には次のように書かれている。前進の薬と後退の薬の場所はそれぞれどこか?

前には危険 後ろは安全
君が見つけさえすれば2つが君を救うだろう
7つのうちの1つだけ 君を前進させるだろう
別の1つで退却の道が開ける その人に

2つの瓶はイラクサ酒
残る3つは殺人者 列にまぎれて隠れてる
長々居たくないならば どれかを選んでみるがいい
君が選ぶのに役に立つ 4つのヒントを差し上げよう

まず第1のヒントだが どんなにずるく隠れても
毒入り瓶のある場所は いつもイラクサ酒の左 (※)
第2のヒントは両端の 2つの瓶は種類が違う
君が前進したいなら 2つのどちらも友ではない

第3のヒントは見たとおり 7つの瓶は大きさが違う
小人も巨人もどちらにも 死の毒薬は入ってない

第4のヒントは双子の薬 ちょっと見た目は違っても
左端から2番目と 右の端から2番目の 瓶の中身は同じ味

「ハリーポッターと賢者の石」 (著 J.K.ローリング / 訳 松岡祐子) より引用
太字、米印引用者

※「毒入り瓶のある場所は いつもイラクサ酒の左」は"You will always find some on nettle wine's left side"の誤訳であり、「イラクサ酒の左にはいつも毒入り瓶がある」が正しい

 

物語の登場人物のハーマイオニーはスネイプ先生が用意した上記の論理パズルを解き、一番小さな瓶の中身が前進の薬、右端の瓶の中身が後退の薬と見抜いた。というわけで書籍中に既に答えは示されているのだが、答えを導く過程は全く書かれていない。せっかくなら自力で解いてみたいものだ。

しかし、上記のパズルを自力で解く上で問題がある。それは、7本それぞれの瓶の位置と大きさを示す記述や挿絵が無いこと。つまり読者にとっては第3のヒントが意味をなさない。書籍を読んだ当時、小学校低学年だった私は「実はこのパズルは第3のヒントがなくても解けるのでは?」と考え、自力でパズルを解こうとして親の嘲笑を買った。当時の私が最終的にどういう解答を出したのかよく覚えていないが、あまり釈然としなかったことは覚えている。

これから、数学やプログラミングなどのマグルの泥臭い武器を使って当時の私の疑問を解決してみる。つまり、問題文の記述だけを頼りに前進の薬と後退の薬の場所をどこまで特定できるかを検証する。

 

問題文だけを頼りに、実際に解いてみる

毒をP、イラクサ酒をW、前進の薬をF、後退の薬をBで表す。7本の瓶の内訳はP3つ、W2つ、F1つ、B1つであり、ヒントの内容は以下のようになる。

  • 第1のヒント Wの左隣には瓶があり、その中身はPである
  • 第2のヒント 両端の瓶の中身は異なり、かつどちらもFでない
  • 第3のヒント 無し
  • 第4のヒント 左から2番目と右から2番目の瓶の中身は同じ *1

第4のヒントから考える。FとBはそれぞれ1つずつしかないので、左から2番目の瓶と右から2番目にある瓶の中身はPかWである。

  1. 左から2番目の瓶と右から2番目にある瓶の中身が両方Pである場合
    両端の瓶の中身で場合分けする。ただし第2のヒントより、両端の瓶の中身は異なり、かつどちらもFでない。また第1のヒントより、左端の瓶の中身はWではない。

    (i) 両端の瓶の中身が左からP,BかB,Pのとき
    この時点での並び順は
    PP???PB
    BP???PP
    となる。しかし、真ん中の3つの瓶に対し、第1のヒントと矛盾することなくW,W,Fを入れる方法がない。よって不適。

    (ii) 両端の瓶の中身が左からP,Wのとき
    この時点での並び順は
    PP???PW
    となる。Pは全部で3本なので、残り1つのWが入る場所は左から3番目となる。残りはFかBとなり、考えられるパターンは以下の2通り。
    PPWFBPW
    PPWBFPW

    (iii) 両端の瓶の中身が左からB,Wのとき
    この時点での並び順は
    BP???PW
    となる。真ん中の3つの瓶の中身はP, W, Fのいずれか。Wが真ん中の3つの瓶のうち中央か右端にあるとき、その左隣にPが入り、残りにFが入る。Wが真ん中の3つの瓶のうち左端にあるとき、残り2つの並びはPF, FPどちらでもよい。よって考えられるパターンは以下の4通り。
    BPPWFPW
    BPFPWPW
    BPWPFPW
    BPWFPPW

  2. 左から2番目の瓶と右から2番目にある瓶の中身が両方Wである場合
    Wの左隣はPなので、この時点での並び順は
    PW??PW?
    となる。第2のヒントより右端はFでもPでもないので、Bであると分かる。残り2箇所の並びはFP, PFどちらでもよいので、考えられるパターンは以下の2通り。
    PWFPPWB
    PWPFPWB

以上より、考えられる瓶の並び順は以下の8通りである。

PPWFBPW
PPWBFPW
BPPWFPW
BPFPWPW
BPWPFPW
BPWFPPW
PWFPPWB
PWPFPWB

よって、Fの場所は左から3番目、4番目、5番目のいずれかであり、Bの場所は左から4番目、5番目、7番目のいずれかであるため、問題文の記述だけで前進の薬と後退の薬の位置を特定することはできない

 

「ハーマイオニーがパズルを解けた」という情報から解を絞る

問題文の情報だけでは前進の薬と後退の薬の場所は確定できないことが分かってしまった。

ここで終わるのも釈然としないので、1つ情報を追加してみよう。それは、「ハーマイオニーが、この論理パズルを解くことができた」という情報だ。私の持つ情報と、ハーマイオニーの持っていた情報の差は第3のヒントしかない。つまり、「特定の2箇所の瓶の中身が毒でないという情報を加えることで、前進の薬と後退の薬の場所が確定しなければならない」ことを考慮してみよう。

これを地道に探索すると、以下の2パターンが見つかる。

  1. 「左から2番目と3番目が毒でない」または「左から3番目と6番目が毒でない」という情報を追加すると、瓶の並び順がPWFPPWBと確定するので、前進の薬は左から3番目、後退の薬は左から7番目と確定する
  2. 「左から2番目と4番目が毒でない」または「左から4番目と6番目が毒でない」という情報を追加すると、瓶の並び順がPWPFPWBと確定するので、前進の薬は左から4番目、後退の薬は左から7番目と確定する

以上より、後退の薬が左から7番目(右端)であることは確定するが、前進の薬の位置は確定しない

 

結局どこまで解を絞れるのか

ハーマイオニーがパズルを解けたという情報を追加しても、後退の薬の場所しか確定しないことが分かった。しかも、考えられる瓶の並び順のパターンは

PWFPPWB
PWPFPWB

の2つであり、どこかの瓶の中身を試し飲みすることでこれらのパターンを区分しようとすると、毒を飲むリスクを必ず冒さなければならない。安全に見分けるにはやはり第3のヒントを活用するしかない。

以上の考察をまとめると

  • 問題文の内容だけを考慮したとき、前進の薬の場所も後退の薬の場所も確定しない
  • 問題文の内容に加えて「特定の2箇所の瓶の中身が毒でないという情報を加えると前進の薬の場所と後退の薬の場所が確定する」ことを考慮したとき、後退の薬の場所は右端だと確定するが、前進の薬の場所は確定しない。瓶の中身は
    左1 毒
    左2 イラクサ酒
    左3 前進の薬か毒。ここの瓶が最も小さいか最も大きいなら前進の薬
    左4 前進の薬か毒。ここの瓶が最も小さいか最も大きいなら前進の薬
    左5 毒
    左6 イラクサ酒
    左7 後退の薬

 

Pythonを使用してもう一度解く

せっかくなのでPythonによるプログラミングでもう一度解いてみよう。PPPWWFBの全順列のうち、条件を満たすものを抽出する。計算量O(n^2 \cdot n! \cdot n)の愚直な実装であるが、瓶が7本しかないのでこれでも高速に動作する。使用コードは下記の通り。

import itertools

N = 7

def condition1(bins):
    for idx in range(N):
        if idx == 0:
            if bins[idx] == "W":
                return False
        elif bins[idx] == "W" and bins[idx-1] != "P":
            return False
    return True

def condition2(bins):
    return bins[0] != bins[-1] and bins[0] != "F" and bins[-1] != "F"

def condition4(bins):
    return bins[1] == bins[-2]

# 3条件を満たすパターンを格納
ans = []
for bins in set(itertools.permutations(["P", "P", "P", "W", "W", "F", "B"])):
    if condition1(bins) and condition2(bins) and condition4(bins):
        ans.append(bins)

ans.sort()
print(len(ans))
for x in ans:
    print(*x)

# どこか2つ(dwarf, giant)がPでないという情報を追加するとF,Bの位置が一意になるものを抽出
true_ans = []
for idx1 in range(N-1):
    for idx2 in range(idx1+1, N):
        fb_index = set()
        tmp = []
        for pattern in ans:
            if pattern[idx1] != "P" and pattern[idx2] != "P":
                fb_index.add(tuple([pattern.index("F"), pattern.index("B")]))
                tmp.append(list(pattern) + [idx1+1] + [idx2+1])
        if len(fb_index) == 1:
            true_ans.append(tmp)

true_ans.sort()
print(len(true_ans))
for x in true_ans:
    print(x)

 

以上のコードを実行すると、下記が出力される。考察結果と一致していることが確認できる。

8
B P F P W P W
B P P W F P W
B P W F P P W
B P W P F P W
P P W B F P W
P P W F B P W
P W F P P W B
P W P F P W B
4
[['P', 'W', 'F', 'P', 'P', 'W', 'B', 2, 3]]
[['P', 'W', 'F', 'P', 'P', 'W', 'B', 3, 6]]
[['P', 'W', 'P', 'F', 'P', 'W', 'B', 2, 4]]
[['P', 'W', 'P', 'F', 'P', 'W', 'B', 4, 6]]

 

以上の考察を各ウェブサイトで確認する

やはり同様の疑問を持った人は過去にいたようで、過程は少々異なるものの、同じ結論に至ったサイトを複数確認できた。

The Riddle of the Potions

The Potions Puzzle

「賢者の石」の7つの瓶問題を解く

 

瓶の挿絵を与え、解答が定まるようにしたサイトも複数確認できた。最も小さい瓶と最も大きい瓶の位置は、考察と矛盾していない。

The Harry Potter Problem by Roger Howe Mathematics Teacher February 2002

「ハリーポッターと賢者の石」の論理クイズを解いてみよう

「ハーマイオニーの論理」に挑戦!

 

f:id:YON_4:20191104122750j:plain

The Potion Puzzle より

 

 

 

*1:イラクサ酒、毒、前進の薬、後退の薬の味に関する情報がないので、「同じ味」は「同じ中身」を意味することとする。この仮定をしない場合、何と何が同じ味か分からないので第4のヒントも意味をなさなくなり、このとき考えられる瓶の並び順は66通りとなる。ちなみに原文ではFourth, the second left and second on the right
are twins once you taste them, though different at first sightとなっており、味が同じというよりは「双子」、つまり中身が同じことを示唆している