令和5年度 春期 午前 問6

✓ これが正解エ（n＋1）（1－a）÷ 2 ＋ na

解説

見つかる場合と見つからない場合を足します。

設問は、n件の表を先頭から順に見ていく線形探索で、平均比較回数を表す式を四つから選ばせています。見分けの軸は、目的の相手が見つかるときと見つからないときという二つの場合を、それぞれの確率で重み付けして両方とも足し上げているか、という一点です。目的の行が表のどこにあるかは等しく確からしいので、見つかるときの比較回数は一番目なら一回、n番目ならn回で、平らにならすと（n＋1）÷2回になります。見つからないときは最後まで全て見て初めて無いと言えるので、必ずn回かかり、ここは半分になりません。前者が起こる確率は1－a、後者はaですから、期待値は（n＋1）（1－a）÷2＋naとなります。この形は両端でも辻褄が合い、失敗の混ざる割合が増えるほど平均はnのほうへ寄っていく、という読み方もできます。

ほかの選択肢はなぜ違うのか

• ア（n＋1）na ÷ 2：（n＋1）na÷2 という式です。見つからない側の項にnを掛けすぎた形で、a＝0すなわち必ず見つかる条件を入れると値が0になり、一度も比較せずに答えが出ることになってしまいます。
• イ（n＋1）（1－a）÷ 2：（n＋1）（1－a）÷2 という式です。見つかる場合だけを書いて、見つからない場合の項を落としています。a＝1を入れると0になり、表に無いのに一度も比較しないという意味になります。
• ウ（n＋1）（1－a）÷ 2 ＋ n ÷ …：（n＋1）（1－a）÷2＋n÷2 という式です。後半の項を確率で重み付けせず、しかも半分にしています。a＝0でn＝10のとき10.5となり、実際の5.5より大きく出てしまいます。