解题小品——归本溯源

《解题小品——归本溯源》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2010年第4期解题小品——归本溯源陶平生(江西科技师范学院数学与计算机科学系，330013)中图分类号：0157．6文献标识码：A文章编号：1005—6416(2010)04—0011一O5例1由n个点和这些点之间的Z条线两条边具有公共端点(设为U2U，、'U2V)．于是，段组成一个空间图形，其中，=q+q+1，得到四边形UI4V23．1(iii)若dl=4，设1与V2、3、4、5每点z≥÷g(q+1)+1(g≥2，q∈N)．已知此图二都邻接，而V、V与。不邻接．若、中有中任四点不共面，每点至少有一条连线段，存一点向、、z，、发出了两条边，则图中存在一点至少

2、有q+2条连线段．证明：图中必在四边形；若6、7每点至多向2、3、4、5存在一个空间四边形(即由四点A、B、C、D发出一条边，则V、V、、之间至少连了三和四条连线段AB、BC、CD、DA组成的图形)．条边，其中，必有两条边具有公共端点，故存(2003，全国高中数学联赛)在四边形．对于这道试题，除了命题组提供的解答因此，q=2时结论成立．外，尚未见到其他的解法．本文给出一个纯图(2)当9≥3时，构作图G的邻接矩阵论方法，虽然有点繁琐，但仍可作为用邻接矩A=()，其中，若与vj相邻，则=l；阵方法解题的一个范例．若与vj不相邻，则=0．证明设个点的集为V={，，⋯

3、，显然，主对角线上的元素全为0(因简V}．如果两点之间连有线段，则令其相邻．于单图无环)，并且=，=，即A为对称是，得阶简单图G．方阵．记A=(a)⋯，其中，用d表示点的度数，d=d()(i=l，2，⋯，n)，且设d=max{d，d2，⋯，d}．则aq==2一5酊(i、．，∈{f1上，2z，⋯，})，．·g+2≤d1≤n一1．于是，所证结论转化为：(1)当q=2时，有=7，Z≥10，4≤≤6。存在、_『∈{1，2，⋯，}，i，使(i)若d=6，设V，与V：，，，⋯，每点口≥2．①都邻接，则在，，⋯，这六点之间至少还(这是由于血i的每个加项只取0、1两个有四条边

4、，其中，必有两条边具有公共端点(设为U2U3、U2I)4)．于是，得到四边形V1'／3423．值，若aij>12，则∑中至少有两个加项(ii)若d1=5，设V1与V2，V3，⋯，V6每点为1．设=1．于是，都邻接，而与V不邻接．若dI>2，设V与：、mmf=1=：1，=1，m=1，，=13邻接，则存在四边形1V2V73；若d7≤1，则舒z与、与vj、t，与与vj分别V，，⋯，V之间至少有四条边，其中，必有相邻收稿日期：2009—06—05岱为四边形．)12中等数学F两用反证法证明．接下来用反法证明d≤3口一1．若图G中无四边形，即对任意的i、假设d≥3q，因每

5、个d≥1，所以，据式(i#j)有≤1．④知，n个正整数d。，d，⋯，d的和为定值，且其平均值大于g而小于g+1．因此，当它又(、i％卜∑22∑=∑=aij,=1i=li(≠们尽量接近平均值时，其平方和取得最小值．则口：(骞Nkr)一(骞2)于是，为使∑d达到最小，由调整法，可取=∑d一∑(∑％)=∑d一∑d．②d。=3q，其余一1个数d：，d3，⋯，d中，设有个取g，T／,一1一个取q+1．式②用到了h2=h．由3g+g+(n一1一)(g+1)据条件，d≥1，故Y_2d一∑d=Y_2d(一1)=∑d=(g+1)(n一1)+2，k=l解得=3q一2．对每个d单调

6、递增(当其他d暂时固定)，因此，式②右端的最小值应在∑d最小时故∑≥(3g)+(3g一2)q+取得．此时，∑d=21=口(g+1)+2．[一1一(3g一2)](q+1)=(3q+7)9+(g一2g+2)(q+1)据反证法所设，0≤1(≠)，则∑口≤q+3q+6q。+2q+2．一n(因为n×凡矩阵A总共有n个元素，注意到主对角线上12个元素不计算在内，其余每个n一n=(g+9+1)(9+g)元素小于或等于1)．q+2q+2g+9．由式②得于是，由式③得，z一n≥∑d一∑d，③q+2q。+2q+g≥∑d一∑d其中，∑d=g(g+1)+2≥(g+3q+6q+2q+2

7、)一[q(q+1)+2]q+2q+4q+g，：n(q+1)一q+1．④即0≥2g，矛盾．所以，g+2≤d1≤3g一1．再进一步估计∑d的最小值．不妨设与邻接的d个点是：，，，⋯，设诸d中d最大．据条件有d。≥g+2．dl十1．则l11⋯10⋯0023X24⋯X2(dl+】)X32034⋯X3(d1+1)A=(1+1)2X(dl+1)3X(d1+1)4⋯0x(a1+2)2x(dl+2)42010年第4期13对于任意点(≥2)，其度数为d，于g+1．是，在点1，2，⋯，，+一，中恰有d由(q+1)n—q+l=∑d个点与邻接．因此，矩阵A的第行恰有d个1，第i列也恰

8、有d个1，但是加框的矩形=(g+2)+