問題
以下の問いに答えよ．
(1) 碁石（ごいし）には白と黒の2種類の石がある．ところがA君は『任意の碁石の集合は1種類の石しか含まない』ことを以下のように証明しようとした．A君の数学的帰納法の適用方法が誤っている理由を説明せよ．
〔A君の証明〕
どの碁石の集合も1種類の石しか含まないことを証明したい．そこで集合に含まれる碁石の数に関する数学的帰納法によってこのことを証明する．
(I) の場合を考える．1個の碁石からなるどの碁石の集合についても，に含まれる碁石は明らかに1種類である．
(II) の場合に成立することを仮定する．すなわち，個の碁石を含むどの碁石の集合についても，に含まれる碁石は1種類であることを仮定する．そして，の場合に成立することを示す．すなわち，個の碁石を含む碁石の集合を任意に選んだとき，に含まれる碁石は1種類であることを証明する．
から勝手に2つの碁石とをとる．残りの集合をとする．にを加えた集合は個の碁石を含むので，帰納法の仮定から，この集合に含まれる碁石は1種類である．したがって，に含まれる碁石ととは同じ種類である．一方，にを加えた集合も個の碁石を含むから，同様にして，に含まれる碁石ととは同じ種類である．ゆえにとは同じ種類である．すなわち，は1種類の碁石からなる．
(2) 20円以上の任意の値段分の切手は5円切手と6円切手の組合わせとして買えることを示せ．
方針
(1)は帰納法の帰納段階がすべての で成立していないことを指摘する。特に から 個の場合へ進むとき、共通部分 が空になり、 と を結びつける石が存在しない。(2)は20円から24円までを具体的に作り、そこから5円切手を1枚足すことで5ずつ上の金額を作れることを示す。これは5つの初期値をもつ帰納法である。
解答
(1)
A君の証明では、 個の集合 から2つの碁石 を取り除き、残りを としている。そして がどちらも1種類の石しか含まないことから、 と が同じ種類だと結論している。
この議論が成り立つには、 の中に少なくとも1つ碁石があり、その石を介して と が同じ種類だと言える必要がある。しかし、 から の場合を示す段階では、 は2個の碁石からなる集合であり、そこから を取り除くと である。空集合には や と比べるための碁石がない。
したがって「 に含まれる碁石と は同じ種類である」「 に含まれる碁石と は同じ種類である」という部分が、 が空の場合には意味をもたない。よって帰納法の から への段階が証明されておらず、数学的帰納法の適用が誤っている。
(2)
まず20円から24円までを5円切手と6円切手で作る。 であり、 である。したがって20円、21円、22円、23円、24円はすべて作れる。
次に、ある金額 が5円切手と6円切手の組合せで作れるなら、そこに5円切手を1枚加えることで 円も作れる。したがって、20円が作れるので25円、30円、35円、 が作れる。同様に21円から26円、31円、 が作れ、22円、23円、24円からもそれぞれ5ずつ大きい金額がすべて作れる。
20以上の任意の整数は、20、21、22、23、24のいずれかに5の倍数を加えた形に書ける。よって20円以上の任意の値段分の切手は、5円切手と6円切手の組合せとして買える。