1、中国数学奥林匹克赛前培训练习 41. 设 是大于 1 的整数，记n,1,0,2sinconkkk 试求下式的最简表示： 1.)(nkjkj2. 证明：如果 ， 则 Zanik,1 nknikia)(113. 如果正整数 n 的所有正因数(包括本身) 之和为 2n，则称 n 为完全数。如 6 的正因数之和1 + 2 + 3 + 6 = 26，故 6 为完全数。证明：不存在形如 paqbrc 的完全数，其中 a, b, c 为正整数，p, q, r 为奇质数。4.设 f(x)是整系数多项式，并且 f(x)=1 有整数根，约定将所有满足上述条件的 f 的组成的集合记为 F。对于任意给定的整数 k 1
2、，求最小的整数 m(k) 1，要求能保证存在 f F，使得 f (x) = m(k)恰有 k 个不相同的整数根。5.一次体育比赛共设有 个项目，每个选手恰好报名参加其中的两个项2 n目，而任两个人都至多有一个相同的项目，假定对于每个 ，不1,2kn超过 人报名的项目少于 个.kk证明：存在 个选手，使得每个项目都恰好有其中的两人参加.2n1、 设 n 是大于 1 的整数，记 wk = cos + i sin ，k = 0, 1, 2, , n 1，试求下式的最简2kn 2kn表示： 。1 j p a + 1p 1 q b + 1q 1 r c + 1r 1 1p 1 1q 1 1r 12，由此
3、知 p = 3, q = 5, r = 7, 11, 13 之一。1 变为 = 23 a5 br c，3 a + 1 12 5 b + 1 14 r c + 1 1r 1由于 5| 4| a + 1 4| ；5 ，5| 4| c 3 a + 1 12 3 a + 1 12 5 b + 1 14 7 c + 1 16+ 1 4| ；7 c + 1 165| 4| c + 1 13 2 + 1| 17| ，13 c + 1 112 13 c + 1 112 13 c + 1 112故 r = 11，5| ，从而 5| c + 1， | ，11 c + 1 110 11 5 110 11 c + 1
4、 110因此 | 23 a5 b11 c，即 16105| 23 a5 b11 c，因此 3221| 23 11 5 110a5 b11 c，但 2 3221, 3 3221, 5 3221, 11 3221，矛盾！所以不存在形如 p a q b r c 的完全平方数。5.一次体育比赛共设有 个项目，每个选手恰好报名参加其中的两2 n个项目，而任两个人都至多有一个相同的项目，假定对于每个 ，1,2kn不超过 人报名的项目少于 个.kk证明：存在 个选手，使得每个项目都恰好有其中的两人参加.2n证：用 个点表示这 个项目，若其中某两个项目被同一人选报，则令相应的两点相邻（即一条边表示一个选手）
5、，于是得到 阶简单图 ，且图2nG满足“性质 ”： ，度数 的顶点至多 个.GP1,2kn k1k只要证，图 含有哈密顿圈（经过图 每个顶点的圈） ，即 为哈密顿图.G反证法，若图 中不含哈密顿圈，则集合 是具有性质 的 阶非哈密顿图GP2n不是空集，从而 中有极大元 （边数最多的） ，于是：0G因为 非哈密顿图，故其中必有不相邻的顶点，而对于任一对不相邻1.0顶点 ，由 的极大性，添加边 后所得的图 便成为哈密顿图，即图 中,uvuv1G1G有一个含有边 的哈密顿圈，于是在 中有一条以 、 为起、终点的哈密顿0uv路：（其中 ）.12nv 12,nuv对于 中任一对不相邻顶点 ，度数 中至少
6、有一个 .0G,uv, duv1n事实上，因顶点 不相邻，据 知， 中有一条以 、 为起终点的哈,uv10Guv密顿路： （其中 ） ，假若 ，若12nv 12,nv, dn，与 （即 ）相邻的 个顶点记为durvr12rkkv，则对于每个 ，顶点 都不与 （即 ）12rkk ,jr 1j2nv相邻，否则在 中就有哈密顿圈：0G，这与 的选择矛盾.12121j jknkvv 0所以 ，而这又与 的假设矛盾.21drndvn据 知， 中必有度数 的顶点，即集合3.0G不是空集，设 是集 中度数最大的一个点，,1vVv1v记 ，据性质 知，集 中至多有 个点，1maxddnP2n从而在 中至少有
7、个点的度数皆 ，于是在这 个点中必有一个不与0G2n2n相邻的点（因为与 相邻的点只有 个，而 ） ，设该顶点为 ， （于1v1vm12nv是 ）.2nd既然 与 不相邻，据 的极大性，有一条经过 所有顶点的哈密顿路：1v2n0G0G，在这条哈密顿路上，与 相邻的 个点记为 ，12nv 1vm12,mkkv. 据 的证法知，对每个 都不与2mkkn 2 1 jjv相邻，而据性质 中 的情形知，在 这 个点中，2nvP12,mkkv至少有一个点的度数 （因 ，据性质 ，度数 的顶点至多1P个） ，设 是这样一个点，即 ，又由 的定义（ 是集1m1tkv1tkdvm中所有点的最大度数，而集 中含有 中度数 的所有点） ，既然0Gn，故该点不在集 中，故进而知 ，又据前所选择，1tkdv1tkv，于是得到两个不相邻的顶点，其度数皆 ，从而与 矛盾. 2ndv n2故原假设不真，因此图 中有哈密顿圈，即本题的结论成立.G
