問題はこちら（画像をクリックするとPDFファイルで開きます。）
自然数を和として分割する方法について考える問題です。
シンプルでキレイな題意は、アレンジしようにもそれ以上手を加える余地があまりなく、それ以降出題を考えても二番煎じになってしまうためかえって出題を敬遠されるかもしれません。
ただ、シンプルで分かりやすく、難易度が適度におさまり、かつ手垢の付いていない良問というのはそう簡単には生み出せるものではありません。
本問は上述の良問要素を含んでいると思います。
（もちろん見る人が見たら手垢はついていると思いますが）
（以下ネタバレ注意）
+ クリック（タップ）して続きを読む
実験して要領を掴む
(1) , (2) はある意味実験設問です。
４からとは言わず、最初の１から考えてみます。
なお、本問においては \(n\) そのものは許されないのですが、ひとまず \(n\) そのものも許して表現します。
３の和分割
- \(1+1+1\) , \(1+2\)
- \(2+1\)
- \(3\)
４の和分割
- \(1+1+1+1\) , \(1+1+2\) , \(1+2+1\) , \(1+3\)
- \(2+1+1\) , \(2+2\)
- \(3+1\)
- \(4\)
というように (1) は実験の範疇で片付きます。
ただ、後に繋げるために、(2) の \(n=5\) のときはオチである一般論に繋がるような考え方で導出したいところです。
こうして実験してみると、例えば４の和分割を求める際には
- \(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)\)
と整理でき、等比数列であることが見出せます。
路線２
定番の考え方と言ってしまえばそれまでなのですが、
と対応付けて考えることもできます。
例えば (1) を例にとれば
\(〇｜〇〇｜〇\)
という区切りの場合
\(1+2+1\)
と対応付けます。
「分割」という言葉のイメージをそのまま体現した方針です。
この路線については【戦略２】【解２】で扱っています。
解答はコチラ
