排列与组合之小明班级共有多少人_小升初-查字典小升初
 
请输入您要查询的关键词

排列与组合之小明班级共有多少人

2011-05-12 19:14:22     标签:小升初教育新闻

问题:小明所在的班级要选出4名中队长,要求每位同学在选票上写上名字,也可以写自己的名字。 结果全班的每位同学都在自己的选票上写了4个互不相同的名字。当小明把同学们的选票收集后发现一个有趣的现象:就是任意取出2张选票,一定有且只有一个人的名字同时出现在2张选票上。 请问:小明所在的班级共有多少人?

总体逻辑思路:首先,假设题目所说的情况存在。然后,得出班级人数。最后,构造出一个例子,说明确实存在这种情况。

我们先来证明这个班每个人都恰好都被选了4次。

思路简介:我们首先用反证法证明没有人被选了4次以上。由于平均每人被选了4次,既然没有人被选了4次以上,肯定也不存在被选了4次以下的人。所以,可以得到每个人恰好被选了4次。

首先证明没有人被选了4次以上,我们用反证法。

假设有一个人被选了4次以上(由于很容易证明这个班的人数肯定不少于7人,所以我们可以假设有一个人被选了4次以上),我们设这个人为A同学。接下来我们来证明这种情况不存在。

把所有选择A同学的选票集中到一起,有5张或5张以上。方便起见,我们把这些选票编号,记为A1选票,A2选票,A3选票,A4选票,A5选票,…。意思就是选择A同学的第1张选票,选择A同学的第2张选票,…。

这些选票都选择了A同学。由于任意2张选票有且只有1个人相同,所以这些选票上除了A同学外,其他都是不同的人。

我们还可以证明,这些并不是全部的选票,不是太难,就不证明了。

既然这些(所有选A同学的选票)不是全部的选票,我们再拿一张没有选择A同学的选票。方便起见,称之为B选票。

根据任意2张选票有且只有1个人相同,A1选票上必有一个人和B选票上的一个人是相同的,而且这个人不是A同学。

同样道理,第A2、A3、A4、A5、…上也必有一个人和B选票上的一个人是相同的,而且这个人不是A同学。

由于B选票上只有4个不同的人,而A1、A2、…,的数量大于4.所以,A1、A2、A3、…选票中至少有2张选票,除了A同学外还有一个共同的候选人。根据任意2张选票有且只有1个人相同,我们知道这是不可以的。

所以,没有人被选了4次以上。

由于平均每人被选4次,既然没有人被选4次以上,当然也就不可能有人被选4次以下。

所以,每个人恰好被选了4次!

-----------------------

证明了每个人都恰好被选了4次后,下面我们用两种方法来求出班级的人数。

方法一:解方程设这一班有n个人,从n张选票里面任选2张有C(n,2)=n(n-1)/2种情况。

由于任意2张选票都有且只有1个人相同,所以每一种情况都代表了一种2张选票重复选择了同一个人的情况。(这句话不太好理解,暂时没有想到好的表述)

每一个人都被选了4次,则2张选票重复选择了同一个人的情况又等于nC(4,2)=6n

所以n(n-1)/2=6n解得n=13.

方法二:分析论证,计算我们从所有选票中拿出一张,这张选票上有四个人,方便起见记为甲、乙、丙、丁四个人。

除了我们拿出的这张选票外,所有选甲的选票组成集合[甲].所有选乙的选票组成集合[乙].所有选丙的选票组成集合[丙].所有选丁的选票组成集合[丁].

由于每个人都恰好被选了4次,所以[甲]、[乙]、[丙]、[丁]四个集合中都有3个元素。而且这四个集合没有交集。

每个集合有3张选票,再加上我们拿出的这张选票,一共有4×3+1=13张选票,即13个人。

下面我们证明选票数不能多于13张。还是用反证法。

假设选票数多于13张,我们从中取14张。从这14张选票中我们拿出一张称为C选票。除了C选票外还有13张选票,C选票上有4个不同的人,这13张选票中的每一张都有一个人和C选票上的一个人是相同的。这样13张选票中至少有4张选择了C选票上的同一个人,这样再加上C选票,就有5个人选择了同一个人。

根据前面的结论,没有人被选了4次以上,所以选票数不能多于13张。而且只能是13张。

所以只有13张选票,即只有13个人。

--------------

下面说明这种情况确实存在。

给出一种投票结果即可。

(1,2,3,4)

(1,5,6,7)

(1,8,9,10)

(1,11,12,13)

(2,5,8,11)

(2,6,9,12)

(2,7,10,13)

(3,5,9,13)

(3,6,10,11)

(3,7,8,12)

(4,5,10,12)

(4,6,8,13)

(4,7,9,11)

----------------

方法三:网上搜到得一种方法,设班级有x个人,那么x张票中总共有4x(有重复)个名字,也就是说班级里每个人的名字平均出现4次,(1) 如果有一个人的名字在所有票中都出现,那么x张票应该有不重复的名字3x+1个,这与班级有x个人矛盾,(2)如果一个人的名字在5张票中都出现过,那么假设为(1,2,3,4)(1,5,6,7)(1,8,9,10)(1,11,12,13)(1,14,15,16)那么你无法构造一个不包含1,但与前面5张票都有一个同名的票,所以一个人的名字在所有票中最多出现4次,并且每个人的名字在所有票中平均出现4次,那也就是说每个人的名字在所有票中出现4次假设包含1的票为(1,2,3,4)(1,5,6,7)(1,8,9,10)(1,11,12,13)其中2出现了1次,之后构造其他包含名字2的3张票为(2,5,8,11)(2,6,9,12)(2,7,10,13)

之后构造分别包含名字3,4的各3张票。发现符合题意,所以这个班有13人。

查看全部
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关文章
猜你喜欢