揭阳学校安全教育平台:求解一道数学竞赛题

来源:百度文库 编辑:查人人中国名人网 时间:2021/05/07 09:50:05
一群学生随机地站在一个5×5的方格中,每个小方格能且只能站一个人。试证明:在这个图中,一定有一个由小方格组成的矩形,它的四个角上小方格里站着的四个学生的性别相同。

pai314是个高手了.就是答案繁了一些,而且若要细究,也可以说有小的漏洞:
在最后一段,也可以说是很精彩的一段吧,提到"第2排可以放3人",但事实上第二行却未必要放3人,这些情况就相当于没有讨论了,在一般的考试是可以放的,但若在数学竞赛中,扣分是难免的了.

因此,我还是给出一个新的答案吧:

用反证法,反设存在一种站法,使得不存在四个角小方格上人性别相同的矩形(称为好矩形).

选择人数多的性别,设有n人,另一个性别m人,m<n.为简单,后面人数就代表所选性别中的人数.
考虑所有行和列的人数,选取人数最多的行或列,由于行列对称,不妨设第i行人数最多,有k人.我们依此把正方形分为2个区域A和B如下:
A:这k个人所在的k列.
B:其余5-k列,如果k=5,就没有这个区域了.
我们说,A中的人数不超过k+4.
否则除了站满了k个人的那行之外,其余4行在A中至少有5人,就存在另一行(第j行)至少2人(分别在第x列和y列),考虑i,j行,和x,y列,显然构成一个好矩形,与假设矛盾.
另外,B中的人事实上是分布在其中4行的,因为第i行人数是最多的,其所有人都在A中,因此B中第i行没有人.
这样,
k=5: 则B中0人,n <= k+4 = 9
k=4: 则B中只有一列,不超过4人,n <= (k+4) + 4 <= 12
k=3: 依前B中有2列,并且分布在4行,如果其中有2行都有2个人,则这2行2列就构成好矩形,因此B中至多1行有2个人,因此B中至多5人, n <= (k+4) + 5 <= 12
k<=2: n <= k * 5 <= 10
综上,n<=12.

总人数 25 = n + m < n + n <= 24矛盾
反设不成立,任何一种站法都存在一个好矩形.
证毕.

由抽屉原理可以知道,一定有个性别人数有13人或者更多.
把25个方格按照每一横排5个方格,算做1个抽屉。就是有5个抽屉了。假设性别人数多的有13个人(性别最均匀的情况)。放进这5个抽屉里,由抽屉原理知道,一定有个抽屉(也就是一个横排)有3个或者更多.
这里就要分情况讨论了:
1。有个横排有5个人。(黑点代表人)
●●●●●
●○○○○
---------
可以知道,接下来的横排每排只能 有1个人。每个横排之间只能有1个人的竖列位置是相同的!有2个位置相同就组成题目中的小矩形了。这样最多可以放5+4*1=9人<13人。则论题成立.
2。有个横排有4个人
○●●●●
●●○○○
●○●○○
●○○●○
●○○○●
同上,接下来每个横排最多有2人。一人对应第1排的无人位置,1人对应1个有人位置。最多人数=4+4*2=12<13人。论题成立。
3。有个横排有3人。
●●○●○
○●●○●
○○●●○
○○○●●
●○○○●
每个横排之间只能有1个人的竖列位置是相同的.有2个位置相同就组成题目中的小矩形了。第2排可以放3人,1人对应第1排的一个有人位置,其他2人对应无人位置。但不能有3排都有3个人.不然:3*3-5=4,有4个位置有人重叠对应。只有3排,由抽屉原理知道,一定有1排有2个位置有人重叠对应,就出现论题中的矩形了。所以接下来3排都最多2个人。最多人数=3+3+3*2=12人<13人。论题成立了.