训练题B解答.doc0321112247706.doc

训练题B解答 （陶平生）、将数列处于平方位置的项所构成的子数列，称为数列的“平方子列”，今从正整数数列中，删去其平方子列，在剩下的项所构成的数列中，再次删去其平方子列，如此继续第次删去的平方子列中的第项记为、求的表达式；、求正整数，使解：、我们将探求的过程分三步进行：、试验：对前个数进行所述的操作，顺次得到七个平方子列，即有序组，排列如表一：（表一） （表二） （表三）在表一中，从每行或每列看，不易发现其规律，但是如果将数与用斜线连结，且从其它每个数所在位置都作该斜线的平行线，立即可以看出，数表有特征：从左到右，顺次将每条斜线上的数自下而上读出，恰好就是数按自然顺序的排列；、构造：依照上述斜线规则，易将数表续填下去，使得每个正整数都出现于表中，具体填法如表二，表三（表三的制作方法是：在一根水平线上，等距地取一列点，过每个点作铅垂射线，过每个点，以及每相邻两点的中点，作一簇平行的斜线，自左至右顺次记为，在与每条的交点处填数）.一般说来，若最上方填，则因下一条斜线与射线都相交，共得个交点，于是在上应填个数，自下而上第一数为，最上方一数为，而其第个数为， 又因斜线与射线相交，有个交点，则在上应填个数，自下而上第一数为，最上方一数为，而其第个数为， 因此，在点处（即表中第一行），所填的数顺次为，将合并得，第根斜线上的第个数为：，（其中，）现将表二中第行第个数记为，则是第根斜线上的第一数，是第根斜线上的第二数，是第根斜线上的第个数 ，由得 、下面证明，即要证，表二的第行就是数列的第个平方子列为此，称正整数序列为“数列”；对用数学归纳法，时，由填数方法知，在表二的第一行所填的数顺次为，故是数列的第一个平方子列；假设表二的前行分别是数列的前个平方子列，则当从表中删去前行后，剩下的数如按从小到大的顺序排列，恰好就是从数列中删去前个平方子列后剩下的数组成的数列（称为数列） 按定义，数列是数列的平方子列，即是数列中自小到大的第个数而在表二中删去前行后，不超过的数，全部含于由表中第行，第一列及第根斜线所围成的三角形区域中，而在此区域中，第列有个数，第列有个数，第列有个数，共计有个数，且位于该区域最后一根斜线上方，故是区域中的最大数，从而由得，是数列中从小到大的第个数，因此，故由数学归纳法得，表二的第行，即是数列的第个平方子列（），由得，、由于，故位于表二第根（）斜线上，且是该斜线自下而上的第个数（），所以，由又有，则，因此、一次体育比赛共设有个项目，每个选手恰好报名参加其中的两个项目，而任两个人都至多有一个相同的项目，假定对于每个，不超过人报名的项目少于个.证明：存在个选手，使得每个项目都恰好有其中的两人参加.证：用个点表示这个项目，若其中某两个项目被同一人选报，则令相应的两点相邻（即一条边表示一个选手），于是得到阶简单图，且图满足“性质”：，度数的顶点至多个.只要证，图含有哈密顿圈（经过图每个顶点的圈），即为哈密顿图.反证法，若图中不含哈密顿圈，则集合是具有性质的阶非哈密顿图不是空集，从而中有极大元（边数最多的），于是：、因为非哈密顿图，故其中必有不相邻的顶点，而对于任一对不相邻顶点，由的极大性，添加边后所得的图便成为哈密顿图，即图中有一个含有边的哈密顿圈，于是在中有一条以、为起、终点的哈密顿路：（其中）.、对于中任一对不相邻顶点，度数中至少有一个.事实上，因顶点不相邻，据知，中有一条以、为起终点的哈密顿路：（其中），假若，若，与（即）相邻的个顶点记为，则对于每个，顶点都不与（即）相邻，否则在中就有哈密顿圈：，这与的选择矛盾.所以 ，而这又与的假设矛盾.、据知，中必有度数的顶点，即集合不是空集，设是集中度数最大的一个点，记，据性质知，集中至多有个点，从而在中至少有个点的度数皆，于是在这个点中必有一个不与相邻的点（因为与相邻的点只有个，而），设该顶点为，（于是）.既然与不相邻，据的极大性，有一条经过所有顶点的哈密顿路：，在这条哈密顿路上，与相邻的个点记为，. 据的证法知，对每个都不与相邻，而据性质中的情形知，在这个点中，至少有一个点的度数（因，据性质，度数的顶点至多个），设是这样一个点，即，又由的定义（是集中所有点的最大度数，而集中含有中度数的所有点），既然，故该点不在集中，故进而知，又据前所选择，于是得到两个不相邻的顶点，其度数皆，从而与矛盾. 故原假设不真，因此图中有哈密顿圈，即本题的结论成立.、沿着凸多面体的每一个面的周界上都有一只苍蝇在爬行（有多少个面，就有多少只苍蝇），并且都按顺时针方向在各自的面上沿边界绕行现已知，在任何时候它们的速度都不小于（厘米小时）证明：或迟或早必有某两只苍蝇会相撞证：设多面体共有个面，分别用点表示，如果某两个面相邻（有公共棱），则在相应两点间连线成边，如此得到一个阶图，它显然是一个平面图，（可以这样理解：将多面体充张成一个球面，则多面体的个面便成为球面上的个区域，再将分别看成相应区域的内点，相邻区域内点之间所连的线显然可以不相交）今固定这样一个瞬间：所有苍蝇都在棱上爬行（不在端点上，或将端点归入过这端点诸棱中的一条上，或者去掉所有端点），环绕面周界爬行的苍蝇记为，今按如下方法将图的一些边标上箭头并染成红色：如果绕面的苍蝇在此瞬间正沿面与的公共棱上爬行，则在边上标出由指向的箭头，并染成红色；由于每个面上都有一只苍蝇，则的每一顶点都发出一条有向红边而当两只苍蝇在同一条棱上爬行时，则它们或者已曾相撞或者将要相撞我们需要证明，这种情况迟早总会发生反证法，假若此情况不发生，则图为有向简单图（没有重边），它有个顶点，恰有条有向红边，其中必存在有向红圈（这种圈可能不止一个）；每个圈都将的其余顶点分成两部分（即把球面分成两部分），在球面上沿着圈的箭头方向前进，左侧称为正部，右侧称为负部；对于同一个圈，若以正部作为其内部，则是反时针的；若以负部作为其内部，从内部看，则是顺时针的于是对于同一个圈，按其“内部”的不同，可作两次看待。我们将一个圈上的点数与其所围“内部”的点数之和称为这个圈的“权值”，由于不同的圈只有有限多个，故必有一个瞬间，使得有一个圈的“权值”达到最小，设此圈为分两种情况讨论：、若圈为顺时针的（即以负部作为其内部），这时圈上每一顶点所表示的面上的苍蝇都在向圈内方向爬行，自时刻后，再经过一段时间，圈上必有一只苍蝇首先走完它所在的一条棱而转入另一条棱；例如图中面上的苍蝇走完棱后将要转入棱，这时，有向红边将改成，而点（表示一个面的点）也要发出一条红边到达另一顶点，如此沿箭头走下去，将出现两种情况，要么得到一个权值更小的圈，这将与所设的最小性矛盾；要么在经过圈内若干个点后，又回到圈的顶点，这时，所得的圈即使权值不变，但圈内的顶点至少耗去一个，再经过一段时间后，又将有一只苍蝇走完所在的棱而转向另一条棱，重新出现上述情况，逐渐使圈内的点减少到零，又经过一段时间后，当圈上一条边再次出现上述情况时，新的一个箭头将指向圈上另一点，从而使圈的权值严格减少，与所设矛盾、若圈为逆时针的（即以正部作为其内部），这时，只须让时间倒流，往前追溯，仿照，亦可推出矛盾因此，必出现两只苍蝇在同一条棱上爬行的情况，即或迟或早有两只苍蝇相撞、对于直线上的两个点集和，如果能经过适当平移后重合于，则说这两个集是相等的；试确定，闭区间能否分解成两个互不相交的相等的点集？解：设，且存在，使得，今设，则；当时，考虑点的归属：假若，则有，矛盾！于是有 显然，集的最小点是，（事实上，如有，使，则，但是，矛盾！），于是 .类似可知，（事实上，如有，使，则，而，矛盾！）于是，当，必有 .将改记为 ，其中.我们来证明，对任何，式皆成立.对归纳：据知，时，结论成立；设对于某个自然数，式成立，则据平移，有，而，则，注意，据所设式，以及，所以由，即；进而由得，；即，所以，（若该区间有某点，则，而，矛盾！），即式对于成立因此对任何，式皆成立.于是对任何，这与集的有界性矛盾！因此闭区间不能分解成两个互不相交的相等的点集、设为正整数，是的二进制小数表示（其中），从其小数点后任意截取一段相继位置上的数字，所得到的一个二进制整数，称为的一个“截段”（例如，对于的二进制小数表示而言，数的二进制表示或便是其“截段”）试求最小的正整数，使得不大于的每个正整数的二进制表示，都是的一个“截段”解：首先由，且大于的最小质数是；我们证明，便是满足上述要求(简称为性质)的最小正整数一、先证明，小于的任何正整数都不具有性质反证法，若有，使，用表示具有性质的最小正整数，显然有，记 ，则，进而可推出为奇数；否则，若为偶数，则可知，这与的最小性矛盾于是，故二进制小数是纯循环小数，设其循环节（最小正周期）长为，此是满足的中的最小正整数，即对任何满足的都有 而据的循环性，对任何，有.下面估计循环节长的值注意到二进制截段之间存在的“包含性”（例如，截段包含有截段等）我们需要列出那些不相包含的二进制表示，由于，因此，不大于的任一正整数，其二进制表示至多有个数位主要考虑长为的截段情况：即从到这些数的二进制表示；每个这样的位截段的首位数字都是；首先，数占有个数位我们不妨将循环节看成由此数开始；对于，区间中，共有个数，其中每个数的二进制表示都是位的，其结构为：形状（中间的将该数分成首位为的前后两段，前段有个数位，后段有个数位，且前段相同的后段必不相同，于是代表这种数的任一个位截段与代表其它数的位截段连接时，其首位不可能越过截段中间的那个 ）因此每个这种数至少占用循环节中的个数位故中的数共占去至少个数位考虑不同的，中的这个数的二进制表示至少要占去同一个循环节中的个数位；从到有个数，这些数的二进制表示也是位的，每个数的二进制表示与其它的数的二进制表示至少有一数位上的数不同，即总共至少要扩充个新的数位由于下一个循环节也由位数开始，于是从到中的任一数的二进制表示，其首位数必须在前述的循环节中，从而归入了前面的计算这样，从到这些数的二进制表示，都要在同一个循环节中出现 因此，循环节长由于，据欧拉定理，所以由得，而，由得 ，故从式得，.假若不是质数，则它具有质因数，满足，于是.这与矛盾，因此必为质数.据知，对于互不同余，而若，则 ；于是，当取时，相应的所得的二进制循环小数可以从的循环节（长为）的任一位数字开始 对于每个，的二进制表示共有位数字据条件，该二进制表示是的一个截段，所以有，使，（的前位与相同）据知，正整数随严格单增，从而，所以而在区间中的奇数只有，然而这三数皆不为质数（），这与为质数矛盾所以小于的任何正整数皆不具有性质，从而二、再证明，具有性质，因为质数，设 ；对任一整数，则的二进制表达式至多位我们需要证明，存在的一个截段使先证明，二进制表示的循环节(最小正周期)长=2052即要证，满足的的最小正整数因为质数，所以，即若是满足且的最小正整数，则于是下列三情况之一必要发生.()、 ； ()、； ()、即以下三式：（1）、； （2）、；（3）、之中至少有一个要成立我们来证明，上述三式皆不成立注意由，得又由得，记，则 ，所以，由此得；令，则，所以；又令，则