1: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:48:09.67 ID:CMgM6wFi0.net
ある監獄には100人以上の囚人たちがいる.
彼らには監獄入りした順に1番、2番、3番、…、と番号が付けられている.
ある日看守がこう言った.

「明日、お前たちの中から私の勝手で100人選んで、その中に一方の番号が
他方の番号の倍数になっている二人組があるかどうか確認する。無ければ
お前たち全員を処刑する」

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


さて、何人目の囚人が加わったでしょうか?
転載元:http://viper.2ch.sc/test/read.cgi/news4vip/1425520089
面白いパラドックス問題や論理問題についてみんなで考えてみよう!
http://blog.livedoor.jp/nwknews/archives/4635698.html
LOC_Utah_Prisoners_c1885


6: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:49:29.88 ID:vV8ULPun0.net
わかんなーい



13: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:50:28.17 ID:4OxoR98f0.net
一方の番号と他方の番号ってなんのことなの????



15: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:50:37.12 ID:ZwX+9eTA0.net
101人目



16: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:50:39.13 ID:gliK9j7+0.net
1番がいるから慌てる必要は無いんじゃ



18: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:50:51.59 ID:CMgM6wFi0.net
お前らvipperは優秀だからもちろんすぐに答えはわかるよな?wwwww



19: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:51:12.63 ID:jQ5e3c520.net
囚人全員IQ130あるのかよ



23: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:52:48.55 ID:CMgM6wFi0.net
101は違うからな



>>19
そういうことになるなwwww



24: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:53:07.80 ID:YVJr0JPG0.net
ペアは誰が決めるの?



32: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:54:42.48 ID:CMgM6wFi0.net
>>24
ペアは決めるんじゃなくてそいいうペアが作れるかどうかってこと



29: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:54:06.20 ID:5KPAA9us0.net
199か?



40: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:56:47.88 ID:CMgM6wFi0.net
>>29
正解、さすがやな

理由まで言えたら完璧だけどどう?



43: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:58:48.71 ID:ZwX+9eTA0.net
>>40
2,198のペア 3,197のペアというようにくっつけていく
真ん中の数を1と組ませると199が残る



54: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:01:07.97 ID:CMgM6wFi0.net
>>43
ペアを確定する意図がよくわからんのだが



52: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:00:20.76 ID:o+klf0Qia.net
>>40
198までならどの100人を選んでも絶対倍数あるけど
199までの後半100人を選ぶと倍数がないから。

でも、そもそも看守の意図がわからない。
全員殺したいの?



30: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:54:23.93 ID:EaxzU8mL0.net
マジで難しい。
ランダムで組まれた100人組で、倍数コンビが一組でもいればセーフで
何人目かが入った途端突然その確率が下がるんだろ?うーん



48: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:59:20.06 ID:UWT29Fnk0.net
一方と他方ってのは
選ばれた100人の集団と選ばれなかったもうひとつのグループって事か?



50: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:59:38.74 ID:eC49uaIM0.net
198人目までは確実に生き残れる
199人目ではじめて奇数が100人になる
ってことだけど奇数100人選ばれるって結構だよな



51: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 10:59:43.40 ID:EaxzU8mL0.net
100番から199番までが選択されると誰も組めなくなるってことか?



58: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:02:19.04 ID:CMgM6wFi0.net
>>51
そうそう、そういうこと



53: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:00:50.15 ID:4OxoR98f0.net
いや、まじで一方と他方って行き成り言われて困惑(困惑)してるんだけど
まあいいや



55: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:01:55.67 ID:t3+Di13Yd.net
>>53
ほんとこれ



57: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:02:16.53 ID:App70Poq0.net
198までは、(n,2n)nは99以下の自然数というベアを考えると 99組だから、100人とれば1組はできる。
199だと100-199で不可能



61: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:03:32.17 ID:CMgM6wFi0.net
>>57
198までは云々を証明できる?



65: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:05:55.29 ID:56gMT6ni0.net
久しぶりに自分のおつむの自信が無くなった。
あてたやつ凄いね。



67: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:06:52.46 ID:+5z9Ayzq0.net
よく分からねえ
198までなら何でダイジョブなの
1-197の99個の奇数と4だとだめなの



70: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:08:00.26 ID:CMgM6wFi0.net
>>67
それだと1と4のペアがあるからセーフ



75: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:10:39.12 ID:+5z9Ayzq0.net
>>70
なるほど



