関連スライド
各ページのテキスト
入試問題解説 第 26 回：ユークリッドの互除法 と数学的帰納法 2019 大 阪 大 学 理 系 大 問 4
入試問題解説 問題 下の図は， p p p+q 1 から始めて分数 の左下に分数 ，右下に分数 を配置す 1 q p+q q るという規則でできた樹形図の一部である。このとき以下の問いに答えよ。 1 1 1 2 2 1 1 3 1 4 3 2 4 3 3 5 2 3 5 2 2 5 3 1 5 3 3 4 4 1 (1) この樹形図に現れる分数はすべて既約分数であることを示せ。ただし整数 n は 1 既約分数とみなす。 (2) すべての正の有理数がこの樹形図に現れることを示せ。 (3) この樹形図に現れる有理数はすべて異なることを示せ。 19 (4) はこの樹形図の上から何段目の左から何番目に配置されるか答えよ。たとえ 44 3 ば， は上から 3 段目の左から 4 番目である。 1 (2019 大阪大学 理系 大問 4) ■ 本問の学習テーマ・目的 本問では「2 数の大きい方から小さい方を引いても最大公約数は変わらない」という互除 法の性質を用います。さらに分子と分母の和に関する数学的帰納法を用い，すべての正 の有理数がちょうど 1 回ずつ現れることを証明します。 指針 / アプローチ ▼ (1) 互いに素であること ▼ (2)(3) 和についての帰納法 ▼ (4) 段数と左からの番号 分子と分母の公約数を調べます。 段数についての数学的帰納法です べての分数が既約分数であること を示します。 p p < q なら ，p > q な q¡p p¡q ら が 1 段上の分数です。 q 19 1 から 1 段ずつ上へ戻り， 44 1 分子と分母の和は必ず小さくなり ます。 (2) では任意の正の既約分数が現れることを示します。何段 までの回数を数えます。左下・右 下へ進む順序を調べ，左から何番 目かを求めます。 目に現れるかは分からないため，右図のように 1 段上の分数 p q¡p p¡q q を求めます。分子と分母の和は必ず小さくなるので，この和 p<q p>q に関する数学的帰納法を用います。 p q (3) では 1 段上の分数とその配置，およびそこから進む向き 分子・分母の大小関係から が一意に定まることから，各分数の現れる位置が 1 か所に限 1 段上の分数が特定できます られることを示します。 --- 1 --- © ブリザードマン @HhG2cL9UOLRSz4I 無断転載・共有禁止
入試問題解説 解答 (1) 上から n 段目に現れる分数はすべて既約分数であることを，n に関する数学的帰納法で示す。 正の整数 a; b の公約数は a; a + b の公約数とも a + b; b の公約数とも一致する。よって a; b が互いに素なら a; a + b と a + b; b も互いに素であり，既約分数の左下と右下に配置 1 される分数も既約分数である。上から 1 段目の は既約分数なので，数学的帰納法により示 1 された。 （証明終わり） (2) p p と表せる。この が樹形図に現 q q p 1 れることを p + q に関する数学的帰納法で示す。p + q = 2 なら = であり，上から 1 q 1 任意の正の有理数は互いに素な正の整数 p; q を用いて 段目に現れる。 k ≧ 2 とし，分子と分母の和が k 以下の正の既約分数はすべて現れると仮定する。p + q = k + 1 なら p Ë q であり，(*1) (*1) p = q で互いに p q¡p r=Xp¡q q 素なら p = q = 1 で す。和が 3 以上のとき は p = q の場合を除 けます。 (p < q) (p > q) ÝÝ ① は (1) の公約数の性質により正の既約分数である。r の分子と分母の和は q または p で，い ずれも k 以下だから，仮定より r は樹形図に現れる。p < q ならその左下に，p > q なら右 下に p が現れる。よってすべての正の有理数が現れる。 q （証明終わり） (3) p が現れる位置は 1 か所であることを，p + q に関する数学的帰納法で示す。 q p 1 p + q = 2 のときは = である。左下にできる分数は 1 より小さく，右下にできる分数 q 1 1 は 1 より大きいので， は上から 1 段目にのみ現れる。 1 分子と分母の和が k 以下の既約分数が現れる位置はそれぞれ 1 か所であると仮定する。和が p k + 1 の既約分数 の 1 段上の分数は，(1) の既約性から①の r に限られる。r の分子と分 q 母の和は k 以下なので，仮定より r の位置は 1 か所に決まる。そこから進む向きも p < q な 既約分数 ら左下，p > q なら右下に決まる。よって数学的帰納法により，どの有理数も現れる位置は 1 か所である。 （証明終わり） (4) ①で 1 段上へ戻る計算を同じ数を続けて引く部分ごとにまとめると 19 2 回 19 3 回 1 5 回 1 ¡¡! ¡¡! ¡¡! 44 6 6 1 となる。戻る回数は計 10 回なので上から 11 段目にある。頂点の 1 から左下へ 5 回，右下へ 1 19 に到達する。 44 左から j 番目の分数の左下は 2j ¡ 1 番目，右下は 2j 番目である。頂点（左から 1 番目）か 3 回，左下へ 2 回たどれば ら左下へ 5 回進んでも 2 ¢ 1 ¡ 1 = 1 より左から 1 番目のままであり，続く「右下へ 3 回，左 下へ 2 回」の移動で番号は 1 ! 2 ! 4 ! 8 ! 15 ! 29 と変化する。よって求める位置は上 から 11 段目の左から 29 番目である。 --- 2 --- © ブリザードマン @HhG2cL9UOLRSz4I 無断転載・共有禁止
入試問題解説 答案記載上の注意点 ▼ ポイント 1：帰納法の対象 (1) では段数 n ，(2)(3) では分子と分母の和 p + q に関する数学的帰納法を用います。「帰納 法により」とだけ書かず，対象となる整数を最初に明記します。 ▼ ポイント 2：帰納法で仮定する範囲 1 段上の分数では分子と分母の和は p または q になります。必ずしも k にはなりません。和 が k の場合だけを仮定しても，1 段上の分数にその仮定を使えない場合があります。「和が 2 以上 k 以下のすべての場合」を仮定します。 ▼ ポイント 3：1 段上の分数が既約分数であること p < q の場合は q ¡ p > 0 です。また p; q ¡ p の公約数は p; q の公約数でもあるので， p; q ¡ p は互いに素です。分子と分母が正の整数で互いに素であることを確かめてから，帰 納法の仮定を用います。p > q の場合も同様です。 ▼ ポイント 4：1 段上の分数の位置と進む向き 「1 段上の分数が一意に決まる」だけでは，その分数自体が複数の位置に現れる可能性が残りま す。(3) では帰納法の仮定により 1 段上の分数が現れる位置が 1 か所に決まり，そこから左 下・右下のどちらへ進むかも決まることを書きます。 解説 1. 1 段上の分数の求め方 a a+b < 1，右下にできる分数は > 1 です。したがって 1 より a+b b 小さい分数は 1 段上の分数の左下に，1 より大きい分数は右下に配置されていることが分かり 左下にできる分数は ます。 p a < 1 なら，1 段上の分数を とおくと q b p a です。どちらも既約分数なので a = p， = q a+b a + b = q となり，b = q ¡ p です。 p p a+b > 1 の場合は = から b = q，a = p ¡ q q q b です。つまり 1 段上へ戻るときは分子と分母の大きい方か たとえば ら小さい方を引きます。 p q¡p p¡q q p<q p>q p q 分子・分母の大小関係から 1 段上の分数が特定できます --- 3 --- © ブリザードマン @HhG2cL9UOLRSz4I 無断転載・共有禁止
入試問題解説 2. 分子と分母の和についての数学的帰納法 (1) では樹形図に現れる分数が既約分数であることを示します。上から n 段目から n + 1 段 目へ進む規則を用いて，段数に関する数学的帰納法で証明します。 (2) では任意の正の既約分数が樹形図に現れることを証明します。その分数が何段目に現れる かは分からないため，分子 p と分母 q から定まり，1 段上へ戻るたびに必ず小さくなる正の 整数を考えます。 p < q のときは分子 p が変わらず，p > q のときは分母 q が変わりません。分子だけまたは 分母だけではどちらの場合にも小さくなるとはいえません。ところが和は p + q ¡! U q (p < q) p (p > q) ÝÝ ② と変わり，どちらの場合にも小さくなります。そこで分子と分母の和に関する数学的帰納法を 用います。(*2) (*2) 1 段上へ戻るたび 具体的には和が k 以下の分数から和が k + 1 の分数を作れることを示します。そのため帰納 に小さくなる正の整数 を考えるときは，分子 や分母だけでなく和や 積も候補になります。 法の仮定は「和が k の場合」だけでなく「和が 2 以上 k 以下のすべての場合」とします。こ のように前のすべての段階を仮定する手法も数学的帰納法の一種であり，「和が k 以下の既約 分数はすべて現れる」という命題を k について証明していると捉えれば，通常の帰納法と仕組 みは同じです。 3. 互除法による最大公約数の保存 ユークリッドの互除法では 2 つの正の整数の大きい方から小さい方を引いても最大公約数は変 わりません。本問で 1 段上へ戻る計算はこの引き算そのものです。 (2)(3) では 2 つの性質を用います。最大公約数が変わらないので，1 段上の分数も既約分数 です。また分子と分母の和は小さくなるので，その分数に帰納法の仮定を適用できます。 4. 引き算が終わる理由と最後の分数 異なる 2 つの正の整数について，大きい方を 2 数の差に置き換える操作を行うと，操作後の 2 数も正の整数のままであり，それらの和は 1 以上減少します。和は 2 以上なので，2 数が異な (*3) この議論では最初 る状態でこの引き算を無限に続けることはできません。したがって最後には 2 数が等しくなり の分数が既約分数であ ることが前提となりま ます。 す。たとえば 2 の分 6 最後の 2 数を d; d とすると，その最大公約数は d です。初めの分子と分母は互いに素であ 子と分母に引き算を続 1 になりま り，途中でも最大公約数は 1 のままなので d = 1 です。したがって最後は必ず 1 2 に 2 なります。値は 1 です が，分子・分母は 1 に す。(*3) このことからも (2) を証明できます。与えられた既約分数から 1 まで戻れれば，その順序を 1 逆にして樹形図を下へ進むことができます。解答ではこの和が小さくなることを用いて数学的 帰納法で証明しました。 --- 4 --- © ブリザードマン @HhG2cL9UOLRSz4I 無断転載・共有禁止 けると，最後は なりません。
入試問題解説 5. 互除法を用いた段数と位置の計算 19 から 1 段ずつ上へ戻るときに，同じ数を繰り返し引く計算をまとめると，44 = 2 ¢ 19 + 6， 44 19 = 3 ¢ 6 + 1，6 = 5 ¢ 1 + 1 と表せます。最初は分母 44 から分子 19 を 2 回引きます。次は 分子 19 から分母 6 を 3 回引き，最後は分母 6 から分子 1 を 5 回引きます。最後の式は 2 数が 1 と 1 になったところで止めるための書き方です。通常の互除法では余りが 0 になるまで計算 しますが，ここでは分子と分母がともに 1 になったところで止めます。 上へ戻る計算 19 19 ! 44 6 19 1 ! 6 6 1 1 ! 6 1 引き算の回数 下へ進むときの向き 2回 左下 3回 右下 5回 左下 1 から下へ進むときは表を下から読みます。左下へ 5 回，右下へ 3 回，左下へ 2 回進みます。 1 上へ戻るときとは順序が逆になることに注意します。1 段目（頂点）を基準として 10 回移動す るため，11 段目に配置されます。 左から j 番目の分数の前には j ¡ 1 個の分数があり ます。次の段ではそれらから 2(j ¡ 1) 個の分数がで きます。そのため左下は 2j ¡ 1 番目，右下は 2j 番 目です。 j 番目 左下 右下 2j 番目 (2j ¡ 1) 番目 6. 存在と一意性の証明 (2) では 1 段上の分数が樹形図に現れると仮定し，目的の分数も現れることを示しました。 (3) では 1 段上の分数が現れる位置は 1 か所であると仮定し，目的の分数が現れる位置も 1 か 所であることを示しました。 用いる式は同じでも，帰納法で仮定する内容が異なります。「樹形図に現れること」と「現れる 位置が 1 か所であること」を区別して仮定と結論を書くことが大切です。 ■ 復習のポイント ★★★★★ 互除法：大きい方から小さい方を引いても最大公約数は変わりません ★★★★★ 帰納法の対象：(1) は段数，(2)(3) は分子と分母の和です ★★★★★ 帰納法の仮定：和が 2 以上 k 以下のすべての場合を仮定します ★★★★★ 位置の一意性：1 段上の分数の位置とそこから進む向きを確定します ★★★★☆ 位置の計算：左下は 2j ¡ 1 番目，右下は 2j 番目です --- 5 --- © ブリザードマン @HhG2cL9UOLRSz4I 無断転載・共有禁止