ある有名日記サイトに出ていた問題

オミクロン「私はこれから2から5000までの数字を2つ思い浮かべます。
そしてその積をピーターに、その和をスーザンにこっそり教えます。
私の考えた数がなんだったか答えてください」
　オミクロンが二人に囁くのを横でデイヴィッドが見ていた。
　ピーター「わからないな」
　スーザン「そうだと思った。私にもわからないわ」
　ピーター「わかったぞ」
　スーザン「私もわかった。でも、デイヴィッドにはわからないでし
ょうね。小さい方の数を教えればデイヴィッドにも大きい方の数を
当てることができるでしょう」
　さてオミクロンが考えた2つの数とは？

http://member.nifty.ne.jp/windyfield/diary0010a.html#08
ですね。

私には計算機なしでは解けそうもありません。

　　　　　　　 ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　 Λ＿Λ 　　|　 「〜教えて」と突発的な質問でスレッド建てても、
　（　´∀｀）＜　すぐ下がって放置されたり、荒らされちゃうよ。
　（ ΛΛ つ ＞――――――――――――――――――――
　　( ﾟДﾟ) ＜　 この問題はとんち系だね。
　　/つつ　　|　 「即答できたら理系」のスレッドに転載しとくよ。
　　　　　　　 ＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿_

★これが即答できたら理系★
http://cheese.2ch.net/test/read.cgi?bbs=math&key=970003634

デイヴィッドは判断不可能だろう、
とアタリをつけると2数が決まる、
と決め付けてしまう。（＾＾；

132番目の素数=743
7=4+3

オミクロン＝２ちゃんねらー

２と３、以外に該当する組はある？？？

ヒント：２人の会話から、２つの数は相異なる素数になる。

間違い。

オミクロンが考えた2つの数は4999と5000
デイヴィッドは小さい方の数が4999であることが分かれば
もう一方が5000であることが分かる。

はにゃ？

＞2つの数は4999と5000

そうすると和は9999。
2から5000までの数で
和が9999になるのは4999＆5000だけ。

和を聞いたスーザンが即答できると思うんですがどうか。

積も一通りだね。
5000*4999＝24995000
そもそも問題文がいろいろ解釈できるからね。

＞ピーター「わからないな」
＞スーザン「そうだと思った。私にもわからないわ」

この部分は
ピーター「(電卓がないと)わからないな」
スーザン「そうだと思った(私もあなたも数字が苦手だから)。私にもわからないわ」
と解釈できるし。

あと、オミクロンの考えた数がA、Bだとして
スーザンの言ってる「小さい方の数」が
min(A＠｀B)なのか、min(AB＠｀A+B)なのか。

つうか「とんち系」ですかコレ。
私には超重量級の計算問題にしか見えないンですけど…。

>11
登場人物の思考力は「十分に」高いと仮定するのがお約束かと。
例えば、ピーターの最初の発言は、
「与えられた２つの数の組は、共に素数でも、
ある素数pとその二乗でもない」と解釈すべき。

「小さい方」は、min(A＠｀B)かと。

条件を小分けにすると..
　　@1 ピーター「わからないな」
　　@2 スーザン「そうだと思った。私にもわからないわ」
　　@3 ピーター「わかったぞ」
　　@4 スーザン「私もわかった」
　　@5 スーザン「でも、デイヴィッドにはわからないでしょうね。
　　　　　　　　　　小さい方の数を教えれば、デイヴィッドにも
　　　　　　　　　　大きい方の数を 当てることができるでしょう」
# きっと前提に
# ピーター・スーザン・デイヴィッドはとても頭が良い
# がないと、この問題は成り立ちませんよね

スーザン「そうだと思った」から、スーザンに教えられた和は2つの相異なる
素数の和で表せない数。偶数は全て2つの素数の和で表せるから、スーザンに
与えられた和は奇数って考えたんですけど、いいんですかね？

> スーザン「そうだと思った」
「わからない可能性が高い」 を意味するかと思いきや、
実は 「わからないと確信していた」 だったのか.. なるほど。

考えられる組み合わせ
和：対応する積
１１：１８，２４，２８，３０
１７：３０，４２，５２，６０，６６，７０，７２
・・・・・
のうち、
@3 でピーターが「わかったぞ」と言えるやつに○をつけていけば・・・

とんちなんていってごめんなさい。m(__)m
３人が頭いいなら重量級ですね。
ちょっと考えました。
ただし、スーザンの「そうだと思った」からは、
彼女の聞いた数が奇数であることしか読み取れないと仮定します。
(奇数であることは10万以下の偶数に関するゴールドバッハ予想より)

