入場料金集金問題の解答例を示します。
問題の解
5000円札をもっている人を○、10000円札をもっている人を◎で表す。
図1で、9から始めると失敗するが、図2で、8から始めると成功する。円形の輪の位置を指定するために、1から10を使う。
nに関する数学的帰納法で証明する。
(A)nの値が 1 のときは、まず、5000円札をもつ人から5000円札を受取る。
つぎに10000円札をもつ人から10000円札を受取り、5000円札を渡せばよい。
したがって、命題は正しい。
(B)nの値がkのとき、命題が正しいと仮定する。
つぎに、nの値がk+1のときも命題が正しいことを示す。
n=k+1のとき、5000円札をもつ人の隣り(ただし、時計回り)に10000円札をもつ人の組を見つける。そういう組は必ずある。
この2人を除くと 2k 人になるので、仮定から釣り銭に不足することなく集金ができる。
最初に見つけた2人から集金する場合は、5000円札をもつ人から5000円札を受取り、つぎに10000円札をもつ人から10000円札を受取り5000円札を渡せばよい。
すなわち、nの値がk+1のときも命題は正しい。
(A),(B)より、命題が証明された。
(注意)数学的帰納法では実施できることを示しているだけで、具体的にどの人
から集金していくかは示していない。