一个组合题

如果我们要把 n 个水果装进一个塑料袋里，且这些水果满足以下限制：
１，苹果数必须是偶数
２，香蕉数必须是５的倍数
３，橙子最多４个
４，梨最多１个。
一共有多少种不同的装法？

[color=Silver][[i] 本帖最后由 颖颖 于 2010-7-26 10:22 编辑 [/i]][/color]

如果我们要把 n 个水果装进一个塑料袋里，且这些水果满足以下限制：
１，苹果数必须是偶数
２，香蕉数必须是５的倍数
３，橙子最多４个
４，梨最多１个。
一共有多少种不同的装法？

梨子數是1或0
橙可以是4或3或2或1或0
就這兩種的話組合是10種裝法

前面兩個考慮進去的話,再想想:hz1026:


承上帖,總可能性等於組合數的積

把四種水果的組數分別設為a,b,c,d
(蘋果兩個一組,香蕉五個一組,其他一個一組)

已知2a+5b+c+d=n
限制a,b必須是正數,c,d就是上面那十個可能性
求a*b*c*d in term of n,貌似不可能

[color=Silver][[i] 本帖最后由 青炎陽 于 2010-7-26 10:41 编辑 [/i]][/color]

到底有几个水果？

回复 #3 KYOKO 的帖子

不限。

例如，n=1，有两种装法：
１，一个橙子
２，一个梨。

n=2，有三种装法：
１，两个苹果＋一个橙子
２，两个苹果＋一个梨
３，两个橙子＋一个梨

现在问的是，对于一个广义的 n，一共有多少种装法？

先考虑简单的问题：
如果我们要把 n 个水果装进一个塑料袋里，且这些水果满足以下限制：
１，苹果数必须是偶数
３，橙子最多４个
４，梨最多１个。
一共有多少种不同的装法？

结论：当n<5时，有n+1种。次序：橙子(n+1种)，苹果(1种)，梨(1种)。
当n>4时，有5种。次序：橙子(5种)，苹果(1种)，梨(1种)。

猜测 ，原题答案有n+1种。

這題就是一障眼法，其實答案很簡單：n+1种。

反正就是往塑料袋里裝蘋果和香蕉，梨作為替補必要時來替換一個蘋果，橙子作為替補必要時來替換1、2、3、4個香蕉，把它們視為蘋果和香蕉的鏡像就行了。

回复 诸位

证明！做数学一定要证明！

P.S. 其实我也不知道答案。。。

这道题是悉尼男子高中（i.e. 不是 James Ruse 高中，难度应该不会很大） 8 年级（初二）的 Maths Enrichment Class 里出的。

[color=Silver][[i] 本帖最后由 颖颖 于 2010-7-26 13:34 编辑 [/i]][/color]

回复 #8 颖颖 的帖子

证明思路秀辰兄已经给出，无非是换数学语言陈述的问题

建立一个映射：从 满足题设条件的装法 映射到 只装苹果香蕉且不限被2，5整除的装法
然后证明它是单射和满射从而是双射从而是n+1
单射和满射都简单用定义证即可

设苹果、香蕉、橙子、梨分别为A,B,C,D。A+D=P,B+C=Q。

n分为（P,Q）共n+1种。
对任意的P，只有1种分法满足苹果和梨。即A=P/2,D=P mod 2。
对任意的Q，只有1种分法满足香蕉和橙子。即B=P/5,C=P mod 5。

综上所述，满足条件的分法有n+1种。

这个题很好。

回复 #8 颖颖 的帖子

或者有更直觀的證明方法，需要以下兩個步驟：

1.用N個梨和橙子裝滿塑料袋，有N+1種裝法——很簡單；

2.將每2個梨換成蘋果，每5個橙子換成香蕉，有唯一的換法——也很簡單。

兩個都應該是抽屜原則及其延伸吧。

我非數學專業，無法用嚴謹的數學語言來表述，不過思路已經非常簡潔明快了吧？

n=（苹果+梨）+（香蕉+橙子）
这道题目，转化一下，就是将n拆分成两个非负整数有序对的个数，（n,0),(n-1,1),……
所以是n+1种情况。因为只要给出一种分发，都可以有唯一的水果个数对应方式，梨的个数是2的余数，橙子的个数是5的余数，这样肯定是一对一的。呵呵。

[color=Silver][[i] 本帖最后由 鸟窠道人 于 2010-7-26 22:40 编辑 [/i]][/color]

回复 #11 dimeterio 的帖子

倒也对，最关键的地方确实如此。

呃，题目少了个条件：

原题为：
『如果我们要把 n 个水果装进一个塑料袋里，且这些水果满足以下限制……』
其中只是要求“水果”，没有要求水果必须是“苹果、香蕉、橙子 or 梨”，所以可以一个都不放（符合1、2、3、4条件），然后往里面塞任意个桔子、任意个西瓜（塞的下么）、任意个樱桃、任意个石榴……


必须加上

如果我们要把 n 个水果装进一个塑料袋里，且这些水果满足以下限制：
０，水果必须是苹果、香蕉、橙子、梨的一种。
１，苹果数必须是偶数
２，香蕉数必须是５的倍数
３，橙子最多４个
４，梨最多１个。
一共有多少种不同的装法？

[quote]原帖由 [i]颖颖[/i] 于 2010-7-26 10:18 发表
如果我们要把 n 个水果装进一个塑料袋里，且这些水果满足以下限制：
１，苹果数必须是偶数
２，香蕉数必须是５的倍数
３，橙子最多４个
４，梨最多１个。
一共有多少种不同的装法？ [/quote]
最近刚学了组合数学，。。把这个问题建立模型
以下1代表不放，x^2表示放2个,以此类推。。
苹果数为偶数设为：1+x^2+x^4+......说明苹果可以没有，或者是2个或者是4个。。。
香蕉树为5的倍数：1+x^5+x^10+.....
橙子数最多为四个：1+x+x^2+x^3+x^4
梨子数最多1个：1+x
则（1+x^2+x^4+......）*（1+x^5+x^10+.....）*（1+x+x^2+x^3+x^4）*(1+x)化简后x^n的系数恰好就是n个水果不同的放法
（1+x^2+x^4+......）*（1+x^5+x^10+.....）*（1+x+x^2+x^3+x^4）=1/（1-x^2)*1/(1-x^5)*(1-x^5)/(1-x)*(1+x)=1/(1-x)^2
=1+2x+3x^2+4x^3+.......+(n+1)x^n...

其中 1/(1-x)^n=1+nx+n(n+1)x^2/2!+n(n+1)(n+2)x^3/3!+.....:hz1019:

这个方法算是这种常见问题的通解吧:hz1019::hz1019:

[color=Silver][[i] 本帖最后由 zhaohaidao 于 2010-10-18 17:12 编辑 [/i]][/color]

[quote]原帖由 [i]颖颖[/i] 于 2010-7-26 12:52 发表
不限。

例如，n=1，有两种装法：
１，一个橙子
２，一个梨。

n=2，有三种装法：
１，两个苹果＋一个橙子
２，两个苹果＋一个梨
３，两个橙子＋一个梨

现在问的是，对于一个广义的 n，一共有多少种 ... [/quote]

n=2，有三种装法：
１，两个苹果
２，一个橙子＋一个梨
３，两个橙子
是这样吧

[color=Silver][[i] 本帖最后由 toushion 于 2010-11-3 18:34 编辑 [/i]][/color]