【奥数第5题】2015年4月15日

plr

今天来个简单点的计数的题，让不管离开高中多久的人都能做
（1）我们可以把一个正整数表示成若干个1或2的和， 比如对于数字5， 有
     5=1+1+1+1+1
     5=1+1+1+2
     5=1+1+2+1
     5=1+2+1+1
     5=2+1+1+1
     5=1+2+2
     5=2+1+2
     5=2+2+1
     即5有8种表示方法， 今天是15年4月15日，就问15有多少种表示方法吧？
（2）我们还可以把一个正整数表示成若干（可以是1个）个大于1的自然数的和，
比如对于数字8， 有
     8=2+2+2+2
     8=2+2+4
     8=2+4+2
     8=4+2+2
     8=2+3+3
     8=3+2+3
     8=3+3+2
     8=2+6
     8=3+5
     8=4+4
     8=5+3
     8=6+2
     8=8
    居然有13种之多，那么还是问数字15有多少种这样的表示方法呢？

【说明】 只是答案正确的， 每道+5金， 如果带清楚的解析过程的， 每道+10金吧

北大侠客行MUD，中国最好的MUD

pizzagoo

排列组合啊

all

(1)
1=1，共1种，
2=1+1
2=2，共2种，
3=1+1+1
3=1+2
3=2+1，共3种，
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=2+2，共5种，
5=，共8种，

1，2，3，5，8，居然还是类斐波那契数列。

all

(2)
2，1种，3，1种，4，2种，5，3种，6，5种，7，8种，8，13种，
1，1，2，3，5，8，13，斐波那契

老师是斐波那契的后代？

plr

回复 4# all

all， 你这是不完全归纳法啊！ 要证明 a_n+2 =  a_n+1 + a_n

hash

我们高中老师说过：由观察法得。。。。。

all

（1）我们可以把一个正整数表示成若干个1或2的和：

令a(n)为把n表示成若干个1或2的和的种数，则a(1)=1，a(2)=2，a(3)=3，满足a(3)=a(2)+a(1),
下面证明对所有的n，a(n+2)=a(n+1)+a(n)都成立。
把n+2表示成若干个1或2的和，那么这若干个数的最后一个或者是1，或者是2。
当最后一个数是1时，前面若干个1或2的总和是n+1，总共有a(n+1)种表示方法；
当最后一个数是2时，前面若干个1或2的总和是n，总共有a(n)种表示方法；
因此a(n+2)=a(n+1)+a(n)。

plr

回复 7# all


    期待第2问

all

（2）我们还可以把一个正整数表示成若干（可以是1个）个大于1的自然数的和

令a(n)为把n表示成若干个大于1的数的和的种数，则a(2)=1，a(3)=1，a(4)=2，满足a(4)=a(3)+a(2),
下面证明对所有的n（n>=2)，a(n+2)=a(n+1)+a(n)都成立。
把n+2表示成若干个大于1的数的和，那么这若干个数的最后一个或者是2，或者不是2（大于2）。
当最后一个数是2时，前面若干个数的总和是n，总共有a(n)种表示方法；
当最后一个数不是2（大于2）时，这最后一个数最小是3，最大是n+2，如果把每个表示法的最后一个数都减去1，那么所有的数加起来等于n+1，这时最后一个数最小是2，最大是n+1，刚好满足把n+1分成若干个大于1的自然数的条件，所以共有a(n+1)种表示法。
综上所述，对所有n（n>=2)，都满足a(n+2)=a(n+1)+a(n)。