九州大学 2000年度 後期日程 第2次学力試験理系（後期）数学 第4問

(1)
A君の証明では、$k+1$ 個の集合 $T$ から2つの碁石 $a,b$ を取り除き、残りを $T^{\mathrm{\prime }}$ としている。そして $T^{\mathrm{\prime }}\cup \{a\},T^{\mathrm{\prime }}\cup \{b\}$ がどちらも1種類の石しか含まないことから、$a$ と $b$ が同じ種類だと結論している。

この議論が成り立つには、$T^{\mathrm{\prime }}$ の中に少なくとも1つ碁石があり、その石を介して $a$ と $b$ が同じ種類だと言える必要がある。しかし、$k=1$ から $k+1=2$ の場合を示す段階では、$T$ は2個の碁石からなる集合であり、そこから $a,b$ を取り除くと $T^{\mathrm{\prime }}=\mathrm{\varnothing }$ である。空集合には $a$ や $b$ と比べるための碁石がない。

したがって「$T^{\mathrm{\prime }}$ に含まれる碁石と $a$ は同じ種類である」「$T^{\mathrm{\prime }}$ に含まれる碁石と $b$ は同じ種類である」という部分が、$T^{\mathrm{\prime }}$ が空の場合には意味をもたない。よって帰納法の $n=1$ から $n=2$ への段階が証明されておらず、数学的帰納法の適用が誤っている。

(2)
まず20円から24円までを5円切手と6円切手で作る。 $20=4\cdot 5$ であり、$$21=3\cdot 5+6,22=2\cdot 5+2\cdot 6,$$ $$23=5+3\cdot 6,24=4\cdot 6$$ である。したがって20円、21円、22円、23円、24円はすべて作れる。

次に、ある金額 $N$ が5円切手と6円切手の組合せで作れるなら、そこに5円切手を1枚加えることで $N+5$ 円も作れる。したがって、20円が作れるので25円、30円、35円、$\dots$ が作れる。同様に21円から26円、31円、$\dots$ が作れ、22円、23円、24円からもそれぞれ5ずつ大きい金額がすべて作れる。

20以上の任意の整数は、20、21、22、23、24のいずれかに5の倍数を加えた形に書ける。よって20円以上の任意の値段分の切手は、5円切手と6円切手の組合せとして買える。

(1) は帰納段階で2集合の共通部分が空になる最初の箇所を特定する。
(2)は20から24までの連続5整数を基礎にした強い帰納法で示す。

(1)
$k=1$ から $k+1=2$ へ進む段階では、
$T$ から $a,b$ を除いた $T^{\mathrm{\prime }}$ は空集合である。
$T^{\mathrm{\prime }}\cup \{a\}$ と $T^{\mathrm{\prime }}\cup \{b\}$ がそれぞれ1種類でも、
両集合に共通の碁石がないため、$a,b$ が同種とは結論できない。
従って帰納段階が最初の一歩で成立していない。

(2) $$20=4\cdot 5,21=3\cdot 5+6,22=2\cdot 5+2\cdot 6,$$$$23=5+3\cdot 6,24=4\cdot 6.$$従って20から24までは作れる。$N\geqq 25$ とし、
$N-5$ までのすべての20以上の整数が作れると仮定する。
$N-5\geqq 20$ なので $N-5$ は作れ、そこへ5円切手を1枚加えれば
$N$ も作れる。強い帰納法により20円以上のすべてが作れる。