71: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:08:17.94 ID:gqOe3nmTp.net
99組できて100人選ぶから、鳩ノ巣原理で100人目がどっかに入るのか
TooManyPigeons
n = 10 羽の鳩が m = 9 つの巣の中にいる。したがって少なくとも1つの巣には2羽以上の鳩がいる。
http://ja.wikipedia.org/wiki/鳩の巣原理



73: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:09:46.70 ID:CMgM6wFi0.net
>>71
うん、鳩ノ巣原理だよ
鳩ノ巣99個の区分けの仕方考えてみ



76: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:11:22.38 ID:G9G8JalK0.net
199人目
198人目まではどう100人選んでも倍数の組が出来るけど、199だと100から連番で199人目までの100人が選ばれて倍数の組が存在しない



80: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:12:23.85 ID:F2PFnXo/0.net
問題文ムズすぎ



83: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:13:36.24 ID:2jrmahjY0.net
この問題文は原文そのままなの?頭にスッと入ってこないや…



87: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:16:30.58 ID:G9G8JalK0.net
問題文は「看守が囚人の中から任意で100人選び、その100人の中に倍数になる組み合わせがあった場合」のほうが分かりやすい



88: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:17:36.50 ID:MZLF+MFS0.net
100人以上の囚人の中から適当にペア50組作ります
囚人には1から始まる固有の番号が割り当てられています
この50組の中で相方が自分の倍数のペアが1組でもいたら全員釈放すると看守が言いました
囚人たちは大喜び
「絶対に出られるじゃないか!めでたい!」
しかし次の日新たに1人囚人が増えました
囚人たちは焦りました
「これでは出られなくなるかもしれない!」
新しく入った囚人の番号は何番でしょう?



90: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:19:04.72 ID:CMgM6wFi0.net
>>88
それだと条件変わってるからな



92: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:20:11.08 ID:MZLF+MFS0.net
>>90
変わってないだろどこ?



96: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:23:54.63 ID:CMgM6wFi0.net
>>92
組を作ってから検証するんじゃなくて100人の中から一方が他方の倍数
になる2人組を作れるか検証する



91: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:20:00.65 ID:kTEA8r0s0.net
こういう数学的な考え方する問題ってだいたい問題文の日本語がちょっとおかしい



94: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:21:43.44 ID:eC49uaIM0.net
てか看守が殺せるような組み合わせを選ぶやつって設定を作っとかないと、ランダムならそんなに焦るほどの事じゃないっていう



98: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:25:28.23 ID:CMgM6wFi0.net
>>94
確かにそれは付け加えた方がわかりやすいな
ランダムなら199人でも1パターンしかないし



97: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:24:03.95 ID:MZLF+MFS0.net
ああ、そうか
「貴様らの中から100人選ぶ。自分の数字の倍数になる番号の者を見つけよ。一人でも見つけられたら釈放してやろう」
こうだな



105: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:28:03.80 ID:CMgM6wFi0.net
>>97
そうだな、釈放するとは言ってないけど



106: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:29:01.87 ID:Vf507iDt0.net
まず読むのに一瞬以上かかる が俺の回答



107: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:30:25.49 ID:whJdcIbgd.net
この問題って>>1が作ったのか?



109: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:31:48.50 ID:CMgM6wFi0.net
>>107
そうだよ、問題文わかりずらくてスマンね



111: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:32:31.27 ID:Vf507iDt0.net
>>109
わるいけどIQ180の俺から鑑みるに
読むに値しない文章だ



112: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:33:07.13 ID:vOFegjB90.net
>>1の説明を一回読むだけで正しく理解できたらニュータイプだと思う



117: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:34:39.69 ID:TZvj7F3V0.net
頭いい人ならもっと簡潔で不自然のないような文章で問題作るんだろうなぁって思いました



118: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:34:43.72 ID:V7QKZqY80.net
つまり100個目の素数ってこと?



121: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:35:09.65 ID:CMgM6wFi0.net
この問題に素数は関係ないよ



137: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:42:35.82 ID:59E2hC1g0.net
全く訳がわからんから誰かわかりやすい解説はよ



152: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:48:06.49 ID:Z+M4Tr6Q0.net
>>137
ある監獄には100人以上の囚人たちがいる。
彼らには監獄入りした順に1番、2番、3番、…、と番号が付けられている。
ある日看守がこう言った。

「明日、お前たちの中から私の勝手で100人選ぶ。その100人のうち1人でも自分の番号の倍数になってる奴がいたらお前らは死なずにすむ。」

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


