インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

17:第3種解読可能数

17

私が中学生のころハマっていた同人サイト『DQと共に』に何故か載っていた論理問題とその解答を紹介します。

古典的論理問題

完璧な論理的思考を行うことができる3人がいる(A, B, Cとする)。 Cは2以上の相異
なる整数であって、その和が100未満であるような2数を考え、Aにはそれらの積を、Bにはそれらの和を教えた。その後、CはA, Bに対し「もとの2数を答えよ。」と問うた。Cがそのような行動を取ったことをA, Bの2人は知っているが、相手がどの数を教えられたかは互いに知らない。そして、A, Bは以下のような会話を行った:

A: さっぱり分からない。
B: そうだと思ってた。私も分からない。
A: え?じゃあ、分かった。
B: ん?なら私も分かった。

2人の会話が真実を述べているものとするとき、Cが考えた2数を答えよ。

論理問題の解答

Cの考えた2数をx, yとし、1 < x < y, x+y < 100とする。また、 n=xy, m=x+yとする。すなわち、Aはnを、BはmをCから教えられている。まず、任意の素数pに対し、n=pまたはn=p^2とはなり得ないことに注意する。

定義 和が100未満であるような相異なる2つの真の約数の積として書く方法が(2数の入れ替えは同じとみなして)ちょうど1通りしかない自然数のことを第1種解読可能数とよぶ。

相異なる素数の積、素数の3乗、素数の4乗は第1種解読可能数である。その他にも、318 = 2\times 3\times 53などがある(6\times 53しかない)。 このとき、明らかに次が成り立つ:

補題1 「A: さっぱり分からない。」が真となるための必要十分条件は、nが第1種解読可能数ではないことである。

次に、Bの発言を考察する。

S:=\{ l \in \mathbb{Z} \mid 5 \leq l < 100, lを相異なる2つの2以上の整数の和として表したとき、それらの整数の積はどの表し方に対しても第1種解読可能数ではない\}

と定義する。

補題2 「B: そうだと思ってた。 私も分からない。」が真であるための必要十分条件はm \in Sである。更にS = \{11, 17, 23, 27, 29, 35, 37, 41, 47, 53\}が成り立つ。

証明. 明らかにm\geq 5である。前半の主張は完璧な論理的思考を行うという仮定により、A, Bは補題1が成り立つことを知っていることからわかる(「そうだと思ってた。」の部分が重要)。2数の積が第1種解読可能数となるような和への分け方が存在するようなl\in \mathbb{Z} (5\leq l < 100)Sの元の候補から外していくことが出来る。まず、Goldbach 予想により、mは奇数でなければならない(もちろんGoldbach予想は未解決であるが、100未満で成立することは容易に確認できる。或いは、A, B, CはGoldbach予想を証明出来ているのかもしれない)。 つまり、候補は

5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51,
53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99

である。
2p (pは奇素数)が第1種解読可能数であることから、2+pを候補から消すことが出来る(もちろん、2+p < 100のときのみを考える。以下、同様)。これにより、

5, 7, 9, 13, 15, 19, 21, 25, 31, 33, 39, 43, 45, 49, 55, 61, 63, 69, 73,75, 81, 85, 91, 99

が消えて、候補は

11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97

となる。2p^2 (pp^2 > 100を満たす素数)が第1種解読可能数であることから、2p+p = 3pを候補から消すことが出来る。 これにより、51, 57, 87, 93が消えて、候補は

11, 17, 23, 27, 29, 35, 37, 41, 47, 53, 59, 65, 67, 71, 77, 79, 83, 89, 95, 97

となる。4p (p2p > 100を満たす素数)が第1種解読可能数であることから、4+pを候補から消すことが出来る。これにより、65, 71, 77, 83が消えて、候補は

11, 17, 23, 27, 29, 35, 37, 41, 47, 53, 59, 67, 79, 89, 95, 97

となる。6p (p2p > 100を満たす素数)が第1種解読可能数であることから、6+pを候補から消すことが出来る。これにより、59, 67, 79, 89, 95が消えて、候補は

