毒入りワイン
毒入りワイン
1000本のワインがあり、1本に毒が入ってます。
この毒は少しでも飲むと15時間から20時間後に死にます。
24時間以内にどのワインが毒入りかを特定するには最低何人の奴隷が必要でしょうか?
1000本のワインがあり、1本に毒が入ってます。
この毒は少しでも飲むと15時間から20時間後に死にます。
24時間以内にどのワインが毒入りかを特定するには最低何人の奴隷が必要でしょうか?
まず、開始直後に飲むと効果がでるのが15時間から20時間で、開始から4時間後に飲むと効果が出るのが開始から19時間から24時間後なので時間差による特定は不可能である。
1000本のワインに番号を振り2進数で表す。
ワインは1000本あるので、10桁の2進数で表される。
1人目の奴隷は1桁目が1のワインを飲む。
2人目の奴隷は2桁目が1のワインを飲む。
……
10人目の奴隷は10桁目が1のワインを飲む。
20時間後には毒が効いてきて死ぬので、死んだ奴隷を1、死んでない奴隷を0として、元の順番通りに10桁の2進数を作る。
この2進数から元のワインに振った番号を特定出来るのでそのワインが毒入りのワインである。
こうすると、10人で\(2^{10}=1024\)本までは特定ができ9人では\(2^{9}=512\)本までしか特定ができないので、10人が必要である。
従って\(m\)本のワインから毒入りワインを特定するのは\(n=\frac{\log m}{\log2}=\log_{2}m\)となり、端数を切り上げて\(\left\lceil \log_{2}m\right\rceil \)人必要となる。
1000本のワインに番号を振り2進数で表す。
ワインは1000本あるので、10桁の2進数で表される。
1人目の奴隷は1桁目が1のワインを飲む。
2人目の奴隷は2桁目が1のワインを飲む。
……
10人目の奴隷は10桁目が1のワインを飲む。
20時間後には毒が効いてきて死ぬので、死んだ奴隷を1、死んでない奴隷を0として、元の順番通りに10桁の2進数を作る。
この2進数から元のワインに振った番号を特定出来るのでそのワインが毒入りのワインである。
こうすると、10人で\(2^{10}=1024\)本までは特定ができ9人では\(2^{9}=512\)本までしか特定ができないので、10人が必要である。
-
一般的に\(n\in\mathbb{N}_{0}\)人いれば\(2^{n}\)個のワインから毒入りワインを特定できる。従って\(m\)本のワインから毒入りワインを特定するのは\(n=\frac{\log m}{\log2}=\log_{2}m\)となり、端数を切り上げて\(\left\lceil \log_{2}m\right\rceil \)人必要となる。
ページ情報
タイトル | 毒入りワイン |
URL | https://www.nomuramath.com/wz77mf9g/ |
SNSボタン |
秘書問題(最良選択問題)
1位の応募者を採用することを最優先する場合はどのような戦略をとれば良いか。
10個の誕生日の候補
会話を元に誕生日を特定しましょう。
3人で100m走
100m走で10m差が2回ある2人が走るとどうなる?
連続で2段上れないときには階段の上り方は何通りあるか?
1回で1段または2段上れるが連続で2段上ることができないとき何通りの上り方があるか。