1、中国数学奥林匹克赛前培训练习41. 设n是大于1的整数，记,1,1,0,2sin2cos nknkinkk 试求下式的最简表示： 112.)(nkjkj 2. 证明：如果 Znkaniki ,11， 则 nknik kinii nnaa )(11113. 如果正整数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
2、1，求最小的整数m(k) 1，要求能保证存在f F，使得f (x) = m(k)恰有k个不相同的整数根。5.一次体育比赛共设有 ( )2 2n n 个项目，每个选手恰好报名参加其中的两个项目，而任两个人都至多有一个相同的项目，假定对于每个 1,2, , 1k n L ，不超过k人报名的项目少于k个.证明：存在2n个选手，使得每个项目都恰好有其中的两人参加.1、设n是大于1的整数，记wk = cos + i sin ，k = 0, 1, 2, , n1，试求下式的最简表示：。解：设f(x) = (xh) = xn1 + xn2 + + x + 1，则 (1h) = 1 + 1 + + 1 + 1
3、 (n个1) = n(jj + h) = j(1h) = njn1， (jk) = = = nn2故(jk)2 = (1) (jk) = (1)nn2。2.3. 如果正整数n的所有正因数(包括本身)之和为2n，则称n为完全数。如6的正因数之和1+ 2 + 3 + 6 = 26，故6为完全数。证明：不存在形如paqbrc的完全数，其中a, b, c为正整数，p, q, r为奇质数。证：假设存在奇素数p, q, r及正整数a, b, c，使得p a q b r c为完全平方数，不妨设3 p 2，由此知p = 3, q = 5, r = 7, 11, 13之一。1变为 = 23 a5 br c，由于
4、 5| 4| a + 1 4| ；5 ，5| 4| c + 1 4| ；5| 4| c + 1 13 2 + 1| 17| ，故r = 11，5| ，从而5| c + 1，| ，因此 | 23 a5 b11 c，即16105| 23 a5 b11 c，因此3221| 23 a5 b11 c，但2 3221, 3 3221, 5 3221, 11 3221，矛盾！所以不存在形如p a q b r c的完全平方数。5.一次体育比赛共设有 ( )2 2n n 个项目，每个选手恰好报名参加其中的两个项目，而任两个人都至多有一个相同的项目，假定对于每个 1,2, , 1k n L不超过k人报名的项目少于
5、k个.证明：存在2n个选手，使得每个项目都恰好有其中的两人参加.证：用2n个点表示这2n个项目，若其中某两个项目被同一人选报，则令相应的两点相邻（即一条边表示一个选手），于是得到2n阶简单图G，且图G满足“性质P”： 1,2, , 1k n“ L ，度数 k的顶点至多 1k - 个.只要证，图G含有哈密顿圈（经过图G每个顶点的圈），即G为哈密顿图.反证法，若图G中不含哈密顿圈，则集合H =G G是具有性质P的2n阶非哈密顿图不是空集，从而H中有极大元 0G （边数最多的），于是：( )1 .因为 0G 非哈密顿图，故其中必有不相邻的顶点，而对于任一对不相邻顶点 ,u v，由 0G 的极大性，添
6、加边uv后所得的图 1G便成为哈密顿图，即图 1G中有一个含有边uv的哈密顿圈，于是在 0G 中有一条以u、v为起、终点的哈密顿路：1 2 2nv v vL （其中 1 2, nu v v v= = ）.( )2 .对于 0G 中任一对不相邻顶点 ,u v，度数 ( ) ( ), d u d v 中至少有一个 1n .事实上，因顶点 ,u v不相邻，据( )1 知， 0G 中有一条以u、v为起终点的哈密顿路： 1 2 2nvv vL （其中 1 2, nu v v v= = ），假若 ( ) ( ), d u n d v n吵 ，若 ( )d u r n= ，u（即 1v）相邻的r个顶点 为
7、1 2, , , rk k kv v vL ( )1 22 2rk k k n= L ，则对于每个 1,2, ,j r= L ，顶点 1jkv - 都不 2nv （即v）相邻， 则在 0G 中 有哈密顿圈：1 2 1 2 2 1 1j jk n n kv v v v v v v- -L L ，这 0G 的选 .所以 ( ) ( ) ( )2 1 2 1 1d v n r n n n- - = - ，而这 ( )d v n的假设 .( )3 .据( )2 知， 0G 中必有度数 1n 的顶点，即集合( ) ( ) , 1v v V G d v nE = -危 不是空集，设 1v是集E中度数最大的
8、一个点，( ) ( ) 1 max 1d v m d v v n= = 蜤 ，据性质P知，集E中至多有 2n- 个点，从而在 0G 中至少有 2n+ 个点的度数 n，于是在这 2n+ 个点中必有一个不 1v相邻的点（因为 1v相邻的点只有m个，而 1m n ），设 顶点为 2nv ，（于是 ( )2nd v n）.1v 2nv 不相邻，据 0G 的极大性，有一条经过 0G 所有顶点的哈密顿路：1 2 2nv v vL ，在这条哈密顿路上， 1v相邻的m个点 为 1 2, , , mk k kv v vL ，( )1 22 2mk k k n= L . 据( )2 的证法知，对每个 11,2,
9、, , jkj m v -= L 都不 2nv 相邻，而据性质P中 1k m n= 的 知，在 1 21 1 1, , , mk k kv v v- - -L 这m个点中，至少有一个点的度数 1m （因 1m n ，据性质P，度数 m的顶点至多1m- 个），设 1tkv - 是这 一个点，即 ( )1 1tkd v m- ， 由m的定 （m是集E中所有点的最大度数，而集E中含有 0G 中度数 1n 的所有点）， ( )1 1tkd v m- ，故 点不在集E中，故 而知 ( )1tkd v n- ， 据 所选 ，( )2nd v n，于是得到两个不相邻的顶点，其度数 n，从而 ( )2 . 故 假设不 ，因 图G中有哈密顿圈，即 的 成 .
