あなたが他の 9 人と一緒にパーティーに参加していて、全員が 1 回だけ他の人と握手したとします。握手は何回行われますか？

これは「握手問題」で、私のお気に入りの 1 つです。数学教師として、私がこのプログラムを気に入っているのは、解決策に到達するためのさまざまな方法があり、それらの戦略の多様性と相互関連性が数学における創造的思考の力を美しく示しているからです。

解決策の 9 つは次のとおりです。まず、各人が他の人と握手することから始めます。 10 人がそれぞれ 90 回の握手を行うと、合計 90 × 2 = 45 回の握手が行われます。ただし、これではすべてのハンドシェイクが XNUMX 回 (各シェーカーの観点から XNUMX 回) カウントされるため、実際のハンドシェイク数は $latex frac{XNUMX}{XNUMX} = XNUMX$ になります。勝利のためのシンプルで素敵な数え方の議論!

問題を解決するためのまったく異なる方法もあります。ゲストが一度に 0 人ずつ到着し、到着したら、出席者全員と握手することを想像してください。最初の人は握手する必要がないため、1 人パーティーでは合計握手はゼロになります。今度は1人目が到着し、最初の人と握手します。これにより、合計に XNUMX 回の握手が追加されるため、XNUMX 人パーティーの場合、合計握手数は XNUMX + XNUMX = XNUMX になります。 XNUMX 人目が到着し、最初の XNUMX 人のゲストと握手すると、合計に XNUMX 回の握手が追加されます。 XNUMX 人目の人が到着すると、握手が合計に XNUMX 回追加され、以下同様に続きます。

この戦略は、ハンドシェイクのシーケンスを再帰的にモデル化します。つまり、シーケンス内の各用語は、その前にある用語と比較して定義されます。おそらく、最も有名な再帰数列であるフィボナッチ数列についてはよくご存じでしょう。 1、1、2、3、5、8、13、21 で始まり、前の XNUMX つの合計に等しい後続の各項が続きます。

以下で説明するように、再帰は、幅広い数学的アイデアを考えるための柔軟で強力なフレームワークです。そして、ヘマチャンドラのような古代インドの学者は 1150 年にこの種の数列について知っていたと信じられていますが、それらは今日でも数学者に興味深い課題を提供しています。

再帰的に考えることがハンドシェイク問題にどのように役立つかを見てみましょう。 $latex a_n$ を、ある時点でのハンドシェイクの数と等しくすると、 n-person party の場合、この再帰関係は次の式で表すことができます。

$latex a_n = a_{n-1} + n–1$

これは、一度の握手の数がわかります。 n- 参加者 ($latex a_n$) は、(n − 1) 1人パーティー ($latex a_{n-XNUMX}$) プラス n − 握手をもう 1 回。新しい人が到着すると、すでに行われた握手に一定数の新しい握手が追加されるというアイデアを捉えています。

ハンドシェイク問題の特定のバージョンでは、10 人のパーティーでの握手の数である $latex a_{10}$ を知りたいので、再帰的関係を使用することを確認します。

$ラテックス a_{10} = a_9 + 9$

$latex a_{10}$ の値を見つけるには、$latex a_9$ の値を知り、それに 9 を加算するだけです。 $latex a_9$ の値を見つけるにはどうすればよいでしょうか?もちろん再帰を使用します。

$ラテックス a_9 = a_8 + 8$

ここで、$latex a_8$ の値を見つけるには、$latex a_7$ の値を見つける必要があります。これには、$latex a_6$ を知る必要があります。この時点で、これが一種の無限降下で永遠に続くのではないかと心配するかもしれませんが、$latex a_1$ に到達したら完了です。XNUMX 人パーティーでは合計握手がゼロであることがわかっているためです。

$ラテックス a_1 = 0$

この初期値または「シード」値は、再帰シーケンスの重要な機能です。これにより、再帰的関係を使用してシーケンスを遡るこのプロセスが終了することが保証されます。シード値に到達すると後戻りは停止し、リスト内を前に進んで必要な値を取得できます。

$ラテックス a_1 = 0$

$ラテックス a_2 = a_1 + 1 = 0 + 1 = 1$

$ラテックス a_3 = a_2 + 2 = 1 + 2 = 3$

$ラテックス a_4 = a_3 + 3 = 3 + 3 = 6$

$ラテックス cdot$

$ラテックス a_{10} = a_9 + 9 = 36 + 9 = 45$

リストを調べてみると、45 人のパーティーでは合計 10 回の握手が行われることがわかり、これは最初の計算と一致します。もしあなたが私の生徒と同じなら、すでに答えがわかっているのに、なぜこの問題を解決する別の方法が必要なのか、特にこの XNUMX 番目のアプローチには時間がかかりそうなのに、と疑問に思うかもしれません。

良い質問ですね。答えの 1 つは、再帰的アプローチにより、この問題で何が起こっているかについてまったく異なる視点が得られるということです。また、あらゆる物事と同様に、数学においてもさまざまな視点が役に立ちます。これらは概念を理解するためのさまざまな機会を与え、行き詰まったときに役立つさまざまなツールを使用できるようにします。