11, 17, 23, 27, 29, 35, 37, 41, 47, 53, 97

となる。8p (p2p > 100を満たす素数)が第1種解読可能数であることから、8+pを候補から消すことが出来る。これにより、97が消えて、Sの元の候補は

11, 17, 23, 27, 29, 35, 37, 41, 47, 53

であることが示された。逆にこれらは全てSに属していることがわかる。そのためには、地道に各数を和に分けていって、それらの積が第1種解読可能数でないことを確かめればよい。これは145通り調べれば済むので、そこまで大変な作業ではない。 Q.E.D.

定義 l\in \mathbb{Z}\geq 5が次の条件を満たすとき、l第2種解読可能数とよぶ:

l2以上の相異なる整数で、その和が100未満であるようなものの積に分けたとき、それら2数の和がSの元であるような分け方がちょうど1つだけである。

完璧な論理的思考を行うという仮定から、「B: そうだと思ってた。私も分からない。」により、Aはm \in S であることを知るので、次が成り立つことが分かる:

補題3 「A: え? じゃあ、分かった。」が真であるための必要十分条件は、nが第2種解読可能数であることである。

証明. n2以上の相異なる整数で、その和が100未満であるようなものの積に分けたとき、それら2数の和として現れる整数がSの元であるような分け方が1つならばAはmがその数であると分かってx, yを決定でき、2つ以上ならばmが決まらないので「分かった」という発言にはならない。 Q.E.D.

定義 l \in \mathbb{Z}\geq 5が次の条件を満たすとき、lを第3種解読可能数とよぶ:

l \in Sであって、lを2以上の相異なる整数の和として表したとき、それら2数の積として現れる整数が第2種解読可能数であるような表し方がちょうど1つだけである。

補題4 「B: ん? なら私も分かった。」が真であるための必要十分条件はmが第3種解読可能数であることである。

証明. 完璧な論理的思考を行うという仮定からBは補題3を理解していることに注意する。 m2以上の相異なる整数の和として表したとき、それら2数の積として現れる整数が第2種解読可能数であるような表し方が1つならば、Bはnがその数であると分かってx, y を決定でき、2つ以上ならばnが決まらないので「分かった」という発言にはならない。 Q.E.D.

定理 第3種解読可能数は17のみである。 特に、x = 4, y = 13を得る。

証明. 補題2および補題4より、11, 17, 23, 27, 29, 35, 37, 41, 47, 53のうち、第3種解読可能数であるものを調査すればよい。まず、11, 23, 27, 29, 35, 37, 41, 47, 53が第3種解読可能数ではないことを示す。18は第2種解読可能数である。実際、

2+9 = 11 \in S, 3+6 = 9 \not \in S

である。 24も第2種解読可能数である:

2+12 = 14 \not \in S, 3+8 = 11 \in S, 4+6 = 10 \not \in S

18, 2411に付随する第2種解読可能数であるというように表現することにしよう。11に付随する第2種解読可能数が2つ存在するので、定義より11は第3種解読可能数ではないことが示された。他の数についても同様に証明することが出来る。各数に付随する第2種解読可能数を2つずつ挙げておく:

23 27 29 35 37 41 47 53
76, 112 50, 92 54, 100 96, 124 160, 186 114, 148 132, 172 240, 282

次に17が第3種解読可能数であることを示す。

17=2+15, 30=5\times 6, 5+6=11 \in S
17=3+14, 42=2\times 21, 2+21=23 \in S
17=5+12, 60=3\times 20, 3+20=23 \in S
17=6+11, 66=2\times 33, 2+33=35 \in S
17=7+10, 70=2\times 35, 2+35=37 \in S
17=8+9, 72=3\times 24, 3+24=127 \in S

より、17=4+13以外の17の2数の和への分け方においては、それらの積が第2種解読可能数ではない。一方、

17=4+13, 52=4\times 13 = 2\times 26, 2+26=28 \not \in S

なので、52は第2種解読可能数であって、17は第3種解読可能数であることが示された。よって、n=52, m=17, x=4, y=13である。 Q.E.D.