《训练题b解答.doc0321112247706》由会员分享,可在线阅读,更多相关《训练题b解答.doc0321112247706(11页珍藏版)》请在金锄头文库上搜索。
1、1训练题 B 解答 (陶平生)、将数列处于平方位置的项所构成的子数列,称为数列1 nx2149,kx x xxLL的“平方子列” ,今从正整数数列中,删去其平方子列,在剩下的项所构成 nx1,2,3,L的数列中,再次删去其平方子列,如此继续第次删去的平方子列中的第2,3,5,6,7,8,10,Lm项记为n,f m n、求的表达式; 1,f m n、求正整数,使 2,m n,2012f m n 解:、我们将探求的过程分三步进行: 1,f m n、试验:对前个数进行所述的操作,顺次得到七个平方子列,即有序组 0116,排列如表一:(1,4,9,16)(2,6,12)(3,8,15)(5,11)(7
2、,14)(10)(13)(表一) (表二) (表三)在表一中,从每行或每列看,不易发现其规律,但是如果将数与用斜线连结,1316 且从其它每个数所在位置都作该斜线的平行线,立即可以看出,数表有特征:从左到右,顺次将每条斜线上的数自下而上读出,恰好就是数按自然顺序的排列;1,2,16L、构造:依照上述斜线规则,易将数表续填下去,使得每个正整数都出现于表中,0(2 )具体填法如表二,表三 (表三的制作方法是:在一根水平线上,等距地取一列点,过每个点作铅垂射线,过每个点,以及每相邻两点的12,nAAALLiAikiA1iiA Al1l2 l3 l4l5 l6l7 l8 l9 k1k2k3k4k512
3、34567891011121314151616151413121110987654321A1A2A3A4A52中点,作一簇平行的斜线,自左至右顺次记为,在与每条的交点处填数).123, , ,l l l Liljk一般说来,若最上方填,则因下一条斜线与射线都相交,共21ml2m2ml12,mk kkL得个交点,于是在上应填个数,自下而上第一数为,最上方一数为m2mlm21m ,而其第个数为, 2mmn2mn(1)nm又因斜线与射线相交,有个交点,则在上应填个数,21ml121,mk kkL1m21ml1m自下而上第一数为,最上方一数为,而其第个数21mm 2211mmmmn为, 2mmn(11
4、)nm因此,在点处(即表中第一行) ,所填的数顺次为,123,kA AAALL221 ,2 ,L,将合并得,第根斜线上的第个数为:2kkkln, (其中,)24kn112kn1,2,3,k L现将表二中第行第个数记为,则是第根斜线上的第一数,是第mn,m na,1mamml,2ma根斜线上的第二数,是第根斜线上的第个数 2m2ml,m na21mn21mnln,由得 2,22 4m nmnan 、下面证明,即要证,表二的第行就是数列的第0(3 ),m nf m nam1,2,3,L个平方子列m为此,称正整数序列为“数列” ;1,2,3,L1N对用数学归纳法,时,由填数方法知,在表二的第一行所填
5、的数顺次为m1m ,故是数列的第一个平方子列;22221 ,2 ,3 ,kLL1N假设表二的前行分别是数列的前个平方子列,则当从表中删去前1m1N1m行后,剩下的数如按从小到大的顺序排列,恰好就是从数列中删去前个平1m1N1m方子列后剩下的数组成的数列(称为数列) mN按定义,数列是数列的平方子列,即,1 ,2 ,f mf mf m nLLmN3是数列中自小到大的第个数,f m nmN2n而在表二中删去前行后,不超过的数,全部含于由表中第行,第一列及第1m,m nam根斜线所围成的三角形区域中,而在此区域中,第列有 个数,第列21mmn11n有个数,第 列有个数,共计有个数,且位于该3121n
6、21 3(21)nn L,m na区域最后一根斜线上方,故是区域中的最大数,从而由得,是数列中从小到大,m namN的第个数,因此,2n,m nf m na故由数学归纳法得,表二的第行,即是数列的第个平方子列() ,m1Nm1,2,n L由得,222,4mnf m nn 、由于,故位于表二第根()斜线上, 2224444201245201289892 45 1且是该斜线自下而上的第个数() ,所以,由322322012444432n 又有,则,因此2189mn27m 27,322012f、一次体育比赛共设有个项目,每个选手恰好报名参加其中的两个项目,22 2nn 而任两个人都至多有一个相同的项
7、目,假定对于每个,不超过人报名1,2,1knLk的项目少于个.k 证明:存在个选手,使得每个项目都恰好有其中的两人参加.2n 证:用个点表示这个项目,若其中某两个项目被同一人选报,则令相应的两点2n2n 相邻(即一条边表示一个选手) ,于是得到阶简单图,且图满足“性质”:2nGGP,度数的顶点至多个.1,2,1kn Lk1k 只要证,图含有哈密顿圈(经过图每个顶点的圈) ,即为哈密顿图.GGG 反证法,若图中不含哈密顿圈,则集合G是具有性质的阶非哈密顿图不是空集,从而中有极大元(边数 G GP2n0G最多的) ,于是:、因为非哈密顿图,故其中必有不相邻的顶点,而对于任一对不相邻顶点,0(1 )
8、0G, u v由的极大性,添加边后所得的图便成为哈密顿图,即图中有一个含有边的0Guv1G1Guv哈密顿圈,于是在中有一条以、为起、终点的哈密顿路:0Guv4(其中).1 22nv vvL12,nuv vv、对于中任一对不相邻顶点,度数中至少有一个.0(2 )0G, u v , d ud v1n事实上,因顶点不相邻,据知,中有一条以、为起终点的哈密顿路:, u v 10Guv(其中) ,假若,若,与(即1 22nv vvL12,nuv vv , d un d vn d urnu)相邻的个顶点记为,则对于每个1vr 12, rkkkvvvL1222rkkknL,顶点都不与(即)相邻,否则在中就有
9、哈密顿圈:1,2,jrL1jkv2nvv0G,这与的选择矛盾.1 21 2211jjknnkv vvv vv vLL0G所以 ,而这又与的假设矛盾. 21211d vnrnnn d vn、据知,中必有度数的顶点,即集合0(3 )0(2 )0G1n不是空集,设是集中度数最大的一个点, ,1v vV Gd vn 1v记,据性质知,集中至多有个点,从而 1max1d vmd v vn P2n在中至少有个点的度数皆,于是在这个点中必有一个不与相邻的点0G2nn2n1v(因为与相邻的点只有个,而) ,设该顶点为, (于是).1vm1mn2nv2nd vn既然与不相邻,据的极大性,有一条经过所有顶点的哈密
10、顿路:1v2nv0G0G,在这条哈密顿路上,与相邻的个点记为,1 22nv vvL1vm 12, mkkkvvvL. 据的证法知,对每个都不与1222mkkknL 211,2, , jkjm vL相邻,而据性质中的情形知,在这个点中,至少2nvP1kmn 12111, mkkkvvvLm有一个点的度数(因,据性质,度数的顶点至多个) ,设1m1mnPm1m是这样一个点,即,又由的定义(是集中所有点的最大度数,1tkv11 tkd vmmm而集中含有中度数的所有点) ,既然,故该点不在集中,故0G1n11 tkd vmVkjVkj-1V1V2V2n5进而知,又据前所选择,于是得到两个不相邻的顶点
11、,其度数1tkd vn2nd vn皆,从而与矛盾. n 2故原假设不真,因此图中有哈密顿圈,即本题的结论成立.G 、沿着凸多面体的每一个面的周界上都有一只苍蝇在爬行(有多少个面,就有多少只3 苍蝇) ,并且都按顺时针方向在各自的面上沿边界绕行现已知,在任何时候它们的速度都 不小于 (厘米小时) 1 证明:或迟或早必有某两只苍蝇会相撞证:设多面体共有个面,分别用点表示,如果某两个面相邻(有公共棱) ,n12,nv vvL则在相应两点间连线成边,如此得到一个阶图,它显然是一个平面图, (可以这样理nG 解:将多面体充张成一个球面,则多面体的个面便成为球面上的个区域,再将nn分别看成相应区域的内点,
12、相邻区域内点之间所连的线显然可以不相交 )12,nv vvL今固定这样一个瞬间 :所有苍蝇都在棱上爬行(不在端点上,或将端点归入过这端点t诸棱中的一条上,或者去掉所有端点) ,环绕面周界爬行的苍蝇记为,iv,1,2,iPinL今按如下方法将图的一些边标上箭头并染成红色:如果绕面的苍蝇在此瞬间 正沿GiviPt面与的公共棱上爬行,则在边上标出由指向的箭头,并染成红色;ivjvijvvivjv由于每个面上都有一只苍蝇,则的每一顶点都发出一条有向红边G 而当两只苍蝇在同一条棱上爬行时,则它们或者已曾相撞或者将要相撞我们需要证明, 这种情况迟早总会发生反证法,假若此情况不发生,则图为有向简单图(没有重
13、边) ,它有个顶点,恰有Gn 条有向红边,其中必存在有向红圈(这种圈可能不止一个) ;每个圈都将的其余顶点nG 分成两部分(即把球面分成两部分) ,在球面上沿着圈的箭头方向前进,左侧称为正部,右侧称为负部;对于同一个圈,若以正部作为其内部,则是反时针的;若以负部作为其CC 内部,从内部看,则是顺时针的于是对于同一个圈,按其“内部”的不同,可作两CC 次看待。 我们将一个圈上的点数与其所围“内部”的点数之和称为这个圈的“权值” ,由于不同的圈只有有限多个,故必有一个瞬间,使得有一个圈的“权值”达到最小,设此圈为0tC分两种情况讨论:6、若圈为顺时针的(即以负部作为其内部) ,这时圈上每一顶点所表
14、示的面上 1CCiv的苍蝇都在向圈内方向爬行,自时刻后,再经过一段iP0t时间,圈上必有一只苍蝇首先走完它所在的一条棱而转C入另一条棱;例如图中面上的苍蝇走完棱后将2v2P12A A要转入棱,这时,有向红边将改成,而23A A2 3v v2v B点(表示一个面的点)也要发出一条红边到达另一顶点,B 如此沿箭头走下去,将出现两种情况,要么得到一个权值更小的圈,这将与所设的最小性矛盾;要么在经过圈内若干个点后,又回到圈的顶点,这时,所得的圈即使权值不变,C 但圈内的顶点至少耗去一个,再经过一段时间后,又将有一只苍蝇走完所在的棱而转向另 一条棱,重新出现上述情况,逐渐使圈内的点减少到零,又经过一段时
15、间后,当圈上一条 边再次出现上述情况时,新的一个箭头将指向圈上另一点,从而使圈的权值严格减少,与 所设矛盾、若圈为逆时针的(即以正部作为其内部) ,这时,只须让时间倒流,往前追溯, 2C仿照,亦可推出矛盾 1因此,必出现两只苍蝇在同一条棱上爬行的情况,即或迟或早有两只苍蝇相撞 、对于直线上的两个点集和,如果能经过适当平移后重合于,则说这两个4ABAB集是相等的;试确定,闭区间能否分解成两个互不相交的相等的点集? 1,1解:设,且存在,使得, 1,1,ABAB UI0a xAxaB今设,则;xAxaB 当时,考虑点的归属:假若,则有,矛盾!21xa2xa2xaBxaA 于是有 2xaA 显然,集的最小点是, (事实上,