29、超纲离散.doc

Size: px

Start display at page:

Download "29、超纲离散.doc"

私多
5 years ago
Views:

1 廖老师网上千题解答分类二十八超纲离散 x, x P, 8 函数 f(x) 其中 P,M 为实数集 R 的两个非空子集, 又规定 x, x M, f(p){y yf(x),x P},f(M){y yf(x),x M}. 给出下列四个判断 : 若 P M, 则 f(p) f(m) ; 若 P M, 则 f(p) f(m) ; 若 P MR, 则 f(p) f(m)r; 4 若 P M R, 则 f(p) f(m) R. 其中正确判断有 (A) 个 (B) 个 (C) 个 (D)4 个解 : 的反例 : 取 P {}, M {-},f(p) {},f(m) {} f(p) f(m) {} 的反例 : 取 P [0, )M (-,0), f(p) [0, ), f(m) (-,0) 但 f(p) f(m) [0, ) R 的证明若 P M, 设 a P M, 则 f(a) a -a, 故 a 0 因此 0 f(p),0 f(m), 故 f(p) f(m) 4 的证明 : 因 P M R 故存在实数 a P M, 假设 f(p) f(m)r, 则 a f(p) f(m) 若 a f(p) 则 a P 与 a P M 矛盾故 a f(m), 因此 -a M, 由于 a P M 故 a 0 又由于 P M 的元素只能是 0 故 -a P -a f(p) -a f(m) a M 与 a P M 矛盾综上 4 正确, 选 B 89 已知 f(x)x axb(a b R), 且 A{x xf(x)},b{x xf[f(x)]}, 则 (A)A 是 B 的子集 (B)B 是 A 的子集 (C)AB (D)B 是 A 的真子集解 : 设 x 0 A{x xf(x)} 则 x 0 f(x 0 ),f(x 0 )f(f(x 0 )),x 0 f(f(x 0 )), x 0 B{x xf[f(x)]} 选 A

2 65 被整除余, 被 5 整除余, 被整除余, 被 9 整除余 4 的正整数组成的集合是什么?( 竟寒 ) 解 : 利用中国剩余定理, 找被 5 9 整除, 被整除余的数,5 95 找被 9 整除, 被 5 除余的数, 96 找被 5 9 整除, 被除余的数, 5 9 (-)-90 找被 5 整除, 被 9 除余的数, 于是所求的集合是 { x x k 5 9, k Z} { x x 4 60kk, Z} { x x 4 60kk, Z} { x x 5 60kk, Z} 69 被整除余, 被 5 整除余, 被整除余, 被 9 整除余 4 的正整数组成的集合是什么?( 竟寒 ) 解 ( 用一个土方法 ) 9 除余 4 最小正整数为 4, 4 若干个 9 结果仍被 9 除余 4 4 被整除余 4,9 被整除余, 49 被 9 整除余 4, 且被除余若干个 6 结果仍被 9 除余 4, 且被除余被 5 整除余,6 被 5 整除余 6 5 被 9 整除余 4, 被除余, 且被 5 除余显然 5 被除余故所求集合为 { x x 5 60k, k z} 0 参加数学课人, 物理 8 人, 化学式 6 人, 至少参加一种的有 6 人, 则三门都参加至多有多少人? ( 竟寒 ) 解 ; 设参加两种的分别有 x 人 y 人 z 人, 三种都参加的人则由容斥原理得 686-x-y-z xyz0 x,y,z,xyz,0, 0 三项都参加的至多 0 人

3 4 判断命题若 a a0 和 a4 都是正质数, 则 a 的真假, 并说明理由 ( 竞赛 ) 答 : 这是个真命命题若 a,a0 和 a4 都是正质数, 由于 0,0,4 被除的余数分别为 0,, 因此 () 若 a 被除的余数为, 则 a4 不是质数 () 若 a 被除的余数为, 则 a0 不是质数 () 若 a 被除的余数为 0, 则 a 为的倍数, 又 a 是质数, 故 a 等于, 故命题成立 69 甲乙丙三人, 丙的生日是 X 月 Y 日甲乙都知道丙的生日是以下 0 组中的一天月日月日月 8 日 5 月 6 日 5 月日 8 月 4 日 8 月 9 日 0 月 4 日 0 月 6 日 0 月 8 日甲知道 X 值, 乙知道 Y 值甲说 : 我如果不知道, 乙肯定不知道乙接着说, 本来我不知道但是现在我知道了甲接着说 : 那我也知道了大家知道丙的生日是哪天吗在线等答案谢谢大家答 :8 月 4 日乙接着说, 本来我不知道但是现在我知道了本来二字说明了乙通过十个日期和 Y 不能推断出丙的生日, 由此可知丙的生日不可能是号或 9 号 ( 因为号和 9 号所对应的月份是唯一的月日,8 月 9 日 ) 而甲在听到乙的这句话后立刻得出丙的生日了说明了甲在排除月日,8 月 9 日后就明白了丙是几号生日了, 排除 8 月 9 日, 月日后每个月的日期如下 : 月日 5 月 6 日 8 月 4 日 0 月 4 日月 8 日 5 月日 0 月 6 日 0 月 8 日由上表易知甲可以作出迅速的选择的原因是丙在 8 月生日得丙在 8 月 4 日生日 8 韩信点兵, 每人一列余人, 每 5 人一列余人, 每人一列余 4 人, 每人一列余 6 人, 问士兵总数借此题目, 让我们大家一块讨论一下中国剩余定理解 : 所求的数是 6 4

