場合の数・確率系 実践演習

自然数の和分割【2002年度 大阪教育大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。)

自然数を和として分割する方法について考える問題です。

シンプルでキレイな題意は、アレンジしようにもそれ以上手を加える余地があまりなく、それ以降出題を考えても二番煎じになってしまうためかえって出題を敬遠されるかもしれません。

ただ、シンプルで分かりやすく、難易度が適度におさまり、かつ手垢の付いていない良問というのはそう簡単には生み出せるものではありません。

本問は上述の良問要素を含んでいると思います。

(もちろん見る人が見たら手垢はついていると思いますが)

(以下ネタバレ注意)

+ クリック(タップ)して続きを読む

実験して要領を掴む

(1) ,  (2) はある意味実験設問です。

4からとは言わず、最初の1から考えてみます。

なお、本問においては \(n\) そのものは許されないのですが、ひとまず \(n\) そのものも許して表現します。

1の和分割

  •  \(1\)

2の和分割

  • \(1+1\)
  • \(2\)

3の和分割

  • \(1+1+1\) ,  \(1+2\)
  • \(2+1\)
  • \(3\)

4の和分割

  • \(1+1+1+1\) ,  \(1+1+2\) ,  \(1+2+1\) ,  \(1+3\)
  • \(2+1+1\) ,  \(2+2\)
  • \(3+1\)
  • \(4\)

というように (1) は実験の範疇で片付きます。

ただ、後に繋げるために、(2) の \(n=5\) のときはオチである一般論に繋がるような考え方で導出したいところです。

こうして実験してみると、例えば4の和分割を求める際には

  • \(1+(3 の和分割)\)
  • \(2+(2 の和分割)\)
  • \(3+(1 の和分割)\)
  • \(4\) そのもの

というようになっています。

つまり \(4\) 以前の

  • \(3\) の和分割
  • \(2\) の和分割
  • \(1\) の和分割

が得られていれば、それをくっつけていけばいいわけです。

この要領で次の \(n=5\) のときを考えると

  • \(1+(4 の和分割):8 通り\)
  • \(2+(3 の和分割):4 通り\)
  • \(3+(2 の和分割):2 通り\)
  • \(4+(1 の和分割):1 通り\)
  • \(5\) そのもの:\(1通り\)

となり、\(5\) の和分割の方法は

\(8+4+2+1+1=16【通り】\)

となりますが、本来、本問の設定においては \(5\) そのものは実際には許されないため

\(16-1=15【通り】\)

ということになります。

一般論への拡張

こうなってくるとよぎるのは

  • 自然数 \(n\) の和分割の方法を \(a_{n}\) 通り

とする漸化式の導入です。

自然数 \(n+1\) の和分割の方法の総数 \(a_{n+1}\) について考えてみます。

  • \(1+(n の和分割):a_{n} 通り\)
  • \(2+(n-1 の和分割):a_{n-1} 通り\)
  • \( \  \  \  \  \  \ \vdots \  \  \  \ \)
  • \(n+(1 の和分割):a_{1} 通り\)
  • \(n+1\) そのもの

ですから、

  • \(a_{n+1}=a_{n}+a_{n-1}+\cdots+a_{1}+1\)

という漸化式が立つことになります。

このあとは

  • \(a_{1}+a_{2}+\cdots+a_{n}=S_{n}\)

とおくと

$$\begin{eqnarray}
\left\{
\begin{array}{l}
a_{n+1}=S_{n}+1 \\
a_{n}=S_{n-1}+1 \ (n \geq 2)
\end{array}
\right.
\end{eqnarray}$$

とし、

和から一般項

\(S_{n}-S_{n-1}=a_{n} \ (n \geq 2) \)

を狙って、辺々引くと

\(a_{n+1}-a_{n}=a_{n} \ (n \geq 2)\)

すなわち

\(a_{n+1}=2a_{n} \ (n \geq 2)\)

と整理でき、等比数列であることが見出せます。

路線2

定番の考え方と言ってしまえばそれまでなのですが、

  • 〇と仕切りを並べる方法

と対応付けて考えることもできます。

例えば (1) を例にとれば

\(〇|〇〇|〇\)

という区切りの場合

\(1+2+1\)

と対応付けます。

「分割」という言葉のイメージをそのまま体現した方針です。

この路線については【戦略2】【解2】で扱っています。

解答はコチラ

-場合の数・確率系, 実践演習
-,

© 2022 MathClinic