特に、再帰は数学のいたるところで使用されるため便利です。たとえば、数学の授業で誰もが学ぶ線形関係、つまり一定の変化率を特徴とし、平面内の線で表される関係の中でそれが生じます。 $latex f(x) = 3x + 5$ のような線形関数は、再帰式と考えることができます。

$ラテックス a_0 = 5$

$ラテックス a_n = a_{n-1} + 3$

$latex f(2)$ について考えるより明白な方法は $latex f(2) = 3 掛ける 2 + 5 = 11$ であるかもしれませんが、別の方法は $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11ドル。線形関数の基本特性である一定の変化率を再帰的にモデル化すると、この関係について別の方法で考えることができます。一定の乗法変化を特徴とする指数関数でも同じことができます。

再帰的思考は、一連の数字以外にも機能します。連立方程式を解いたことがあれば、おそらく再帰的アプローチを適用したことがあるでしょう。システムを解決するには

$ラテックス 2x + y = 10$

$ラテックス 3x – y = 5$

まず 2 つの方程式を加算して、 y 変数を使用すると、方程式 $latex 5x = 15$ が得られます。これを解いて $latex x =$ 3 を取得し、代入して $latex y = 4$ を見つければ完了です。このアプローチでは再帰的アルゴリズムが利用され、システムのソリューションがそのソリューションからより小さな関連システムに構築されます。たとえば、3 × 3 システムを解くには、2 つの変数を削除して 2 × 1 システムに変換し、次に再度 1 × XNUMX システムに変換します。この簡単に解ける単一の方程式は、この再帰的プロセスのシード値のようなものです。これは後戻りの終了を示し、そこから再帰シーケンスのように一連の方程式を遡っていきます。

再帰的証明テクニックさえあります。たとえば、幾何学の有名な公式は多角形の角度の合計公式です。これは、多角形の内角の測度の合計を示します。 n辺多角形は $latex (n-2) の 180^{circ}$ 倍です。この結果を証明する XNUMX つの方法は、 n-ゴン、そして三角形を削除したら何が起こるかを想像してください。

三角形を削除すると、 n-gon に (n − 1)-gon であり、内角 180 度も削除されます。これは再帰的な関係です。つまり、 n-gon は、() の内角の合計より 180 度大きいです。n − 1)-ゴン。一般的な結果を確立するには、シード値に達するまで三角形を削除し続けます。この状況では、XNUMX つを除くすべての三角形を削除したときに発生します。 n-ゴンの頂点。この時点で、最初の多角形は三角形に縮小されており、その内角の合計は 180 度であることがわかっています。ここで、各ステップで 180 度を加算しながら元に戻り、公式を取得します。

私たちの話に戻りますが、握手の問題自体は、私たちが創造的に考え、問題に対する複数の異なる視点を結びつけると何が可能になるかを示しています。一連のハンドシェイクの再帰モデルを試してみると、次のようになります。

$ラテックス a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

素晴らしいパターンが現れます:

$ラテックス a_2 = a_1 + 1 = 0 + 1$

$ラテックス a_3 = a_2 + 2 = 0 + 1 + 2$

$ラテックス a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$ラテックス cdot$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

この問題について、新しく一般的な考え方ができました。それは、1 回のハンドシェイクの数です。 n-人のパーティは最初のパーティの合計と等しい n − 1 つの正の整数。

私たちの当初のアプローチを思い出してください。で n-1人パーティー、各人が他の人と握手します n − 1名。積 $latex n (n-1)$ はすべてのハンドシェイクを 1 回カウントするため、ハンドシェイクの合計数は $latex frac{n(n-2)}{XNUMX}$ になります。しかし、異なる方法でも同じものをカウントするため、同じ結果が得られる必要があります。特に、これは次のことを意味します。

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

ハンドシェイク問題へのさまざまなアプローチを接続すると、最初の和の閉じた式が得られます。 n − 1 つの正の整数。しかし、さらに多くのことがわかります。式 $latex frac{n(n-1)}{2}$ には分数が含まれていますが、これは整数の合計に等しいため、これも整数でなければなりません。これは数論の単純な事実を証明します: すべての整数について n, $latex frac{n(n-1)}{2}$ は整数です。

これと同じ種類の議論が現代数学に力を与え続けています。一例として、2000 年代初頭の研究者たちは、 いくつかの驚くべき結果が証明された ソモス シーケンスとして知られる再帰シーケンスについて、それらも何かをカウントすることを示すことで説明します。数学者は、創造的なつながりの力を通じて、自分たちがこれまでどこにいたのかを理解することで、どこに行くことができるかを再び発見しました。

演習

1. 次のように再帰的に定義されるシーケンスの閉じた式を見つけます。
$ラテックス a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. 列の最後で、式 $latex frac{n(n-1)}{2}$ は、式に分数が含まれているにもかかわらず整数であることが示されました。$latex frac{n(n-1 )}{2}$ は何かを数えた結果です。この式が整数でなければならないことを示す数論の議論もあります。それは何ですか？

3. 再帰シーケンスの最初のいくつかの項を見つけます
$ラテックス a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. 再帰シーケンスの最初のいくつかの項を見つけます
$ラテックス a_1 = 1$
$ラテックス a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$