問題82：IOM 2019

問題一覧へ戻る

#82

組み合わせ

★★☆☆☆

IOM 2019 問4

ある教授が $100$ 人の生徒に次のような試験を受けさせ, それぞれの生徒に合格または不合格のいずれかの結果を与える.

教授は生徒を $1$ 人ずつ順番に呼び出し, それぞれの生徒に $100$ 人のうち合格者が何人出ると思うか尋ねる.
生徒が答えたら, 教授はすぐにその生徒の合否を決め, すべての生徒に伝える.

ただし試験を通じて生徒は互いに意思疎通できないものとする.

すべての生徒の合否が決まった状態で, 正しい人数を回答していたにもかかわらず不合格となった生徒が存在したとき, 教授はクビとなり, すべての生徒の結果は合格に変わる. そうでなければ合否の変更は起こらない.

生徒らの目標は $100$ 人全員で合格することである. 彼らは目標を達成できるか？

解いてみた

平山： $n = 1$ のときは $0$ って言えばいいんかな
平石：合否は伝えてもらえるんか
平山：それ無かったら無理でしょw
平石：無理かー
平山： $n = 2$ はまず $1$ って言って、合格なら $1$ 、不合格なら $0$ か
平山：不合格って言われたら $1$ 減らせばよくね？
平石：あーあってるわ、 $99$ から始めればいいんやな
平山：最後に不合格って言われた人が正解になって幸せ
宿田：合格確定！

解説・感想

工事中

解答

生徒らが次の戦略によって目標を達成できることを示す.

最初の生徒は $99$ 人と答える.
その後の生徒は, 直前の生徒が合格ならば同じ人数を, 不合格ならば $1$ 減らした人数を答える.

不合格の生徒が存在した場合のみ考えればよい. このとき不合格者が $a$ 人だとすると, 不合格者のうち最後に呼び出された生徒は $100 - a$ 人と答えており, これは正しい人数である. よって示された.