＋设为首页 ＋添加到收藏夹
少林寺有72绝技，有一天，方丈想把这些绝技传给他的弟子们。和尚们并不关心能学多少种绝技，而只关心自己所学的几项绝技是不是有人全部掌握。因为任何一种绝技只要练好了都能立于不败之地。比如和尚A会第项绝技，而B会第项绝技，A并不会感到师傅不公，因为他有一项绝技1，B不会。假设方丈大师会n项绝技，请你帮他算一算，在满足上面条件的情况下，他最多能传授几个弟子？
忘记组合怎么算了~
大概是
n/2
C
n
To jettylee
怎么证啊？
introductory combinatorics上面有详细证明！
发信人: starfish (好好学习，天天向上), 信区: Algorithm
标 题: [合集]请教starfish一道离散题
发信站: 南京大学小百合站 (Fri Jun 20 13:13:42 2003)
globus (Every Jack has his Jill.) 于Fri Jun 13 19:16:44 2003)
提到：
A是X＝的一族子集构成的集合，其中的元素互不包含
证明 A的元素个数最大为Cn
starfish (好好学习，天天向上) 于Fri Jun 13 19:19:26 2003)
提到：
Cn表示什么啊？组合数？
globus (Every Jack has his Jill.) 于Fri Jun 13 19:22:36 2003)
提到：
是啊
就是选择嘛
cornucopia (仰视星辰) 于Fri Jun 13 20:40:14 2003)
提到：
取元素的方法必须就是Cn
但证明其他方法没他多。。。。
没想好呢，呵呵
globus (Every Jack has his Jill.) 于Fri Jun 13 22:09:38 2003)
提到：
这个凭常理判断
显然是每个元素都是一个包含n/2个数的集合的时候这样的元素最多
但是怎么证明呢？
starfish (好好学习，天天向上) 于Fri Jun 13 22:23:38 2003)
提到：
显然阿，
关键就在于证明当A中的每个元素势都相等的时候A中元素数目可以达到最多，
不过我也还没想到如何证明：$
sunder (爱情不老) 于Sat Jun 14 00:48:55 2003)
提到：
这样的集合称为杂置。
原题为Sperner定理：
令X为n个元素的集合。则X的杂置最多含有nC[n/2]个元素。
下面的证明来自Richard A. Brualdi的“Introductory Combinatorics”第三版
国内有机械工业出版社出版的翻译版《组合数学》。
证明可使用归纳法，证明下面的更强的结论：
X的所有2^n个组合的集合可以被划分成nC[n/2]部分，使得任意杂置最多含有每一部分中的
一个组合。
此划分称为链划分
n=1时有1条
空集<{1}
n=2时有2条
空集<{1}<{1,2}
{2}
n=3时有3条
空集<{1}<{1,2}<{1,2,3}
{2}<{2,3}
{3}<{1,3}
通过对n=3所示的链划分得出对于n=4的组合的链划分如下
取多于一个组合的每一个链，做成n=4的两条链：
其一是通过把4加到原链的最后一个组合中得到一个新的组合，再将这个组合加到该链的最
后形成一条新链，另一个则是通过把4添加到原链除最后一个组合外的所有组合中得到。
链 " 空集<{1}<{1,2}<{1,2,3} "
变成 " 空集<{1}<{1,2}<{1,2,3}<{1,2,3,4} " 和 " {4}<{1,4}<{1,2,4} "
链 " {2}<{2,3} "
变成 " {2}<{2,3}<{2,3,4} " 和 " {2,4} "
链 " {3}<{1,3} "
变成 " {3}<{1,3}<{1,3,4} " 和 " {3,4} "
这样得到n=4的组合的6=4C2个链的一个链划分。在n=4的这个划分中，这些链有两个特殊的
性质。链中的每个组合都比它在链中的前趋组合多一个元素。链中
的第一个组合的大小加上该链的最后一个组合的大小是n=4. 类似性质对于n=1,2和3时的链
划分也是成立的。集合{1，2，。。。，}的组合的链划分如果
1) 链中的每个组合都比他在链中的前趋组合多一个元素；并且
2)链中的第一个组合的大小加上该链的最后一个组合的大小是n
则该链划分就是 对称的链划分。在对称链划分中的每一个链都恰好含有一个|_n/2_|组合
，因此对该对称链划分中链的个数是为
nC[n/2](下取整)=nC[n/2](上取整)
正如上面对于n=3所述的那样，对于|1,2,...,n|的对称的链分解可以从{1,2,...n-1}的对
称的链分解归纳得到。
在{1,2,...n-1}的对称的链划分中，取任一个链
A1<A2<...<Ak，其中|A1|+|Ak|=n-1
并按照k=1还是k>1得到 {1,2,...,n}的一个或是两个链：
A1<A2<...<Ak<Ak+{n}，其中|A1|+|Ak+{n}|=n
和
A1+{n}<...<Ak-1+{n}，其中|A1+{n}|+|Ak-1+{n}|=n(如果k=1，则此链不出现)。
{1，2，...,n}的每一个组合恰好出现在用这种方法构造的一个链中，因此链的最后结果的
集合形成对于{1,2,...,n}的一个对称的链划分。
在{1,2,...,n}的对称的链划分中链的个数是
nC[n/2]
因此，在{1,2,...,n}的杂置中的组合的个数最多等于
nC[n/2]
如果n是偶数，可以证明，只有S的所有的n/2组合的杂置才是大小为 nC(n/2) 的杂置。
如果n是奇数，只有S的所有的(n-1)/2组合的杂置和所有的(n+1)/2组合的杂置才是那些这
样大小的杂置。
today (俺家丢了只小狗) 于Sat Jun 14 00:55:06 2003)
提到：
声明！！！：
这么长是一下一下打上去的，sunder打的太慢了，
所以后半部是我负责的。
害得我少灌了一会儿水，在这里灌一篇补偿一下。
ihappy (听故事) 于Sat Jun 14 00:59:46 2003)
提到：
这个翻译真是太糟糕了,看得难受死了
http://www.cut-the-knot.com/pigeonhole/sperner.shtml
这是一个英文的证明,很好懂的
btw,这个定理曾经作为某年高中数学联赛的题目
today (俺家丢了只小狗) 于Sat Jun 14 01:00:13 2003)
提到：
是啊，sunder也说翻译是很糟糕。
starfish (好好学习，天天向上) 于Sat Jun 14 01:02:30 2003)
提到：
完了
高中题目我都做不出来了，5555~~~~
ihappy (听故事) 于Sat Jun 14 01:05:20 2003)
提到：
hehe,没关系,当年我参加高中联赛的时候也没有做出来.
这种couting的题目想不到路子上怎么也做不出来的
today (俺家丢了只小狗) 于Sat Jun 14 01:06:58 2003)
提到：
ihappy你这就不对了，
你那时候是高中，他是研究生内，
而且你做不出来并不代表别人也应该做不出来呢。
starfish (好好学习，天天向上) 于Sat Jun 14 01:09:58 2003)
提到：
谢谢你的安慰
另外那个网站很不错
有不少好玩的东西：）
starfish (好好学习，天天向上) 于Sat Jun 14 01:10:29 2003)
提到：
FT~
再一次打击我~~
哐当
ihappy (听故事) 于Sat Jun 14 01:17:11 2003)
提到：
ft,你没有听说过这种竞赛题高中生能做出来,很多数学家却不行吗?
today分明是在挑拨离间,不要理她,呵呵.
today,kkkickkk, 现在给你一个将功赎罪的机会,到数学版去给我那个题目想一个
小学生能理解的解法.
sunder (爱情不老) 于Sat Jun 14 01:18:38 2003)
提到：
不仅糟糕
还有错误
borntolose (天生是输家) 于Sat Jun 14 05:54:14 2003)
提到：
人本来是越年轻越聪明。就像桃谷六仙说的，高中生比数学家聪明，三岁小孩比高中生聪
明，两岁小孩又比三岁小孩更聪明，......没出娘胎之前最聪明。：=）
globus (Every Jack has his Jill.) 于Sat Jun 14 10:08:20 2003)
提到：
哈哈
谢谢以上各位
cjs (BlueSky) 于Sat Jun 14 18:21:47 2003)
提到：
显然，计算机方面还是年轻人的天下。
today (俺家丢了只小狗) 于Sat Jun 14 22:09:28 2003)
提到：
倒~~~可是你不会做的也并不说明我能够做出来呀~~~
收藏一下
应该不会超过1000个吧？
数学归纳法：
当N=2时：C(1,2)=2;//收两个
当N=3时：C(2,3)=C(1,3); //C(2,3)表示每人教两门，C(1,3)表示每人教1门
当N=4时：C(1,4)=C(3,4)=4; C(2,4)=6;//取C(2,4) //每人教两门；
当N=4时：C(1,5)=C(4,5)=5; C(2,5)=C(3,5)=10;//取C(2,4) //每人教两门；
可以证明：C([n/2],n)是N的所以组合数中最大的，所以最后结果应该是C([n/2],n)
证明如下：
设R=Max(C(k,n)); (k<n);这个假设应该没有问题：-）
我们来看看 C(k,n)的最大值，展看C(k,n)=n*(n-1)*(n-2)......*(n-k+1)/k!=
n*(n-1)*(n-2)......*(n-k+1)/k*(k-1)*(k-2)......*1;这个没有问题吧：-）
展开式n*(n-1)*(n-2)......*(n-k+1)中共有K个乘法项，k！也是K个乘法项，所以
C(k,n)=n*(n-1)*(n-2)......*(n-k+1)/k*(k-1)*(k-2)......*1；
分子，分母都乘(n-k)!,得到C(k,n)=n*(n-1)*(n-2)......*(n-k+1)*(n-k)!/k*(k-1)*(k-2)......*1*(n-k)! ;分子等于n!,分母等于k!*(n-k)!；
R最大，就是求k!*(n-k)!最小，就是在k!*(n-k)!最小时，k的取值就表示每个徒弟教k门时，收的徒弟最多！
楼上要首先证明，互不包含的子集数的最大值是C。
大体步骤：
首先猜测结果为 C
明显有如下结论：
对 i<j, Si 里的每一个元素 必然 被包含于 Sj 里的一个或多个元素。********(结论1)
从 S1 的所有子集开始，如果 Sk 的元素被包含于 Sk+1 的某个元素，则以被包含的那个 Sk 的元素为起点画一有向边指向包含它的那个Sk+1里的元素，显然这是个层次结构很明显的图形。
A->B,将Ａ叫做Ｂ前驱，的Ｂ叫做Ａ的后继。
某一层的结点数最多的是 C([n/2],n)。
对于某个非空的子集，它对应于该图形的某个节点。
~~~~~~~~~~~映射证明~~~~~~~~~~~
对于多个互不包含的子集，则一定可以将层数 k != n/2 的那些结点映射到 第 n/2 层里去，并且保持它们互不包含性质不变。
因为对于 k<n/2 的层的任何结点，它们必然 被包含于 n/2层 的某些结点里(根据结论1）。
本身在第 n/2 层的的节点必不在这些节点当中，不然就违反了互不包含的前提；
这些结点也不存在到 >n/2 层 的那些结点的路径，否则根据传递关系，也违反前提。
而在这些节点当中，必然可以选出跟 层数<n/2 的节点一一对应并互不相同的的节点。方法是从最小的层数开始，向 n/2 方向逐层选出替代结点。
比如最小的层数k上 有个结点,则该结点在 k+1 层有多个后继，可以选择其中一个，并且：
这跟本身在k+1层的的结点不会相同，否则违反互不包含前提；
对于同是第k层的结点的，也可以做到不造成冲突。因为 到达 n/2 之前，每个节点的后继都 >1 个，对于 第 k 层互不相同的 x 个结点，它们共有 >x 个不同后继，画个图规范描叙就很简单地知道如何选择，这些看起来简单叙述麻烦的东西最吃力不讨好了，免去。 ：
呕吐，居然做了吃力不讨好的事情……ＴＴ
经过计算为4.72236648286965E+21
-------------------------------------------------------------------------------------
创建日期： 2004-01-13
更新日期： 2004-09-14
创 建 者： gyhyq
功能说明： 求解
少林寺有72绝技，有一天，方丈想把这些绝技传给他的弟子们。
和尚们并不关心能学多少种绝技，而只关心自己所学的几项绝技
是不是有人全部掌握?因为任何一种绝技只要练好了都能立于不败
之地。比如和尚A会第项绝技，而B会第项
绝技，A并不会感到师傅不公，因为他有一项绝技1，B不会。假设方丈
大师会n项绝技，请你帮他算一算，在满足上面条件的情况下，他最多能传授几个弟子？
-------------------------------------------------------------------------------------
Private Sub Command1_Click()
Dim intRs As Double
计算
intRs = ComputResult
Text1.Text = intRs
End Sub
功能：求解
输入：无
返回：结果
Private Function ComputResult() As Double
Dim dblSum As Double
Dim intN As Integer 绝技个数
72绝技
intN = 72
For i = 1 To intN
dblSum=dblSum+计算C(n,m)
dblSum = dblSum + ComputC(intN, i)
Next
ComputResult = dblSum
End Function
功能：计算n!/(m!(n-m)!)
输入：intN--N,intM--M
返回：结果
Private Function ComputC(ByVal intN As Integer, ByVal intM As Integer) As Double
Dim intNJc() As Integer n!
Dim intMJc() As Integer m!
Dim intNMJc() As Integer (n-m)!
Dim intFM() As Integer (m!(n-m)!)
取N!数组
intNJc = IntToStr(intN)
取M!数组
intMJc = IntToStr(intM)
取(N-M)!数组
intNMJc = IntToStr(intN - intM)
计算(M!(N-M)!)
intFM = StrAndStr(intMJc, intNMJc)
计算N!/(M!(N-M)!)
ComputC = StrDevStr(intNJc, intFM)
End Function
功能：将阶乘放入数组
输入：intNum-阶乘数字
返回：阶乘数组
Private Function IntToStr(ByVal intNum As Integer) As Integer()
Dim intVal() As Integer
如果为0则赋值1
If intNum = 0 Then
定义数组大小
ReDim intVal(0)
intVal(0) = 1
返回
IntToStr = intVal
Exit Function
End If
定义数组大小
ReDim intVal(intNum - 1)
For i = 0 To intNum - 1
数组[i]=i
intVal(i) = i + 1
Next
返回
IntToStr = intVal
End Function
功能：将两个阶乘数组相加
输入：strA()--第一个数组,strB()--第二个数组
返回：合并后的阶乘数组
Private Function StrAndStr(strA() As Integer, strB() As Integer) As Integer()
Dim strCount As Integer
Dim strAB() As Integer 合并后的数组
Dim intLenA As Integer
Dim intLenB As Integer
intLenA = UBound(strA) + 1
intLenB = UBound(strB) + 1
取合并后的长度
strCount = intLenA + intLenB - 1
定义合并后的数组长度
ReDim strAB(strCount)
将第一个数组放入
For i = 0 To intLenA - 1
strAB(i) = strA(i)
Next
将第二个数组放入
For i = 0 To intLenB - 1
strAB(i + intLenA) = strB(i)
Next
返回
StrAndStr = strAB
End Function
功能：计算N!/(M!(N-M)!)
输入：strA()--分子数组,strB()--分母数组
返回：结果
Private Function StrDevStr(intA() As Integer, intB() As Integer) As Double
Dim dblAJc As Double
Dim dblBJc As Double
取intA(i)中的数字
For i = 0 To UBound(intA)
取intB(j)中的数字
For j = 0 To UBound(intB)
if intA(i)中的数字等于intB(j)中的数字
If intA(i) = intB(j) Then
则intA(i)与intB(j)中的数字为1
intA(i) = 1
intB(j) = 1
Exit For
End If
Next
Next
取intA中的积
dblAJc = StrAmass(intA)
取intB中的积
dblBJc = StrAmass(intB)
返回intA积/intB积
StrDevStr = dblAJc / dblBJc
End Function
功能：求数组的积
输入：intNum()--数组源
返回：结果
Private Function StrAmass(intNum() As Integer) As Double
Dim dblSum As Double
dblSum = 1
求积
For i = 0 To UBound(intNum)
dblSum = dblSum * intNum(i)
Next
StrAmass = dblSum
End Function
我喜欢这个ｖｂ的算法，呵呵
很少有人用ｖｂ回答问题的
commandbutton1.click!!^^
