■ はじめに
この問題は、Apple などの企業が面接で出すパズル（例：誤ったラベルが貼られた箱の中身を特定する問題）をアレンジしています。
■ 問題の概要
・オリジナルの3箱問題:
- 各箱のラベルは必ず間違っている。
- 正しい配置（逆順列）は 2 通りあり、最適なら 1 回の果物取り出し（＝1ビットの情報）で全体が特定できる。
・4箱問題へ:
– 4箱の場合、全てのラベルが間違っている正しい配置はデランジメントで 9 通りになります。
– 等確率なら必要な情報量は log₂(9) ≒ 3.17 ビット。
– 最適な戦略では、運が良ければ 2 回のサンプルで解決でき、運が悪いとそれ以上必要になる可能性があります。
■ 重要な仮定
この解法は、以下の仮定に基づいています。
各箱の中の果物は十分な個数があり、ランダムな抽出によって混合箱の場合は例えば「りんご」と「ぶどう」が同じ確率（50%ずつ）で出ると仮定する。
純粋な果物が入っている箱は、その果物のみが取り出されるものとする。
■ 逆順列の計算
・包除原理（インクルージョン・エクスクルージョン）の式:
D(n) = n! × Σₖ₌₀ⁿ ((-1)ᵏ / k!)
（n 個の対象の全逆順列数を求める。）
・再帰的計算法（固定法）:
D(n) = (n – 1) × [D(n – 1) + D(n – 2)]
これにより、D(3) = 2、D(4) = 9 となります。
■ 情報量の概念
・1ビットとは:
コイントスのように、等確率な2択（表/裏、はい/いいえ）の結果から得られる情報量です。
・情報量の計算:
候補が N 通りある場合、必要な情報量は log₂(N) ビット。
例えば、4箱問題では候補数 9 に対して log₂(9) ≒ 3.17 ビットとなります。
■ まとめ
- この問題は、面接で出される実践的なパズルをアレンジしたもので、3箱問題から4箱問題に一般化したものです。
- 包除原理や再帰的計算法を用いてデランジメント（正しい配置）の数を計算し、情報量（ビット）の概念により、最短ケースでは運が良ければ 2 回のサンプルで解決可能であるが、実際の結果次第では追加の確認が必要になる、と評価できます。
#数学 #Apple