1: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:53:17.152 ID:9D6Jri6N0.net
あなたは 100 階建のビルにいます
同じ種類のビー玉を 2 つ持っています
ビルから落とすことでこのビー玉の強度を調べます
どのような戦略を取れば落とす回数の最大値を最小化できるか
2: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:54:36.136 id:XSP/4Wzpa.net
危険なので強度を測る機械にいれる
0にできる
3: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:54:39.256 id:fe0gT9du0.net
ビルから降りてしかるべき施設に持ってく
4: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:54:41.147 id:VwxNH2sR0.net
ヤベーわかんね
5: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:55:31.489 ID:/27MUaFO0.net
まっすぐ縦に並べて落とす
8: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:56:13.462 id:JhzL0Bh30.net
強度ってのは何階から落としたら割れるかってことか
9: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:56:26.411 id:DUc4WFDC0.net
単純に考えると最大５０回か
14: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:57:30.772 id:mzc1T9yw0.net
>>9
2個なんだからできるわけ無いやろ
23: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:00:12.257 id:DUc4WFDC0.net
>>14
一個目を50階から落とす→割れる→もう一個が割れないように1階から順に落としてく
ビー玉の強度が49階からの落下まで耐えられるものだったら最大50階の試行で強度を示せるんじゃね？ってこと
10: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:56:34.057 id:alPaOtl/0.net
強度っていうのはn階から落として壊れたら
強度ｎみたいな認識でいいんだよな？
それにしたって弾2個だけか…
11: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:57:24.906 id:gDG50PC/r.net
真ん中から順に試す
真ん中の階で割れたらさらにその下から真ん中で試すのを繰り返す
18: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:58:22.281 ID:6pAxZTBjd.net
二分法を用いる
19: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:58:49.108 ID:p0/dq8FB0.net
ていうか最大値2なんじゃね？
割れなかったら利用できるってことなん？
20: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:58:53.241 ID:9D6Jri6N0.net
強度は『1 階からでも壊れる』から『100 階からでも壊れない』まで 101 通りあるわけだよ
例えば 1 階から順に落としていけば最初に壊れたところで強度が特定できる
この場合は最大 100 階かかるわけだよ
ただ 2 つあるんだから 1 個目のビー玉で特定しなくてもいい
例えば最初は 50 階で落として，壊れたら残りのビー玉で 1 階から試せば
最大 50 回の試行回数で済むでしょ
もっと頭のいい方法はないだろうか
24: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:00:40.248 ID:W/6b3tLQd.net
>>20
とりあえず考え方はこれだと思う
他に効率いいやりかたあるかな
21: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:59:03.040 id:gDG50PC/r.net
これなら最大で6回やれば終わる
27: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:02:06.737 ID:W/6b3tLQd.net
>>21
それだと特定する前に二個目が割れて続けられなくなる可能性がある
22: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 15:59:08.109 id:alPaOtl/0.net
普通に考えるなら
50階から落とす→壊れない
じゃあ75階から落とす→壊れない
じゃあ87階から落とす…
っていうバイナリサーチだけど、球が2個だけってのが引っかかるんだぜ
25: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:01:18.712 id:gDG50PC/r.net
>>22
一度割れたらもう使えないってことかも
38: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:04:52.916 id:alPaOtl/0.net
>>22
50階から落とす→壊れない
じゃあ75階から落とす→壊れない
じゃあ87階から落とす→壊れた
そこで76階から順番に落としていく。
それで最初に壊れた地点＝強度
こうか
33: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:04:05.601 ID:p0/dq8FB0.net
一つは最大値の確認用
一つは細かい計測用なかんじか
１０階区切りで試すのは？
１０階ＯＫ→２０階ＯＵＴの場合11回ってな具合に
43: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:07:53.313 id:gDG50PC/r.net
>>33
最大で19回だから今のところこの方法が1番か
34: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:04:07.074 id:LuQtAbFf0.net
2階から落とす→4階から落とすと二階ずつ上げてって割れたら一階下に行ってもう一個落とせば確認できる
35: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:04:07.842 id:mpyDkqSBH.net
下から順に1+3n階で落とす
1と4、7と10みたいな感じ
36: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:04:08.459 ID:6VOSf+u10.net
そういうことか
じゃあ50階から始めるしかないんじゃないの
でも常識的に考えたら30階でもビー玉は割れるけどね
46: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:08:37.463 ID:4SmRJQZv0.net
一個目を10階毎だと最大19回
11階毎だと最大18回？
52: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:11:38.614 ID:6pAxZTBjd.net
>>46
それでも19回だよ
59: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:13:58.268 ID:4SmRJQZv0.net
>>52
あぁそうか99階で割れたのをカウントし忘れてたわ
47: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:09:06.682 id:XW60Jhgwd.net
分かったわ
14から27,39,50,60…だね
最大14回
58: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:13:11.155 id:XW60Jhgwd.net
>>47に付け加えると、割れたタイミングで割れなかった最大階のひとつ上から試せばいい
1投目は14から13,12と加算させていく数列
70: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:20:46.699 id:gDG50PC/r.net
>>58
すごい
これが最小回数のアルゴリズムなの証明したい
62: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:16:49.564 id:alPaOtl/0.net
>>58
凄いな、ぴったり100になるのか…
69: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:19:52.174 id:XW60Jhgwd.net
>>62
いや、この方法だと105階まで14投以内で終わらせられるはず
53: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:11:42.574 id:zyHbwxMWd.net
100をn個に区切る
①1個目が壊れるまで下から落とし続けて最大100/n回
②その間に存在するn階分を下から順に調べて最大n回
①②より、(100/n)+n の最小値を求めればいいのかな？
61: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:16:31.563 ID:/27MUaFO0.net
14,27,39,50,60,69,77,84,90,95,99,100
65: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:19:24.049 ID:6pAxZTBjd.net
>>61
これか すげーな
64: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:18:55.670 ID:4SmRJQZv0.net
やっぱお前ら凄いわ
68: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:19:45.728 ID:X+yAF6Fx0.net
文系でもこの程度は解けるわ
図に乗りすぎだろ
74: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:21:34.569 ID:9D6Jri6N0.net
今のところ
たかだか 14 回で分かるというのが
ベストな戦略です
もっといいものはないでしょうか
75: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:21:44.324 ID:+QHaC240d.net
ダメージの蓄積は考えないの？
80: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:24:42.705 id:V4qX3Rp00.net
俺も>>75が気になったが、そもそもビー玉の磨耗は考えないってことか
76: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:23:02.751 id:ueo/W51va.net
説明できる自信ないけど
15階→28階→40階→51階→…と順に調べる
どこかで割れたら、割れなかった階に戻って1階ずつ調べる
いきなり割れた場合が最悪で、14回かかる
85: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:27:13.880 id:ueo/W51va.net
ところで「1階から落とす」はありえないと考えて
スタート地点を2階にしたから15階スタートになったんたけど
どんなんだろう幸い結果に変わりはない
90: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:30:32.534 ID:4SmRJQZv0.net
>>85
落とすビジョンが
人がまっすぐ前に突き出した手から放すイメージだったから
そういえば一階から落とす事に疑問持たなかったわ
87: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:29:22.073 id:GFweQoBM0.net
１００階から落としても割れなかったらもう無理じゃね？
92: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:37:54.809 id:JhzL0Bh30.net
1個目を落とす最初の階数が落とす回数の最大値になるのかな
てことは最初に落とす階を14Fより下のどこかにして全体の試行回数が14回を下回ることがあるかどうかを考えればいいな
93: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:40:44.296 id:Kk6YLtpJ0.net
ダメージは蓄積しないの？
1回目なら耐えれる高さも何度も実験してると割れるようになるんじゃね？
94: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 16:41:40.865 ID:6pAxZTBjd.net
パズルなんだから蓄積はしないだろう
100: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 17:28:13.527 ID:sc/rZQGc0.net
一階で割れたらもっと低いところから落とさないと
103: 以下、＼(^o^)／でVIPがお送りします 2015/05/14(木) 18:08:56.757 ID:W/6b3tLQd.net
1Fからちょうど2Fの高さに向けて投げ上げる
一度も「ビルから落と」さずに・・
俺の屁理屈レベルではこれが限度
105: 1 2015/05/14(木) 18:17:53.602 ID:9D6Jri6N0.net
もうでてるけど正解は 14 回ね
方法は 1 個目のビー玉を
14 → 27 → 39 → 50 → 60 → 69 → 77 → 84 → 90 → 95 → 99 → 100
の順で落としていって，途中で割れたら
その前に割れなかった階の 1 つ上から試す
これより良い方法がない理由としては
もし 13 回以下で確実に分かる方法があるとすると
1 回目は 13 階以下から始まるはずで，壊れなかった場合の 2 回目は 13 + 12 = 25 階以下でなければならない
同様に，壊れずにずっと行ってしまった場合の 12 回目は 90 階以下でなければならない
残り 1 回で 91-100 までを調べることはできないでしょう
参考文献
