训练题B解答doc.docVIP

训练题B解答 （陶平生） 、将数列处于平方位置的项所构成的子数列，称为数列的“平方子列”，今从正整数数列中，删去其平方子列，在剩下的项所构成的数列 中，再次删去其平方子列，如此继续．第次删去的平方子列中的第项记为． 、求的表达式； 、求正整数，使． 解：、我们将探求的过程分三步进行： 、试验：对前个数进行所述的操作，顺次得到七个平方子列，即有序组，，，，，，，排列如表一： （表一） （表二） （表三） 在表一中，从每行或每列看，不易发现其规律，但是如果将数与用斜线连结，且从其它每个数所在位置都作该斜线的平行线，立即可以看出，数表有特征：从左到右，顺次将每条斜线上的数自下而上读出，恰好就是数按自然顺序的排列； 、构造：依照上述斜线规则，易将数表续填下去，使得每个正整数都出现于表中，具体填法如表二，表三．（表三的制作方法是：在一根水平线上，等距地取一列点，过每个点作铅垂射线，过每个点，以及每相邻两点的中点，作一簇平行的斜线，自左至右顺次记为，在与每条的交点处填数）. 一般说来，若最上方填，则因下一条斜线与射线都相交，共得个交点，于是在上应填个数，自下而上第一数为，最上方一数为，而其第个数为， …① 又因斜线与射线相交，有个交点，则在上应填个数，自下而上第一数为，最上方一数为，而其第个数为， … ② 因此，在点处（即表中第一行），所填的数顺次为， ，…，将①②合并得，第根斜线上的第个数为： ，（其中，）……③ 现将表二中第行第个数记为，则是第根斜线上的第一数，是第根斜线上的第二数，…，是第根斜线上的第个数… ④， 由③得 … ⑤ 、下面证明，，即要证，表二的第行就是数列的第个平方子列． 为此，称正整数序列为“数列”； 对用数学归纳法，时，由填数方法知，在表二的第一行所填的数顺次为，故是数列的第一个平方子列； 假设表二的前行分别是数列的前个平方子列，则当从表中删去前行后，剩下的数如按从小到大的顺序排列，恰好就是从数列中删去前个平方子列后剩下的数组成的数列（称为数列）…… ⑥ 按定义，数列是数列的平方子列，即 是数列中自小到大的第个数． 而在表二中删去前行后，不超过的数，全部含于由表中第行，第一列及第根斜线所围成的三角形区域中，而在此区域中，第列有个数，第列有个数，…，第列有个数，共计有个数，且位于该区域最后一根斜线上方，故是区域中的最大数，从而由⑥得，是数列中从小到大的第个数，因此，． 故由数学归纳法得，表二的第行，即是数列的第个平方子列（）， 由⑤得，． 、由于，故位于表二第根（）斜线上，且是该斜线自下而上的第个数（），所以，由 ④又有，，则，因此． 、一次体育比赛共设有个项目，每个选手恰好报名参加其中的两个项目，而任两个人都至多有一个相同的项目，假定对于每个，不超过人报名的项目少于个. 证明：存在个选手，使得每个项目都恰好有其中的两人参加. 证：用个点表示这个项目，若其中某两个项目被同一人选报，则令相应的两点相邻（即一条边表示一个选手），于是得到阶简单图，且图满足“性质”：，度数的顶点至多个. 只要证，图含有哈密顿圈（经过图每个顶点的圈），即为哈密顿图. 反证法，若图中不含哈密顿圈，则集合 {是具有性质的阶非哈密顿图}不是空集，从而中有极大元（边数最多的），于是： 、因为非哈密顿图，故其中必有不相邻的顶点，而对于任一对不相邻顶点，由的极大性，添加边后所得的图便成为哈密顿图，即图中有一个含有边的哈密顿圈，于是在中有一条以、为起、终点的哈密顿路： （其中）. 、对于中任一对不相邻顶点，度数中至少有一个. 事实上，因顶点不相邻，据知，中有一条以、为起终点的哈密顿路：（其中），假若，若，与（即）相邻的个顶点记为，则对于每个，顶点都不与（即）相邻，否则在中就有哈密顿圈： ，这与的选择矛盾. 所以 ，而这又与的假设矛盾. 、据知，中必有度数的顶点，即集合 不是空集，设是集中度数最大的一个点， 记，据性质知，集中至多有个点，从而在中至少有个点的度数皆，于是在这个点中必有一个不与相邻的点（因为与相邻的点只有个，而），设该顶点为，（于是）. 既然与不相邻，据的极大性，有一条经过所有顶点的哈密顿路： ，在这条哈密顿路上，与相邻的个点记为， . 据的证法知，对每个都不与相邻，而据性质中的情形知，在这个点中，至少有一个点的度数（因，据性质，度数的顶点至多个），设是这样一个点，即，又由的定义（是集中所有点的最大度数，而集中含有中度数的所有点），既然，故该点不在集中，故进而知，又据前所选择，，于是得到两个不相邻的顶点，其度数皆，从而与矛盾. 故原假设不真，因此图中有哈密顿圈，即本题的结论成立. 、沿着凸多面体的每一个面的周界上都有一只苍蝇在爬行（有多少个面，就有多少只苍蝇），并且都按顺时针方向在各