以下、頭のいいデイヴィッドの視点から会話を再現します；
ピーター(以下ピ)「今のところ答えは一通りには定まらないな」
スーザン(以下ス)「私の聞いた数は奇数よ。」
ピ「スの聞いた数が奇数なら、答えは一通りに定まるな。
　僕の聞いた数はP*2^mで表せるからね。(ただしP；奇素数、m；2以上の自然数)
　さらに2P＜5000だ。」
ス「ピの聞いた数がP*2^mで表せるなら、私も答えが一通りに定まるわ。
　私の聞いた数をSとすると{S-2^k}の値が素数となるkが一つだけ存在するもの。」
ス「オミクロンの考えた２つの数のうち、素数の方をA＠｀2のべき乗の方をBとすると、
　5000＞B＞2500＞A＞B/2だから、Aをデイヴィッドに教えれば彼はBも答えられるわね。」

・・・というわけで、この仮定のもとでは
片方が2^12＝4096、
もう片方が2^11＝2048＜A＜2500を満たす素数A
という事まで絞れました。　

>Newsgroups: sci.math
>Subject: Think of two numbers...
>Date: Sat＠｀ 30 Sep 2000 20:08:55 +0100
>Message-ID: <[email protected]>
>
>Omicron: "I will think of two distinct integers＠｀ each in the range 2 to
>5＠｀000 inclusive. Then I will whisper the product of the numbers to
>Peter＠｀ and the sum of the numbers to Susan."
>
>Omicron does this＠｀ while David looks on.
>
>Peter: "I cannot work out the two numbers."
>
>Susan: "I knew that＠｀ Peter. And I cannot work out the two numbers
>either."
>
>Peter: "I can now work out the two numbers."
>
>Susan: "I can now work out the two numbers＠｀ too. But David will not be
>able to. However＠｀ he would be able to work out the larger number if he
>was told the smaller number."
>
>What are the two numbers that Omicron thought of?
>
>--
>
>Clive Tooth
>http://www.pisquaredoversix.force9.co.uk/

> 2048＜A＜2500を満たす素数

2053 2063 2069 2081 2083
2087 2089 2099 2111 2113
2129 2131 2137 2141 2143
2153 2161 2179 2203 2207
2213 2221 2237 2239 2243
2251 2267 2269 2273 2281
2287 2293 2297 2309 2311
2333 2339 2341 2347 2351
2357 2371 2377 2381 2383
2389 2393 2399 2411 2417
2423 2437 2441 2447 2459
2467 2473 2477

>17
「2 を含む」のが結構効いてて、
スーザンが「そうだと思わない」のは、2 + 奇素数の可能性もあります。
(あと、正確には 5000 以下の素数の和だから、
偶数でもすべてが捨てられるわけではない、と思う > 1)

だから、たとえば 2 と 9 でも、2*9=18=3*6 だけど
スーザンが 3+6=2+7 を聞いた可能性はないから、
ピーターはスーザンの言葉を聞いてわかることになる。
ただし、和が 11 だと 3＠｀ 8 でもピーターには「わかる」ので、
スーザンにはそれを聞いても「わからない」。

まあ、こうやって絞っていって、小さい数が重ならないものを
見つければいいんだろうけど、とにかく面倒。
やっぱり計算機かな。

>>19おお！有難うございます。早速使わせていただきます。
>>20
なるほど、スーザン「そうだと思った」は、
●スーザンの聞いた数字は偶数ではない。
●スーザンの聞いた数字は2+奇素数では表せない。
の２つの情報があるわけですね。
(例えばスーザンの聞いた数は2083ではありえない。)

>>19さんの上げた素数のうち、
17＞私の聞いた数をSとすると{S-2^k}の値が素数となるkが一つだけ存在する
について地道に調べた結果、候補が3つに絞れました。

2351、2383、2143です。

これ以外の数、例えば2053だと、
{4096+2053-2^k}が素数となるようなkが12以外に4があります。
4096+2053-2^4＝6133(；素数)

> 17 さん

> 僕の聞いた数はP*2^mで表せるからね。
は成り立たないと思いますけれど。

というか、我慢できなくて計算機でやってしまいました。
答えは結構小さいです(あってれば、だけど)。

えーと、和が奇数であることを聞いて一通りに定まるので、
P*2^mしか思い浮かびませんでした。
できれば>>23さんの結果を教えてください。

> 17 さん

20 に書いた通り、
2 と 9 だとするとピーターの「わかったぞ」まで
辻褄があってるはずです。
答えはもう少しもったいぶるつもりですが、
ちゃんと一意に定まってます。

和が奇数であることで2数が決まるのは
奇素数*2＾ｍ　か、2*奇素数＾ｍ　ってことになるんでしょうか？

↑　自分で書いてて間違いであることに気がつきました・・・。
2*81　の和が奇数になることは　6+27　でもあるか・・。

