Mathematics
Examination
Test
Archives
【3】 のラベルの付いた個のボールがある.このボール個の質量はであるが,個のうち個だけ,質量がの不良品であることが分かっている.質量が測定できるはかりを用いて,この不良品のボールを見つけるために,以下のつの手法を考える.ただし,は自然数)とする.
手法1
(1) とする.
(2) ボールをはかりに載せる.
(3) の質量がならば,をだけ増加させて,(2),(3)の操作を繰り返す.
の質量がならば,を不良品と特定して終了する.
手法2
(1) ボールを半分ずつのつの集合に分ける.
(2) 集合のボールすべてを一度にはかりに載せる.
(3) (2)で計測された質量がの倍数であれば,の中に不良品があり,そうでなければ不良品はの中にある.
このとき,不良品の含まれている方の集合をとし,に対して,以下の操作を行う.
(a) に含まれるボールが個であれば,それを不良品と特定して終了する.
(b) に含まれるボールが複数あれば,に対して(1)と同様につの集合に分けて,(2),(3)の操作を繰り返す.
以下の問いに答えよ.
(ⅰ) 手法1を実行したとき,不良品が最も早く見つかる場合と最も遅く見つかる場合それぞれの,(3)の実行回数を答えよ.
(ⅱ) 手法2で,(3)を回実行した後に不良品の可能性のあるボールの個数をとの式で表せ.
(ⅲ) それぞれの手法で,不良品が最も遅く見つかる場合を考える.その際の,手法2における(3)の繰り返し回数をの式で表し,どちらの手法がより少ない繰り返し回数で不良品を見つけられるかを答えよ.