珍珠湾ART

标题: a question from putnam competition [打印本页]

作者: achen 时间: 2004-12-6 00:15
提示: 作者被禁止或删除内容自动屏蔽

作者: sean9991 时间: 2004-12-6 23:30
标题: answer

It's essentially (m+n)^(m+n) > C(m+n, m) * m^m * n^n.

LHS is the total count of sampling (m+n) times from (m+n) objects with replacement.

RHS is the count by (1) seperate the (m+n) objects into two subsets of m and n objects, respectively

(2) sampling each subsets by the number of members of the subsets.

appearantly, LHS is much greater than RHS.

作者: achen 时间: 2004-12-7 01:51
提示: 作者被禁止或删除内容自动屏蔽

作者: sean9991 时间: 2004-12-7 04:03
标题: As explained,

this is a counting problem. Left hand side is the total possible arrangements of m+n choices from m+n objects, with replacement. Right hand side is just partial count, since it's more restricted.

作者: husonghu 时间: 2004-12-7 04:25
标题: 回复：a question from putnam competition

我想sean9991用的是非常smart的方法。我试着用笨办法做 --- 数学规纳法。

因n和m是完全对称的，故可固定其中之一(n)，规纳法证明该式对另一变量(m)为任
意正整数成立即可。

re-write the original as:

(n+m)!/(n!m!)<[(n+m)^(n+m)]/[(n^n)(m^m)]

when m=1,
(n+1)!/(n!1!)<[(n+1)^(n+1)]/[(n^n)(1^1)] is true,
as it can be simplified to show: n+1<(n+1)[(n+1)/n]^n

Assume: (n+k)!/(n!k!)<[(n+k)^(n+k)]/[(n^n)(k^k)] ......(1)

Obviously: [1+1/(n+k)]^(n+k)>(1+1/k)^k

which is combined with (1), we have:
(n+k)!/(n!k!)<[(n+k)^(n+k)]/[(n^n)(k^k)]
<[(n+k)^(n+k)][1+1/(n+k)]^(n+k)/[(n^n)(k^k)(1+1/k)^k]
=[(n+k+1)^(n+k)]/[(n^n)((k+1)^k)] .......(2)

Multiply the two sides of (2) by (n+k+1)/(k+1), and simplify, we got:

(n+k+1)!/[n!(k+1)!]<[(n+k+1)^(n+k+1)]/{(n^n)[(k+1)^(k+1)]}

Done.

欢迎光临珍珠湾ART (http://zzwav.com/)