"Sum and Product Puzzle"をPythonで解いてみた

昔、多分NetNewsのfj.sci.mathかどこかだと思うが、次のような問題が流れていた。

司会と A さん, B さんがいます.
司会「今から Joker を除いたトランプ 52 枚から無作為に 2 枚を取り出し, A さんにはその二数の積を, B さんには和を教えます. その数から元の二数が何であるかを考えてください」
A, B 「はい」
司会「(B さんにわからないよう, A さんに積を教える)」
司会「(A さんにわからないよう, B さんに和を教える)」
A さん「教えてもらった数からは元の二数はわかりません」
B さん「私もわかりません. でも, A さんが『わからない』と言うのはわかっていました」
A さん「それなら私はわかりました」
B さん「それなら私もわかりました」
さて, A さん, B さんの聞いた数はそれぞれいくつでしょう?

これだけで答えが1つに特定できることが驚きであり、取ってあった。それをたまたま見つけたので、もう一度やってみた（解説は後述）。
一見どこから手を付ければ良いのかわからないが、「A さんが『わからない』と言うのはわかっていました」からBさんの数字を考えてみると、ほぼ答えまで絞られるので、解くのにそれほど時間はかからない。

NetNewsの元の投稿は探せなかったが、その代わりに、この問題の元ネタが見つかった。元の問題は1969年に発表されたもので、その後に様々なバリエーションが作られ、一連の問題は"Sum and Product Puzzle"と呼ばれているらしい。参考文献[1]によると、1979年にMartin Gardnerが"the Impossible Puzzle"と呼んで紹介した頃の英語版の1つは次のようなものだったらしい。

Two numbers m and n are chosen such that 2 ≤ m ≤ n ≤ 99. Mr. S is told their sum and Mr. P is told their product. The following dialogue ensues:
Mr. P: I don’t know the numbers.
Mr. S: I knew you didn’t know. I don’t know either.
Mr. P: Now I know the numbers.
Mr. S: Now I know them too.

In view of the above dialogue, what are the numbers?

元の2数の範囲が2〜99なだけで、後は全く同じである。おそらく同じようにして解けるのだが、範囲が広い為に格段に面倒である。
どうせ、部分的にヒューリスティックに絞り込んでいるが、しらみ潰しに探しているのと大差無い。おそらく、整数の範囲を制限しているので、しらみ潰しに探す以外に解法は無いと思う。（例えば「2より大きいあらゆる偶数は素数の和で表せる」というゴールドバッハ予想も、整数の範囲を制限しているので、単独では使えない。m+nとしてあり得る188は7+181 = 31+157 = 37+151 = 61+127 = 79+109であり、99以下の素数の和ではないので、m,nが共に素数である組み合わせが無い。）
プログラミングの勘を取り戻す為のリハビリを兼ねて、プログラムを作ってしらみ潰しに探すことにした。

#!/usr/bin/python

MIN = 2
MAX = 99

def good_factors(p):
    """Generates pairs of factors of p"""
    return [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m <= n and m*n == p]

def good_summands(s):
    """Generates pairs of summands of s"""
    return [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m+n == s and m <= n]

def fact1(m, n):
    """Mr. P: I don't know the numbers."""
    return len(good_factors(m*n)) > 1

def fact2(m, n):
    """Mr. S: I knew you didn't know."""
    for (m_, n_) in good_summands(m+n):
        if not fact1(m_, n_):
            return False
    return True

# This is not necessary but just writing straightforward
def fact3(m, n):
    """Mr. S: I don't know either."""
    return len(good_summands(m+n)) > 1

def fact4(m, n):
    """Mr. P: Now I know the numbers."""
    fact2_compliers = [(m,n) for (m,n) in good_factors(m*n) if fact2(m,n)]
    return len(fact2_compliers) == 1

def fact5(m, n):
    """Mr. S: Now I know them too."""
    fact4_compliers = [(m,n) for (m,n) in good_summands(m+n) if fact4(m,n)]
    return len(fact4_compliers) == 1

result = [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m <= n and fact1(m,n) and fact2(m,n) and fact3(m,n) and fact4(m,n) and fact5(m,n)]

print "result =", result

これを実行すると、(m,n)の正解である(4,13)が出力される。
MIN = 1, MAX = 13にすると、冒頭のトランプの問題の元の2数も計算できる。

但し、心持ち関数型プログラミングっぽくしてみたが、これだととても時間がかかる（Intel Core i5 1.6GHzのCPUでも2分以上）。次のように、good_factors()とgood_summands()が計算結果をキャッシュするように書き換えると、20倍くらい速くなった。

good_factors_dict = {}
def good_factors(p):
    """Generates pairs of factors of p"""
    if not good_factors_dict.has_key(p):
        good_factors_dict[p] = [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m <= n and m*n == p]
    return good_factors_dict[p]

good_summands_dict = {}
def good_summands(s):
    """Generates pairs of summands of s"""
    if not good_summands_dict.has_key(s):
        good_summands_dict[s] = [(m,n) for m in range(MIN, MAX+1) for n in range(MIN, MAX+1) if m+n == s and m <= n]
    return good_summands_dict[s]

◆参考文献
[1] "Sum and Product in Dynamic Epistemic Logic"
H. P. van Ditmarsch, et al.
J Logic Computation (2008) 18 (4): 563-588
First published online: December 21, 2007
http://www.cs.otago.ac.nz/staffpriv/hans/sumpro/sumandproduct06.pdf

この記事を書いている途中に気付いたが、Wikipediaに、ずっと短くて高速で動くPythonのコードがあった。

■トランプの問題の解答と解説
以下、AさんとBさんが聞いた数をそれぞれA,Bとする。
例えば、B=6だと、元の2数が(1,5)の場合にA=5となり、元の2数が(1,5)だとわかるはずなので、矛盾する。従って、Bは1+素数や1+1ではない。また、B>7だと、元の2数の一方が7の場合にAが7の倍数になり、元の2数の一方が7であることがわかるはずなので、矛盾する。そう考えると、Bは5か7しかない。
この時点で、元の2数は(1,4)(2,3)(1,6)(2,5)(3,4)のどれかであり、A,Bは(A=4,B=5), (A=6,B=5), (A=6,B=7), (A=10,B=7), (A=12,B=7)のどれかである。
A=6だと、Bが5か7とわかってもB=5, B=7のどちらもあり得るので、「それなら私はわかりました」とならない。A=10やA=12だと、Bが5か7とわかるとAさんにはB=7とわかり、元の2数が特定できるが、Aさんが元の2数を特定できたからといってBさんにはA=10なのかA=12なのかが特定できないので、「それなら私もわかりました」とはならない。
残るはA=4, B=5だが、Bが5か7とわかるとAさんにはB=5と特定でき、A=6なら特定できないはずなので、BさんはA=4と特定できる。従って問題文を満たす解はA=4, B=5のみであり、元の2数は(1,4)である。

Weblog on mebius.tokaichiba.jp

"Sum and Product Puzzle"をPythonで解いてみた

コメント