とりあえず自分の解答は撤回します。
ギブアップなので>>20さんの解答を待ちます。

これは計算機使わんと無理でしょう。

で、答えは 1組しかないんですか？ あげときますね。

ありゃ、答え見つかっちゃったんですか。

「他人が解いた」と聞くと俄然手が動かなくなるのは
数学屋の宿痾かもしれませんなぁ。
ってことで私も、20さんを待ちながら。

しかしこの問題、ごく日常的な言葉で
非常な複雑な条件を表現したところが見事でしたねぇ。
などと勝手にまとめに。

複数あります。

もし一意に決まるならば、デイヴィッドは小さい方を聞かずに答えがわかるんじゃ？

18をみると、原題ではオミクロンが思い浮かべたのは
「異なる」２つの数字、となっているようですが・・・

4と13という説が出てます。
ピーター「わからないな」 →2*26or4*13だからたしかにわからない
　スーザン「そうだと思った。私にもわからないわ」→和は17（奇数）であることを示唆する
　ピーター「わかったぞ」 →和が17ならわかる
　スーザン「私もわかった。でも、デイヴィッドにはわからないでし
ょうね。小さい方の数を教えればデイヴィッドにも大きい方の数を
当てることができるでしょう」 →ここがおかしいような。
小さいほうの4を教えても、デイヴィッドはわからない気がする。

デイヴィッドは我々と同じ立場なのでは？

正確に言うと、
「『小さい方の数を教えればデイヴィッドにも大きい方の数を
当てることができるでしょう』といえばデイヴィッドにも(両方)
当てることができるでしょう」ということだと思います。

たとえば 4 と 61 でも「私もわかった」まで辻褄が合うので、
結局 4＠｀ 13 は正解ではないことになります。

スーザンの 「わかった」 までを満たす組は数あれど、
それらの組の小さいほうの数として、一度だけ現れる数が
ただひとつ存在する！ってことなのかなぁ？

答え教えてage。

では私の計算結果を。
スーザンの「わかった」までを満たす組は
(4＠｀13)＠｀(4＠｀61)＠｀(16＠｀73)＠｀(16＠｀111)＠｀(67＠｀82)
したがって正解は (67＠｀82) のはずです。

...と言っても信用できないと思うのでソースを付けます。
頭の悪そうなプログラムで申し訳ない。メモリも 100 MB 位食います。
あと、行頭のスペースが消えてると思いますが
2ch の仕様なので御容赦下さい。
--------
#define MAX 5000

#define CANT_DETERMINE 0
#define MAY_DETERMINE 1


int peter_1_possible_pairs[(MAX-1)*MAX+1];
int suzan_1_on_peter_1[MAX*2];
int suzan_1_possible_pairs[MAX*2];
int peter_2_possible_pairs[(MAX-1)*MAX+1];
int suzan_2_possible_pairs[MAX*2];


void check_peter_1_possible_pairs() {
int i＠｀ j;

for (i=0; i<=(MAX-1)*MAX; i++)
peter_1_possible_pairs[i] = 0;
for (i=2; i<=MAX; i++)
for (j=i+1; j<=MAX; j++)
peter_1_possible_pairs[i*j]++;
}

void check_suzan_1_possible_pairs() {
int i＠｀ j;

for (i=0; i<MAX*2; i++)
suzan_1_on_peter_1[i] = CANT_DETERMINE;
for (i=2; i<=MAX; i++)
for (j=i+1; j<=MAX; j++)
if (peter_1_possible_pairs[i*j] == 1) {
suzan_1_on_peter_1[i+j] = MAY_DETERMINE;
} else {
suzan_1_possible_pairs[i+j]++;
}
}

void check_peter_2_possible_pairs() {
int i＠｀ j;

for (i=0; i<=(MAX-1)*MAX; i++)
peter_2_possible_pairs[i] = 0;
for (i=2; i<=MAX; i++)
for (j=i+1; j<=MAX; j++)
if (suzan_1_on_peter_1[i+j] == CANT_DETERMINE &&
suzan_1_possible_pairs[i+j] != 1)
peter_2_possible_pairs[i*j]++;
}


void check_suzan_2_possible_pairs() {
int i＠｀ j;

for (i=0; i<MAX*2; i++)
suzan_2_possible_pairs[i] = 0;
for (i=2; i<=MAX; i++) {
for (j=i+1; j<=MAX; j++)
if (suzan_1_on_peter_1[i+j] == CANT_DETERMINE &&
suzan_1_possible_pairs[i+j] != 1 &&
peter_2_possible_pairs[i*j] == 1)
suzan_2_possible_pairs[i+j]++;
}
}