4 8 若 [x9/00][x0/00][x/00]...[x9/00]546, 求 [00x] 的值这里 "[y]" 表示不大于 y 的整数, 如 [0.]0,[.9],[-0.]- 解 : 式子 [x9/00][x0/00][x/00]...[x9/00] 中共有 9-8 个加数,546 余 5 故 [x ] 后面 5 个加数中的值为 [x ], 由于 [x ] [x/00 ] [x/00 ] [x8/00][x9/00][x0/00][x/00] [x9/00] [x9/00] [x99/00] [00x] [00x] 已知函数 f(x)[x[x[x]]], 其中 [x] 表示不超过 x 的最大整数, 若其定义域为 [0,4], 则其值域为 ( 竞赛 ) 解 : 当 0 x < 时 [x]0,f(x) [x[x[x]]0 当 x < 时 [x],f(x) [x[x[x]] [x[x]] [x] 当 x < 时 [x],f(x) [x[x[x]] [x[x]] 4 x < 6 [x]4 或 5 8 x[x] < 5 8 f(x) 4 当 x < 4 时 [x],f(x) [x[x[x]] [x[x]] 9 x < [x]9 或 0 或 x[x] < 44 f(x) 4 80 若 [x9/00][x0/00][x/00]...[x9/00]546, 求 [00x] 的值这里 "[y]" 表示不大于 y 的整数, 如 [0.]0,[.9],[-0.]- ( 竞赛 ) 解 : 式子 [x9/00][x0/00][x/00]...[x9/00] 中共有 9-8 个加数,546 余 5 故 [x ] 后面 5 个加数中的值为 [x ], 由于 [x ] [x/00 ] [x/00 ] [x8/00][x9/00][x0/00][x/00] [x9/00] [x9/00] [x99/00] [00x] [00x] 函数 f(x) 具有下性质 : 对每个实数 x, 都有 f( x) f( x- ) x 如果 f(9)94, 那么 f(94) 除以 000 的余数是多少解 :f()-f(-) () 故可设 f ( ) a( ) b( ) c [ f ( ) a b c] f ( ) f ( ) a ( a b) c () ()( ) 对照得 a, b, c 0 f ( ) ( ) ( ) [ f ( ) ] f (94) [ f (9) 9 9] ( ) 接下去自已完成

5 56 求证: 对任意的正整数, L 不可能为整数 ( 竟赛 ) 证明 :( 用反证法 ) 假设 L 是整数则 L 乘以任何整数仍为整数下面我们去找一个与 L 有关的整数 Q 使它与 L 相乘不为整数就可以了我们把,, L, 分别用除, 除到商数为奇数为止, 这是可以做的事情设除的次数分别为 p, p, L p, 最后的奇数商数分别为 k, k, Lk, 于是 L L p p p k k k 设 p, p, L p 中最大的为 p p 则 k k Lk 必为整数, 由假设 L 是整数 p 因此 k k Lk ( L ) 也是整数 () p 另一方面, 我们来证明 k k Lk ( L ) 不是整数下面先证 p, p, L p 之中只有一个等于 p 如果 p, p, L p 中有两个数 p 和 p 都等于 p ( < ) 即 p p p, 于是 p k k, k 由于 <, 因此 k p < k, p p k 因为 k 与 k 是奇数, 故有偶数在 k 与 k 之间 p p 即 k < k < k, k < < p p k 即 < < p 于是设 u, 则 p u p, 这与 p 是 p, p, L p 中最大者矛盾因此, p, p, L p 之中只有一个等于 p, 设 p p p k k Lk ( L ) 整数 N kk Lk k Lk 因为 k k, k, k, k 都是奇数, 所以 kk Lk k Lk 不是整数 p 故 k k Lk ( L ) 不是整数这与 () 相矛盾所以假设不成立, 因此是整数 L 不可能为整数 5

6 ( 4-) 588 当 N 且时, 5p q, 其中 p,q 为非负整数, 且 0 q<5, 则 q 的值为多少?( 数论 ) ( 4-) 4 解 : - 5p q, 4 6 (5 ) 0 ( C 5 C 5 L C 5 ) 0 C 5 C 5 L C 5 m ( m N), 于是 5 m 5p q 5 因为 p,q 为非负整数 0 q<5 所以就相当于求 5 m 被 5 除商数 p 是几?, 余数数 q 是几?, 故 p m, q 设平面上有 6 个圆, 每个圆都不能盖住其它任何一个圆心, 证明 : 平面上任一个点都不会被 6 个圆同时盖住 ( 竟赛 ) 证明 : 设六个圆的圆心分别为 O,O,O,O 4,O 5,O 6, 按顺时针方向排列设平面上点 M 被六个圆盖住, 连 M O,M O 如图, 设圆 O,O 的半径分别为 r 和 r, 不妨设 r r 则 MO r, MO r, O O > r 于是 cos O MO MO MO MO r r r r < < MO MO MO MO MO O O r r O M O 故 O MO > 60, 同理可证 O MO > 60, O 6MO > 60 于是 O MO O MO O MO > 60 6 这是不可能的因此原命题成立 4 68 求出所有可能的整数 x 使 P ( x) x 4x 6x 4x 4 为质数 ( 竟赛 ) 4 解 : P ( x) x 4x 6x 4x ( x ) 4 ( x ) 4( x ) 4 4( x ) 4 ( x ) 4( x ) 4 4( x ) [( x ) ] 4( x ) [( x ) ( x ) ][( x ) ( x ) ] [( x ) ]( x ) 当 x 或 x 0时 P ( x) 5 为质数, 此外 P (x) 都是合数 6

7 0 删去正整数数列 4,,,,L 中的所有完全平方数, 得到一个新数列, 这个新数列的第 005 项是多少?( 数论 ) ( 竟赛 ) 解 :,, L, 05中有,,,45 的平方, 又 46 6 从,, L, 05去掉平方数后还有 980 个数于是第 980 项为 05, 因此第 005 项设 A 是任意一个无理数求证 : 对于任意的正数 m, 都存在两正数 p,q, 使得 pa 与 qa 的前 m 位小数是相同的 ( 数论 ) ( 竟赛 ) 证明 ; 不妨设 A>0,p>q>0 于是只要 pa-qaa(p-q)< 0 m m p-q< 0 /A p <( 0 /A)q m m 0 先任取一个正数为 q, 如 q, 再取 p, 就符合条件 A 8 [ 题目 ]9 名数学家在一国际会议上相遇, 其中任意三个人中总有两个人能讲同一种语言, 如果每个数学家最多能讲种语言. 求证 : 至少有个数学家能用同一种语言交流.( 图论 ) ( 竟赛 ) [ 知识介绍 ] 如果把 m k( m,, k N ) 个东西放进个抽屉, 那么至少有一个抽屉放进 m 个东西. [ 证明 ] 设其中一位数学家为 A () 若其他 8 名都能与数学家 A 交流由于数学家为 A 最多能讲三种语言, 根据抽屉原理, 这 8 名数学家至少有人讲同一种语言, 添上数学家 A, 就至少有 4 人讲同一种语言 () 若其他 8 名中至少有一人不能与数学家 A 交流, 设其中一人为 B 设 M 为 A B 之外的任意一人, 由于其中任意三个人中总有两个人能讲同一种语言, 所以 M 能与 A 交流, 或者能与 A 交流设除 A B 外的名数学家能与 A 交流的组成集合 X, 能与 B 交流的组成集合 Y 根据抽屉原理, 人中至少 4 人在同一集合内不妨设 X 中有 4 人, 也就是说至少有 4 人能与数学家 A 交流, 由于数学家为 A 最多能讲三种语言, 根据抽屉原理, 这 4 人中至少有人能讲同一种语言, 添上数学家 A, 就至少有人讲同一种语言综上所述, 原命题成立

8 90 如果一凸多面体中, 各顶点引出奇数条棱, 求证顶点数为偶数? ( 图论 ) ( 高考不要求 ) 解 : 设个顶点引出奇数条棱分别是 k,k, L,k, 这里 k, k, L, k N k k L kv 于是 E ( k k L k ) V V 代入欧拉公式 V F E 得 V V F ( k k L kv ) 于是 V [ ( k k L kv ) ] 为偶数 F 800 求一切满足如下条件的正整数 (a,b): ab a b, 请给出过程, 谢谢. ( 数论 ) ( 竟赛 ) 解 :( ) 若有正整数 a, b, 使 ab a b 则存在正整数 k, 使 a b k( ab ) 下面研究在 k 固定时方程 x y k( xy ) 的整数解 ( x, y) 的情形易知 ( x, y) (0,0) 若不然 k 0 与 k >0 不符于是有 x y > 0 又因为 x y k( xy ) 故有 xy >, 考虑到 x, y 是整数, 进而有 xy 0 () 下面证明关于 x y k( xy ) 的所有整数解 ( x, y) 不可能都有 xy > 0 假设对于的任意一个解 ( x, y) 都有 xy > 0 不妨设 x, ) 是所有整数解中满足 x y 0, 并且 x y 取得最小值的一个解 ( y 8 > 把看成关于 x 的一元二次方程, 按 x 整理得 x kxy y k 0 由假设得关于 x 的方程 x kxy y k 0 有一为 x, 设另一根为 x 由韦达定理得 x x ky, x x y k 由得 x ky x也是整数, 于是 ( x, y ) 也是方程的一个整数解

9 由假设得 x y 0, 故 x 0, > > y k x k k 由得 x x < x x x x 于是 < x, 这与 x, ) 使 x y 取得最小值相矛盾 x y y ( y 因此假设对于的任意一个解 ( x, y) 都有 xy > 0 是不对的由于 x y k( xy ) 的整数解 ( x, y), 有 xy 0 因此只要有整数解, 必存在有使 xy 0 的整数解不妨设其中之一解为 0, y ) ( y > 0), 于是关于 x 的方程 x kxy y k 0 ( 有一根为 0, 于是另一根 x ( 正整数 ) 满足 y k 0, 且 x ky 设 y ( 为正整数 ) x 于是得方程 x kxy y k 0 的所有正整数是 y x 同理可得方程 y kx y x k 0 的所有正整数是 y 综上所述本题的所有解为 a b a 或 b N 9

10 85 ( 数论 ) ab0 的正整数解 0 b 80 4b b 0 b 0 解 : a 40 b b 0 设 k,( k z), 则 b k 0( k z) b 0 k 0 0 于是 a 40 b 40 (k 0) 0 k 因为 a > 0, b > 0, 故 a 0 k 且 k 0 > 解得 < k <, 因此 k 或 0 或原不定方程的正整数解是 945 已知 p > q 0, 且为整数. 求证 : a a 0 a 或或 b b 0 b p ) 对于任意正整数 q, (p,q) 为唯一整数对. ( ) 证明 :( ) 当时, 0, 有唯一的整数对 (,0) p ) () 假设当 k 时, 有唯一整数对 ( p, q) ( p > q 0 ) 使 k q p ) 则当 k 时,k q 若 0 q p, 则 q p < p, 于是有整数对 ( p, q ) 满足条件 p ) 若 q p, 则 k p 对 ( p,0) 满足条件 p ) ( p )[( p ) ] 0 于是有整数我们证出了当 k 时有一对整数对 ( p, q) ( p > q 0 ) 满足条件 p ) 设当 k 时, 有整数对 ( p, q) ( p > q 0 ) 使 k q 成立, p ) 若 q 就有整数对 ( p, q ) 使 k q, ( p )( p ) 若 q 0 有整数对 ( p, p ) 使 k p 由归纳法假设知当 k 时, 有唯一整数对 ( p, q) 满足条件, 因此当 k 时也只能有唯一的整数对 ( p, q) ( p > q 0 ) 满足条件综上, 当 N 时命是总成立 0

