12q?q?1??1??n?1?(注意：q?q?1??q2?q?n?1) 211n?1??q?1??n?1??1??n?1???q?1??n?1??1??1．(由q?2) 222则B0中n?1个点的连线数l?b0?但若在这n?1个点内，没有任一点同时与其余两点连线，则这n?1个点内至多连线??n?1? 条，?2??故在B0中存在一点Ai，它与两点Aj、Ak(i,j,k互不相等，且i,j,k?1)连了线，于是A0,Aj,Ai,Ak连成四边形．
现设任一点连的线数?n?2．且设b0?q?2?n?2．且设图中没有四边形．于是当i?j时，
Bi与Bj没有公共的点对，即Bi?Bj?1 (0?i,j?n?1)．记B0?V\\B0，则由Bi?B0?1，
得Bi?B0?bi?1 (i?1,2,?,n?1)，且当1?i,j?n?1且i?j时，Bi?B0与Bj?B0无公共点对．从而B0中点对个数?n?1i?1??B?B中点对个数?．即
i0i?1n?1C2n?b0??C2Bi?B0??Ci?1n?12bi?11n?121?1?n?1???bi?3bi?2??????bi2i?12?n?1?i?1???3??b??2?n?1???? 2n?1i?1i??(由平均不等式) ?1?1?2??????2l?b?32l?b?2n?1 00??2?n?1??1?122?????????2l?b?3n?12l?b?2n?1 00?2?n?1???1?2l?b0?n?1??2l?b0?2n?2? (注意2l?q?q?1?2?2??n?1??q?1??2)，
2?n?1?2即得到Cn?b0?1??n?1?q?2?b0???n?1??q?1??2?b0? (两边同乘以2?n?1?)
2?n?1?即?n?b0??n?1?b0????n?1?q?2?b0???n?1??q?1??2?b0?．(注意到n?1?q?q?1?)
得q?q?1??n?b0??n?1?b0???nq?q?2?b0??nq?n?3?b0?．(各取部分因数比较)①
2又?nq?n?3?b0??q?n?1?b0???q?1?b0?n?3??q?1??q?2??n?3?q?q?1?n?0②（这里用到前面所得到的式子b0?q?2，q?q?1??q?q?n?1）
2??n?1?q?2?b0???q?1??n?b0??qb0?q?n?2?q?q?2??q?n?2?q2?q?n?2?1?0 ③（这里也用到前面所得到的式子b0?q?2，q?q?1??q?q?n?1）
2又?nq?n?3?b0?、?nq?q?2?b0?、q?n?1?b0?、?q?1??n?b0?均为正整数， 从而由②、③得，q?q?1??n?b0??n?1?b0???nq?q?2?b0??nq?n?3?b0?④ 由①、④矛盾，知原命题成立．
又证：画一个n?n表格，记题中n个点为A1,A2,?,An，若Ai与Aj连了线，则将表格中第i行
j列的方格中心涂红．于是表中共有2l个红点，当d?Ai??m时，则表格中的i行及i列各有m个红
点．且表格的主对角线上的方格中心都没有涂红．
由已知，表格中必有一行有q?2个红点．不妨设最后一行前q?2格为红点．其余格则不为红点(若有红点则更易证)，于是：
问题转化为：证明存在四个红点是一个边平行于格线的矩形顶点．
若否，则表格中任何四个红点其中心都不是一个边平行于格线的矩形顶点．于是，前n?1行的前q?2个方格中，每行至多有1个红点．去掉表格的第n行及前q?2列，则至多去掉
q?2?(n?1)?q?2?q2?q?(q?1)2?1个红点．于是在余下(n?1)(n?q?2)方格表中，至少有
2l?(q?1)2?1?q(q?1)2?2?(q?1)2?1?q3?q2?q个红点．
设此表格中第i行有mi(i?1,2,?,n?1)个红点，于是，同行的红点点对数的总和为
?Ci?1n?12mi．其
2222232中q?q?n?1．(由于当n?k时，Cn?Ck?Cn?1?Ck?1，故当红点总数为q?q?q个时，可
取q行每行取q个红点，q行每行取q?1个红点时
n?1i?12?Ci?1n?12mi取最小值，由下证可知红点数多于此数
时更有利于证明．)，但qC?qC22q2q?12??Cm． i由假设，不存在处在不同行的2个红点对，使此四点两两同列，所以，有(由于去掉了q?2列，
2故还余q?1列，不同的列对数为Cq2?1)
2即
?Ci?1n?12mi2222?Cq，所以q?q(q?1)?q(q?1)(q?2)??q?1??q?2?． 2?1即q(q?1)(q?q?2)??q?1??q?1?q?2
22??即q?q?2q?q?q?2q?2显然矛盾．故证．
2001*三、（本题满分50分） ) 将边长为正整数m，n的矩形划分成若干边长均为正整数的正方形．每个正方形的边均平行于矩形的相应边．试求这些正方形边长之和的最小值． ★解析：记所求最小值为f(m,n)， 我们可以证明f(m,n)?m?n?(m,n)．(*)
其中(m,n)表示m和n的最大公约数．事实上，不妨设m?n，
(1)关于m归纳，可以证明存在一合乎题意的分法，使所得正方形边长之和恰为m?n?(m,n)．
当m?1时,命题显然成立．
假设当m?k时，结论成立（k?1）．当m?k?1时，若
3232 D D1 C n A m A1 B ，由归纳n?k?1，则命题显然成立．若n?k?1，从矩形ABCD中切去正方形AA1D1D（如图）假设矩形A1BCD1有一种分法使得所得正方形边长之和恰为m?n?n?(m,n)?m?(m,n).于是
D 原矩形ABCD有一种分法使得所得正方形边长之和为m?n?(m,n)。
(2)关于m归纳可以证明(*)成立．
当m?1时,由于n?1，显然f(m,n)?1?m?n?(m,n)． 假设当m≤k时，对任意1≤n≤m有f (m，n)= m+n- (m，n)． 若m?k?1，当n?k?1时显然f(m,n)?k?1?m?n?(m,n))．
D1 C n A m A1 B 当1?n?k时，设矩形ABCD按要求分成了p个正方形，其边长分别为a1,a2,?,ap，不妨设
a1?a2???ap．显然a1?n或a1?n．
若a1?n，则在AD与BC之间的与AD平行的任一直线至少穿过二个分成的正方形（或其边界），于是a1?a2???ap不小于AB与CD之和．所以a1?a2???ap?2M?m?n?(m,n)．
若a1?n，则一个边长分别为m?n和n的矩形可按题目要求分成边长分别为a2,?,ap的正方
形，由归纳假设a2???ap?m?n?n?(m,n)?m?(m,n)。
从而a1?a2???ap?m?n?(m,n)． 于是当m?k?1时，f(m,n)?m?n?(m,n)． 再由(1)可知f(m,n)?m?n?(m,n)。
1997*三、（本题满分50分）在100?25的长方形表格中每一格填入一个非负实数，第i行第j列中填入的数为xi,j（i?1,2,?100，j?1,2,?25）如表1，然后将表1每列中的数按从小到大的次序从上到下重新排列为x1,j?x2,j???x100,j（j?1,2,?25）。如表2。求最小的自然数k，使得只要表1中填入的数满足
///?xj?125i,j/?1（i?1,2,?100），则当i?k时，在表2中就能保证?xi,j?1。
j?125★解析：在表1中，取x4i?3,i?x4i?2,i?x4i?1,i?x4i,i?0 (i?1,2,?,25)，其余各数均取于是，每列各数之和均等于1．但重新填入后，前96行之和均等于等于0．故k?97．
1，24
25?1．第97,98,99,100行之和24反之，如果表2中第97行的25个数涂黄， 98~100行共75个数涂红，则这些涂红的数在表1中至多分布在75行中，于是除这75行外的其余各行中的每个数都不小于同列中涂黄的数，即涂黄4个数的和≤没有涂红数的行的每一行数的和≤1．于是表2中第97行的数的和≤1，故第98,99,100行的数的和≤1．即能保证表2中第97~100行的数的和≤1．
∴k?97．
1996*四、（本题满分35分）有n（n?6）个人聚会，已知：
⑴每人至少同其中??个人互相认识；
2⑵对于其中任意??个人，或者其中有2人相识，或者余下的任中有2人相识。
2证明：这n个人中必有三人两两相识。 ★证明：
作一个图，用n个点表示这n个人，凡二人认识，则在表示此二人的点间连一条线．问题即，在题设条件下，存在以这n点中的某三点为顶点的三角形．设点a连线条数最多，在与a连线的所有点中点b连线最多，与a连线的点除b外的集合为A，与b连线的点除a外的集合为B．
1° 设n?2k，则每点至少连k条线， A,B中都至少有k?1个点． ⑴若存在一点c，与a,b都连线，则a,b,c满足要求；
⑵若没有任何两点与此二点都连线(图1)， 则由A?B??，A?B?2k?2，A?k?1
?n????n???B?k?1， 故得A?B?k?1，且图中每点都连k条线．若A (或B)中存在
AB两点，这两点间连了一条线，则此二点与a连出三角形，若A中任何两点间均未连线，B中任两点也未连线，则A??b?中不存在两点连线，B??a?中也不存在两点连线．与已知矛盾．
2° 设n?2k?1．则每点至少连k条线，A,B中都至少有k?1个点． ⑴若存在一点c，与a,b都连线，则a,b,c满足要求；
kΦk-12k+1个点a图2b⑵若没有任何两点与此二点都连线，且A?k，则由B?k?1时(图2)，则由A?B??，
A?B?2k?1，A?k，B?k?1， 故得A?B?2k?1，A?k，B?k?1，若A(或B)
中存在两点，这两点间连了一条线，则此二点与a连出三角形，若A中任何两点间均未连线，B中任两点也未连线，则A??b?中不存在两点连线，B??a?中也不存在两点连线．与已知矛盾．
⑶若没有任何两点与此二点都连线，且A?k?1，即每点都只连k条线．这
Ack2Bk-1k1Φk-1a2k+1个点图3b
1981-2024年全国高中数学联赛真题分类汇编含解析答案16组合与构造