さて、何人目の囚人が加わったでしょうか?

A.199人目

看守が99から199の囚人を選んだら倍数のペアが存在しなくなるから



146: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:45:39.20 ID:8Ka0mmNJ0.net
せっかく良い問題なのに文章力がもったいない



147: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:45:54.61 ID:h2sEpdzZ0.net
199だと100~199でアウトだけど
198ならどの100人選んでもセーフであることをちゃんと示してる奴が
おらんのだが



155: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:48:56.31 ID:ovaxrI6P0.net
>>147
なるほど!分かりやすい!

そういう問題だったのか



161: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 11:50:55.50 ID:l+EsJrnV0.net
おもしろかった



183: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:09:21.88 ID:K2CDiC9z0.net
2の倍数グループ
3の倍数グループ
5の倍数グ

・・・
193
195
197

これで99グループ
198までならかならず99グループ以内で収まる(1が来た場合はその時点でセーフなので1は神)
199がきたら100グループ目ができちゃうからそわそわタイム



190: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:12:09.40 ID:h2sEpdzZ0.net
>>183
おお、ベストな解答



196: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:17:30.92 ID:o4qbXRm00.net
パッと思いつく解法は2つくらいかな

198のとき偶数も約数も0ではない
偶数がn人のとき奇数は100-n人
198の中で奇数は99
選んだそのうち最初に選んだ偶数の約数になってるものは少なくともn個あるからどの偶数の約数にもならないものはたかだか99-n個
よって100-n人選ぶとき少なくとも一つは最初の偶数の約数を含まなければならない


鳩ノ巣を用いる解法
約数のうちで一番大きな奇数によってグループ分けする
このとき一番大きな奇数は197なので
グループ1からグループ197まで99個のグループが出来る
グループpに属する2数はどちらも2^kpの形をしているので同じグループから取られた2数は必ず一方が他方の倍数



198: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:19:44.68 ID:h2sEpdzZ0.net
>>196
俺が想定してたのはその下の方
最大奇数約数で部屋分けして鳩ノ巣原理で
同じ部屋の2数が2の冪乗倍になる



203: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:34:52.95 ID:8Ka0mmNJ0.net
>>196
すげえ
でもなんとなく判らない

下のやつの
「約数のうちで一番大きな奇数によってグループ分け」
「グループ1からグループ197まで99個のグループが出来る」
がよくわからん

良かったらkwsk



205: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:43:30.88 ID:o4qbXRm00.net
>>203
まず奇数は全部違うグループとなります(99個)
次に偶数のときだけど
たとえば10は一番大きな奇約数は5だから5と同じグループに入れます
16は最大の奇約数は1なので1と同じグループに入れます
こんな感じで偶数をグループ分けしていってやると
たとえば3と同じグループのメンバーを見てやると全部より大きい奇数を約数に持たないので全部3×2^nの形であることが分かるけど
このとき3グループの3×2^mと3×2^nは倍数の関係になっています
説明が上手くなくて申し訳ない
分かりにくいとこがあれば言ってくれ



206: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:44:43.30 ID:h2sEpdzZ0.net
>>203
>>196ではないけど

1,2,4,8,16,32,64,128
3,6,12,24,48,96,192
5,10,20,40,80,160
7,14,28,56,112


193
195
197

って感じで1~198までの数字を99グループに分けると100個選んでも
必ず同じグループに属する2数が存在して、その2数は一方が他方の
2の累乗倍になってるからセーフ



209: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 12:52:14.78 ID:8Ka0mmNJ0.net
>>205
>>206
まだ判ってないけどありがとう!

理解するのに時間掛かりそうだから先にお礼だけ言っておくw
なんとなく判ってきました



216: 以下、\(^o^)/でVIPがお送りします 2015/03/05(木) 13:25:32.80 ID:TgYUJIsg0.net
良スレですな



ゲーセンで出会った不思議な子の話

集団で狂う現象って何かある?

【不思議な】電車に乗って変な場所に行った【体験】

俺が異世界に行った話をする

お笑い芸人の怖いコント、漫才貼る

江戸時代に出版されたアメリカ建国の歴史の内容が超展開すぐるwww

森脇健児、ヒロミ、清水圭ってなんで干されたんだろう

人類史上最大のミステリーって何?

嫌われる勇気―――自己啓発の源流「アドラー」の教え
岸見 一郎 古賀 史健
ダイヤモンド社
売り上げランキング: 2