11 08 把的次方表示成 k 个连续正整数的和, 则项数 k 的最大值为分析 : 联想到连续正整数的组成等差数列, k( k ) k 个连续正整数的和应有的形式即 k ( k ) () 当 k 为奇数时 k, k 于是 k 于是 k k >, <, 5, 于是 k 5 4 () 当 k 为偶数时 k, k k 于是于是 > k, 5, 此时 k 5 486>4 因此项数 k 的最大值是 ( 60) 此时 L ( 竟赛 ) 以下 8 个数据 : a 5., a 6., a 65., a 4., a 5 6., a 5 8., a 86., a 99., 它们的和为 0, 若整数 A (,, L8) 的和仍是 0, 则误差, A a 的最大值的最小值为解 : 当 A (,, L8) 相对集中于 (,, L8) 周围 A a (,, L8) 最大值会较小由于 a (,, L8) 在. 5 左右于是整数 A (,, L8) 就应取或 4, 由于 A 0 于是可取个与 6 个 4, a 当 A A, A A A A A A 4时 max A a 当 A A, A A A A A A 4 时 max A a 等等, 比较得 max A a 最小值为 0. 6

求出所有的正整数 n 使得 20n + 2 能整除 2003n n 20n n n 20n n 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y =

求出所有的正整数 n 使得 20n + 2 能整除 2003n + 2002 n 20n + 2 2003n + 2002 n 20n + 2 2003n + 2002 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y = y x y 对于任意正整数 n, 记 n 的所有正约数组成的集合为 S n 证明 : S n 中至多有一半元素的个位数为