GE : NS I 数学の構造

問題編

• １対１対応
• 数学的帰納法

１対１対応

• 山の木の本数を縄によって数える。
• トーナメントにおける試合の数。

X を数えたいけれど数えにくいものの集合としたとき、数えやすいものからなるある集合 Y と、X から Y への、１対１対応を見つける。すると、X の元（要素）の数と、Y の元の数は等しいから、それによって、X の元の数がわかる。

例えば、上の最初の例では、X は、山の木、Y は、縄ということで、次の例では、X は、トナメントの試合で、Y は、トーナメントによって負けるチームということになります。

1. トーナメントで、敗者復活戦があるときは、どうでしょうか。通常、敗者復活戦を組む組み方は、色々とありますが、２敗したら失格。としておきましょう。二チームのときは、２試合か、３試合ですね。３チームのときは、どうでしょうか。４９チームのときは、どうでしょうか。

2. １２個入りのキャラメルを一箱買って、守、悟、望、喜子、悦子の、５人の兄弟に分けたい。それぞれが最低１個はもらえるようにすると、何通りの分け方があるでしょうか。

3. １２個入りのキャラメルを一箱買って、守、悟、望、喜子、悦子の、５人の兄弟に分けたい。何通りの分け方があるでしょうか。こんどは、一つももらえない子どもがいても良いとします。

4. 自然数 n を m 個の自然数の和として表すとき、加える数の順序も考慮に入れて何通りの表し方があるでしょうか。

5. 0 < a < b < c < d < 12 であるような自然数の組 (a,b,c,d) は全部で何通りあるでしょうか。

6. 今度は、a は b 以下、b は c 以下、c は d 以下、d は １６以下とします。このような自然数の組 (a,b,c,d) は全部で何通りあるでしょうか。

TOP

NSI HOME

HOME

数学的帰納法

THEOREM [Mathematical Induction]
P(n) は、自然数 n に関するある命題を表すものとする。このとき、(I)、(II) が成立するとする。
(I) P(n₀) は、正しい。
(II) n₀ 以上の k について、P(k) が正しいと仮定のもとでは、P(k+1) は正しい。
このとき、n₀ 以上のすべての n について、P(n) は正しい。

PROOF
Let S = {n > n₀-1 : P(n) is false}. We want to show that S is empty. Suppose not. Let m = min S. By (I), m is not equal to n₀. Hence m > n_0. By the minimality of m, P(m-1) is true. Now by (II), P(m) is true as well, which contradicts m being in S. Therefore, S is empty. Q.E.D.

1. n を非負整数とする。このとき、11ⁿ⁺² + 12²ⁿ⁺¹ は、133 で割り切れる。
2. n を非負整数とする。このとき、２ⁿ× + ２ⁿ ー １ は、３ で割り切れる。
3. サイズ ２ⁿ× + ２ⁿ のチェス盤から一ますを抜き取ったものを B_n と呼ぶことにすると、すべての、　B_n は、B₁ で敷き詰めることが出来る。