ホーム >> その他 >> 正整数の分割における得点の最大化
hide or visible

問題の説明

与えられた正整数を,和が一定の二つの正整数に分割する操作を行い,分割後の二つの数の積を得点として獲得します.各分割のしかたは和が一定の正整数であれば,どんな $2$ つの数に分割してもよいです.さて,分割のしかたはいろいろ考えられますが,獲得する得点が最大となるような分割はどのようなものか,というのが問題です.

ヒント

具体的な数で数種類の分割を試みて,総得点を計算してみてください.何か気づくことはないでしょうか.

解答

どのように分割しても,獲得する総得点が必ず $\frac{1}{2}n(n-1)$ となることを,帰納法で示します.
$n=1,2$ のとき,明らかに獲得できる得点は $0,1$ であるからこの場合はOKです.
$1,2,...,n$ のとき,結論が成り立つと仮定して,$n+1$ の場合に獲得する総得点が $\frac{1}{2}(n+1)n$ であることを示します.
はじめに $n+1$ を $k,n+1-k$ に分割したとします.($0< k < n+1$) このとき獲得する得点は $k(n+1-k)$ です.帰納法の仮定から,$k,n+1-k$ の分割で獲得できる総得点はそれぞれ $\frac{1}{2}k(k-1),\frac{1}{2}(n+1-k)(n-k)$ です.したがって,$n+1$ の分割によって獲得する総得点は, $$k(n+1-k)+\frac{1}{2}k(k-1)+\frac{1}{2}(n+1-k)(n-k)$$ $$=\frac{1}{2}\{(2nk+2k-2k^2)+(k^2-k)+(n^2-2nk+n-k+k^2)\}$$ $$=\frac{1}{2}n(n+1)$$ よって,$n+1$ のときも成り立つ.

以上より,$n$ をどのように分割しても,獲得する総得点は必ず $\frac{1}{2}n(n-1)$ であるので,獲得する総得点の最大値も $\frac{1}{2}n(n-1)$ です.