《训练题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 显然，集的最小点是， （事实上，
