引用元:http://tomcat.2ch.sc/test/read.cgi/livejupiter/1475863027
l_131

1:風吹けば名無し@\(^o^)/ 2016/10/08(土) 02:57:07.45 ID:aqdKZBQua.net
ある監獄には100人以上の囚人たちがいる.
彼らには監獄入りした順に1番、2番、3番、…、と番号が付けられている.
ある日看守がこう言った.

「明日、お前たちの中から私の勝手で100人選ぶ。その中で、一方の番号が他方の番号の倍数になっている二人組が1組でも作れるかお前たちで試してみろ。1組でもそうしたペアを作れなければお前たち全員を処刑する。おれはお前達を処刑するため全力を尽くす」

意外なことに、これを聞いた囚人たちは全く動揺しなかった.
しかしその晩、新たに一人の囚人が監獄入りしたことで、
囚人たちはたちまち大パニックに陥ったという.


さて、何人目の囚人が加わったでしょうか?
4:風吹けば名無し@\(^o^)/ 2016/10/08(土) 02:58:35.63 ID:D966J0m7a.net
100番目の素数
9:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:00:00.80 ID:D5OH6oZL0.net
>>4
101番目やないか?
100だと1も含まれるやろ
12:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:00:35.79 ID:C1qqZr6u0.net
>>9
素数の組百人が選ばれたらアウトってことやないの?
7:風吹けば名無し@\(^o^)/ 2016/10/08(土) 02:59:17.72 ID:HCNpe/2ua.net
103
8:風吹けば名無し@\(^o^)/ 2016/10/08(土) 02:59:46.92 ID:mZrMByocp.net
なんなんや
10:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:00:10.59 ID:mZrMByocp.net
ああ、198ぽいなぁ
13:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:00:51.77 ID:aqdKZBQua.net
>>10
これが正解
素数かんけいないやで
22:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:03:21.56 ID:AyTMJNbL0.net
>>13
101とか103とか109とかが含まれてたら成立しなくね?
26:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:04:32.42 ID:aqdKZBQua.net
>>22
ペアは一組でもあればええんやから、101番くんはダメでもええやん
33:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:06:59.94 ID:AyTMJNbL0.net
>>26
ああ、一組でもあればええっちゅうことか
15:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:01:41.65 ID:aqdKZBQua.net
199人以上なら、100-199の100人選ばれたらペア作れず死亡や
16:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:01:54.61 ID:D5OH6oZL0.net
ああそういうことか
18:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:02:15.93 ID:YB/IbvdE0.net
同時に何十万人も入ってくる→みんなパニック
当たり前だよなぁ?
24:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:03:54.44 ID:aqdKZBQua.net
198人ならどの100人選ばれても大丈夫っていうのは言いきれるんやろか…不安になってきたわ
31:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:05:58.47 ID:AyTMJNbL0.net
>>24
素数の101がその100人の中に含まれていたらアウトやろ?
最低人数が198人だったら
32:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:06:57.47 ID:aqdKZBQua.net
>>31
101はペアできなくてもええんやぞ
100人のうちどこかに倍数関係ペアおればええんや
50番と100番とか
25:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:04:14.63 ID:HcC0COSG0.net
99*2+1
27:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:05:32.73 ID:TmycB2Nea.net
どういうことや
99、100、…、198
で選ばれても無理じゃね?
28:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:05:37.19 ID:mZrMByocp.net
198人ならどうも大丈夫そうやけど
証明試してみるわ
30:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:05:55.17 ID:HcC0COSG0.net
198はおかしいやろ、1ペア出来るやんけ
35:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:07:17.78 ID:aqdKZBQua.net
>>30
正確には199人目、やな
すまん
39:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:08:27.82 ID:D5OH6oZL0.net
100-199の100人ってことやな
47:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:10:44.19 ID:4/pZH3Xb0.net
看守は全力尽くすんだからペア作らんよう選ぶ
198までならどう選んでもペア出来ちゃうけど
199になれば100~199を看守が選ぶことができる

問題の書き方が悪いわ
お前たちで試してみろって、囚人が出来ることなんてまったくないやん
54:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:14:36.92 ID:aqdKZBQua.net
>>47
ペアは看守が指定するんじゃないかって勘違いされかねないから、あえて囚人が自由にできるってことにしたんや
たしかに囚人は看守の選び方次第で運命決まるのは変わらない
50:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:11:44.36 ID:cFM8GnkJ0.net
問題がゴミ
51:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:11:52.47 ID:mZrMByocp.net
199人囚人がいる時100-199を選ばれると倍数ペアがおらず死亡

198人いる時はどう選ばれても絶対大丈夫なことを示す。
198人の中には偶数番号99人奇数番号99人
偶数番号の囚人がn人選ばれるとする(1≦n≦99)
この時奇数番号囚人は100-n人選ばれる

さて、選ばれた偶数番号n個それぞれについて、割り切れなくなるまで繰り返し2で割ってみる。するとn個の奇数が生じる
ここで場合分け
①このn個の奇数がすべて異なる場合
奇数番号は、このn個の奇数以外から選ばねばならない(選ぶとその奇数に対応する偶数と倍数ペアになってしまう)
すると選べる奇数番号は99-n個
奇数番号は100-nえらばねばならぬからこれは矛盾、故に①では必ず倍数ペアあり
②n個の奇数に、同じものがある場合
2で割り続けた結果が一致する二つの偶数は、割り続けた結果の奇数をpとするとp×2^mとp×2^nと書ける
この二つの偶数は必ず2の階乗倍の関係になるため、これらの偶数が倍数ペアとなる、故に②では倍数ペアあり

よって198人では常に倍数ペアは存在
はい終わり
58:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:15:26.85 ID:aqdKZBQua.net
>>51
証明完璧やん
東大生かなにか?
56:風吹けば名無し@\(^o^)/ 2016/10/08(土) 03:15:16.71 ID:AyTMJNbL0.net
久々に頭使った気がするわ