main() {
int i＠｀ j＠｀ p;

check_peter_1_possible_pairs();
printf("Peter 1 ok.\n");
check_suzan_1_possible_pairs();
printf("Suzan 1 ok.\n");
check_peter_2_possible_pairs();
printf("Peter 2 ok.\n");
check_suzan_2_possible_pairs();
printf("Suzan 2 ok.\n");


for (i=2; i<=MAX; i++)
for (j=i+1; j<=MAX; j++)
if (peter_1_possible_pairs[i*j] != 1 &&
suzan_1_on_peter_1[i+j] == CANT_DETERMINE &&
suzan_1_possible_pairs[i+j] != 1 &&
peter_2_possible_pairs[i*j] == 1 &&
suzan_2_possible_pairs[i+j] == 1)
printf("%d %d\n"＠｀ i＠｀ j);

return 0;
}

すみませんがどういう数の組を探したのか教えてください。
よくわからないので。

発端の「有名日記サイト」にも解いた方が現れてますね。
http://member.nifty.ne.jp/windyfield/diary0010c.html#23
こちらも計算機でねじ伏せています。

なんと答えが違います。

40さんの方針はケレンがないので、
間違いはないだろうと思っているのですが。

＞４０
６７と８２の組み合わせだと
最初にデイヴィッドがスーザンの知っている数（和）として
想定している組み合わせは
２と４１×６７の合計の２７４９
４１と２×６７の合計の１７５
６７と２×４１の合計の１４９
の３つですよね。
そのうち、１７５は２＋１７３（プライム同士）の組み合わせが
あるので「そうだと思った」とは成らないので除外できますが、
２７４９はどうやってデイヴィッドは除外できたのでしょう？

なんか私は頭が混乱していて、、、変な質問だったら失礼。

２７４９＝８＋２７４１
８×２７４１＝２１９２８　を５０００までの
２つの数字の積で表す方法は、一通りしかない。

名無しさん＠お腹いっぱい。さん、ありがとー。
すっきりしました。

なるほど、それで「５０００まで」なのですね、、、
この問題を作った人は、どんな人なのかしら？！

18を見ろ。

スーザン｢そうだと思った。｣は､原文では｢I knew that＠｀ Peter.｣
ですから､ちょっとニュアンスが違いますね｡

結局、答えは67と82？

Ｓ={(i＠｀ j) | 0 <= i <=j < 5000}とおく。

peter_1_possible_pairs[x] = |{(i＠｀ j)∈Ｓ｜ x = i*j}|
　　：ピーターが積xを教えられた時に、ピータが考える２数の組み合わせの数

suzan_1_on_peter_1[y] = 1 if ∃(i＠｀ j)∈Ｓ s.t. y = i+j and peter_1_possible_pairs[i*j] == 1
　　　　　　　　　　　= 0 otherwise
　　：スーザンが和yを教えられた時に、スーザンが「ピータが考える２数の組み合わせの数が１になりうる」と考えるかどうか

suzan_1_possible_pairs[y] = |{(i＠｀ j)∈Ｓ｜y = i+j and peter_1_possible_pairs[i*j] != 1}|
　　：スーザンが和yを教えられてスーザンが「ピータが考える２数の組み合わせの数は１とおりではない」と考えたときの
　　　スーザンが考える組み合わせの数

peter_2_possible_pairs[x] = | {(i＠｀ j)∈Ｓ｜x = i*j and suzan_1_on_peter_1[i+j] == 0 and suzan_1_possible_pairs[i+j] != 1}|
　　：ピータが積xを教えられて「そうだと思った。私にもわからないわ」を聞いたとき、ピータが考えられる組み合わせの数

suzan_2_possible_pairs[y] = | {(i＠｀ j)∈Ｓ｜y = i+j and suzan_1_on_peter_1[i+j] == 0
　　　　　　　　　　　　　　　　　　　　　　　　and suzan_1_possible_pairs[i+j] != 1
　　　　　　　　　　　　　　　　　　　　　　　　and peter_2_possible_pairs[i*j] == 1}|
　　：スーザンが和yを教えられて「わかったぞ」を聞いたときの、スーザンが考えられる組み合わせの数

PrintPair = {(i＠｀ j)∈Ｓ | peter_1_possible_pairs[i*j] != 1
　　　　　　　　　　　　and suzan_1_on_peter_1[i+j] == 0
　　　　　　　　　　　　and　suzan_1_possible_pairs[i+j] != 1
　　　　　　　　　　　　and peter_2_possible_pairs[i*j] == 1
　　　　　　　　　　　　and suzan_2_possible_pairs[i+j] == 1 }
= {(4＠｀13)＠｀(4＠｀61)＠｀(16＠｀73)＠｀(16＠｀111)＠｀(67＠｀82)}
：スーザンの「わかった」までを満たす組

>>49
ご苦労様。
大変ありがたい。

なんでもええ