多分、平成２１年３月２１日付けで、Ｓ（Ｈ）さんから伺った話題だと思う。
ｎ個の石の山が１つある。山を２つに分ける度に２つの山の石の数の積を求める。
最後に、その総和Ｆ（ｎ）を求めると、山の分け方に依らず同じで、
Ｆ（ｎ）＝ｎ（ｎ−１）/２
である。
このことを示せ。
とても深遠な性質である。問題の意味を把握するために、小さいｎについて調べてみよう。
ｎ＝３ のとき、 ○○○ → ○○、○ → ○、○、○
このとき、 Ｆ（３）＝２×１＋１×１＝３ で、 ｎ（ｎ−１）/２＝３×１＝３ より、
Ｆ（ｎ）＝ｎ（ｎ−１）/２ が成り立つ。
ｎ＝４ のとき、 ○○○○ → ○○○、○ → ○○、○、○ → ○、○、○、○
このとき、 Ｆ（４）＝３×１＋２×１＋１×１＝６ で、 ｎ（ｎ−１）/２＝２×３＝６
○○○○ → ○○、○○ → ○○、○、○ → ○、○、○、○
このとき、 Ｆ（４）＝２×２＋１×１＋１×１＝６ で、 ｎ（ｎ−１）/２＝２×３＝６
よって、山分けの方法に依らず、Ｆ（ｎ）＝ｎ（ｎ−１）/２ が成り立つ。
ｎ＝５ のとき、
（１） ○○○○○ → ○○○○、○ → ○○○、○、○ → ○○、○、○、○ → ○、○、○、○、○
（２） ○○○○○ → ○○○○、○ → ○○、○○、○ → ○○、○、○、○ → ○、○、○、○、○
（３） ○○○○○ → ○○○、○○ → ○○○、○、○ → ○○、○、○、○ → ○、○、○、○、○
（１） のとき、Ｆ（５）＝４×１＋３×１＋２×１＋１×１＝１０ で、ｎ（ｎ−１）/２＝５×２＝１０
（２） のとき、Ｆ（５）＝４×１＋２×２＋１×１＋１×１＝１０ で、ｎ（ｎ−１）/２＝５×２＝１０
（３） のとき、Ｆ（５）＝３×２＋１×１＋２×１＋１×１＝１０ で、ｎ（ｎ−１）/２＝５×２＝１０
よって、山分けの方法に依らず、Ｆ（ｎ）＝ｎ（ｎ−１）/２ が成り立つ。
上記の計算を鑑みて、数学的帰納法で示されることに気づく。
ｎ＝１ のとき、２つの山に分けることはできないので、 Ｆ（１）＝０ とすれば、命題は、
ｎ＝１のとき成り立つ。
ｎ＝２ のとき、山分けの方法は、 ○○ → ○、○ のみで、 Ｆ（２）＝１×１＝１
また、ｎ（ｎ−１）/２＝２×１/２＝１ より、命題は、ｎ＝２のとき成り立つ。
ｎ＝ｋ （ｋ≧１）以下について命題は成り立つと仮定する。すなわち、
Ｆ（ｋ）＝ｋ（ｋ−１）/２
ｎ＝ｋ＋１ のとき、２つの山 ｍ と ｋ＋１−ｍ （１≦ｍ≦ｋ） に分けると、
ｍ も ｋ＋１−ｍ も ｋ 以下の山である。
このとき、 Ｆ（ｋ＋１）＝ｍ（ｋ＋１−ｍ）＋Ｆ（ｍ）＋Ｆ（ｋ＋１−ｍ） となる。
よって、 Ｆ（ｋ＋１）＝ｍ（ｋ＋１−ｍ）＋ｍ（ｍ−１）/２＋（ｋ＋１−ｍ）（ｋ−ｍ）/２
＝ｍ（ｋ＋１）−ｍ2＋ｍ（ｍ−１）/２＋｛ｋ（ｋ＋１）−（２ｋ＋１）ｍ＋ｍ2｝/２
＝ｋ（ｋ＋１）/２
となり、命題は、ｎ＝ｋ＋１のときも成り立つ。
したがって、数学的帰納法により、全ての自然数ｎについて、
Ｆ（ｎ）＝ｎ（ｎ−１）/２
が成り立つ。
数々の和さんから別証明を頂いた。（平成２５年７月２１日付け）
山分け問題の証明について、数学的帰納法による証明よりも、題意に忠実かなと思われ
る証明とのことです。確かに、直接的に求められるんですね！
（証明） F(ｎ)は、次の規則により決定される。
ｎ＝ｋ＋ｍ のとき、 F(ｎ)＝F(ｋ)＋F(ｍ)＋ｋｍ および、F(1)＝０
したがって、これらを満たすF(ｎ)を求めればよい。
ｍ＝１ とすると、 F(ｋ＋１)＝F(ｋ)＋F(１)＋ｋ・１＝F(ｋ)＋ｋ
よって、数列 {F(ｋ)}の階差数列が {ｋ} 、F(１)＝０ だから、
ｋ≧２ のとき、 F(ｋ)＝０＋１＋２＋・・・＋(ｋ−１)＝ｋ(ｋ−１)/２
上記の式は、ｋ＝１ のときも成り立つ。
したがって、すべての自然数ｎについて、 F(ｎ)＝ｎ(ｎ−１)/２
逆に、F(ｎ)＝ｎ(ｎ−１)/２ とすると、全てのｍ（１≦ｍ≦ｎ−１）に対して、
F(ｋ)＋F(ｍ)＋ｋｍ＝ｋ(ｋ−１)/２＋ｍ(ｍ−１)/２＋ｋｍ
＝｛（ｋ＋ｍ）2−（ｋ＋ｍ）｝/２＝ｎ（ｎ−１）/２＝F(ｎ)
が成り立つ。したがって、規則を満たすF(ｎ)は、F(ｎ)＝ｎ(ｎ−１)/２ （証終）
