数学@ふたば
[ホーム]

[掲示板に戻る]
レス送信モード
おなまえ
E-mail
題  名
コメント
添付File []
削除キー(記事の削除用。英数字で8文字以内)

画像ファイル名:1595143998776.jpg-(72553 B)
72553 B無題Name名無し20/07/19(日)16:33:18No.114328+ 21年2月頃消えます
1列に並んだ5つの穴のどれかにウサギが1匹隠れています。
あなたは毎朝、どれか1つだけ穴を覗いてウサギがいるか確認できます。
ウサギは毎晩、1つ隣の穴に移動します。
ウサギを確実に見つけるには何日かかるでしょうか。
削除された記事が3件あります.見る
1無題Name名無し 20/07/19(日)18:21:03No.114329+
「あちらの穴2〜4に『あなたの中にウサギはいますか』と質問したら何と答えますか、
と質問したら良い
2無題Name名無し 20/07/19(日)18:39:32No.114330+
書き込みをした人によって削除されました
3無題Name名無し 20/07/19(日)18:54:56No.114331+
覗いて見える程度の浅い所にはいないので
永遠に無理です
4無題Name名無し 20/07/19(日)18:56:23No.114332+
毎日端から穴を確認後、居なかったら埋めていく
と言うのを繰り返したら最長でも4日でウサギの居る穴を特定できる
5無題Name名無し 20/07/19(日)20:23:30No.114333+
隣がどっちか決まってなければいつまでたっても無理では
6無題Name名無し 20/07/19(日)20:51:32No.114334+
その条件だけだと永遠に無理だ。
多分引用する際に何か重要な条件を抜かしてしまったんじゃないのか?
7無題Name名無し 20/07/19(日)21:43:25No.114335+
7日やね
右から二つ目を三回
左から二つ目を三回した後に
右から二つ目を見るまでに必ずいる
8無題Name名無し 20/07/19(日)22:03:31No.114336+
>>No.114335
と思ったら間違ってた
9無題Name名無し 20/07/19(日)23:53:16No.114337+
6日
端から穴1〜穴5と呼ぶことにして
穴2,3,4,2,3,4の順に覗けば必ずどこかでは見つかる
兎がいるか不明な穴を?,兎がいない穴をXとすると
発見までの流れは最悪のケースで次の通り
?????→2覗→?X???→夜→
X????→3覗→X?X??→夜→
?X???→4覗→?X?X?→夜→
X?X?X→2覗→XXX?X→夜→
XX?X?→3覗→XXXX?→夜→
XXX?X→4覗→XXXOX
10無題Name名無し 20/07/20(月)04:35:30No.114338+
>穴2,3,4,2,3,4の順に覗けば必ずどこかでは見つかる
どうやってそのことに気づいたの。
11無題Name名無し 20/07/20(月)06:37:05No.114339+
>No.114338
兎が奇数番目の穴に居るならその翌日は偶数番目の穴に,偶数番目の穴に居るならその翌日奇数番目の穴に居る
という性質を利用し,初日に兎が偶数番目の穴に居た場合の可能性を先に潰そうと思った(最初の3日間)
それで見つからなければ初日奇数番目に居て,4日目には偶数番目に居ることになるので最初の3日間と同じ手順を踏むことで発見できるという結論に至った
12無題Name名無し 20/07/21(火)00:23:18No.114341+
>No.114337
表記法がイカス
13無題Name名無し 20/07/21(火)05:26:42No.114342+
兎の位置の偶奇に注目する以外も含めた全ての確認方法のうちの最短日数は?
14無題Name名無し 20/07/21(火)07:42:14No.114343+
一般化した数列に興味ある
An=n個の穴で兎が毎晩隣接移動する際に朝一つの穴を確認して必ず見つけることができる最短日数

A1=1
A2=2
A3=2
A4=4
A5=6
An=?
15無題Name名無し 20/07/21(火)08:31:56No.114344+
>No.114343
偶奇法が最短だとすればn≧3においてAn=2(n-2)
穴2〜穴(n-1)の順で確認した後に穴(n-1)〜穴2の順で確認すれば良い
16無題Name名無し 20/07/21(火)23:57:58No.114345+
一般化ったって偶奇法は6個以上の穴では無限に終わらない危険性を潰せないんじゃ…
穴が多いために見回るうちに遇→奇→遇とか奇→遇→奇とかいった移動を許してしまう
17無題Name名無し 20/07/22(水)04:04:04No.114347+
    1595358244860.gif-(174170 B)
174170 B
図はn=8の場合
兎が居る可能性がある穴に兎を配置し、兎の初期位置が(左から数えて)奇数番目なら赤、偶数番目なら青に着色している
青兎について、居うる穴は常に一つ跳びになっているので順番に確認していけばいずれ追い詰めて捕らえることができる
これは赤兎についても同様
従って兎が最初どこにいて、どのように動いたとしても
>No.114344
の方法で必ず捕らえることができる
18無題Name名無し 20/07/23(木)01:12:30No.114349+
書き込みをした人によって削除されました
19無題Name名無し 20/07/23(木)15:13:28No.114350+
ご丁寧にgifまであってとても分かりやすい
20無題Name名無し 20/07/29(水)00:37:58No.114361+
いま疲れていて精読する気が起きないが
面白い問題&解答だね
21無題Name名無し 20/07/29(水)07:02:12No.114363+
捉えられることはわかったけど
そのアルゴリズムが最短日数であることは言わなくていいの?
というよりも証明できるのか?
22無題Name名無し 20/07/30(木)02:19:37No.114365+
端を除く穴を移動しない
確率1/4✖日数?
23無題Name名無し 20/07/30(木)18:42:53No.114367+
書き込みをした人によって削除されました
24無題Name名無し 20/07/30(木)18:44:11No.114368+
穴の数に対する一般化の証明としては
多分穴n個の問題を穴n-1個の問題+追加手順、に帰着できる系の操作で良いと思うが知らん

やったら多分No.114344の手順で良いという結論になると思う
そしたら日数の手ごろな上界が得られたわけなので
具体的なnについては虱潰しでより短い日数が可能か否かの判定は可能
25無題Name名無し 20/07/31(金)15:45:53No.114372+
>確実に見つけるには
うさぎが右方向左方向決まって無い限り無いよな

確認を移動する程に確率は下がらね?

- GazouBBS + futaba-