第1章习题1.1 1.用2种颜色的珠子做成有5颗珠子项链,问可做出多少种不同的项链? 解在学群论前我们没有一般的方法,只能用枚举法。用笔在纸上画一下,用黑 白两种珠子,分类进行计算:例如,全白只1种,四白一黑1种,三白二黑2 种,…等等,可得总共8种。 2.对正四面体的顶点用2种颜色着色,有多少种本质上不同的着色方法? 解类似第1题,用枚举法可得5种。 3.有4个顶点的图共有多少个?互不同构的有多少个? 解由本节内容,有4个顶点的图共有64个图。用分类计数的方法可得共有11 个互不同构的图 4.如何用圆规5等分一个圆 解用初等数学的方法求五边形的边长:作一个顶角为36°、腰长为1的等腰三 角形,设底边长为a,则a就是十边形的边长,以a为半径以单位圆周上任意 点为圆心在圆周上交出两点,则这两点之间的距离就是五边形的边长。那么a 怎么求呢?只要在那个等腰三角形上作一条补助线#0;底角的角平分线,再利用 5-1 相似三角形边长成比例的关系,可得2,因而a就可作出了 5.用根式表示3次和4次代数方程的根。 查看数学手册。因公式较复杂,不在这里列出了。 第1章习题1.2 1设4<∞用二项式定理证明24-24 证设油于元子集的个数 所以全部子集的个数(包括空集)为 1+1) 即|24-=2
第 1 章 习题 1.1 1. 用 2 种颜色的珠子做成有 5 颗珠子项链，问可做出多少种不同的项链？ 解 在学群论前我们没有一般的方法，只能用枚举法。用笔在纸上画一下，用黑 白两种珠子，分类进行计算：例如，全白只 1 种，四白一黑 1 种，三白二黑 2 种，…等等，可得总共 8 种。 2．对正四面体的顶点用 2 种颜色着色，有多少种本质上不同的着色方法？ 解 类似第 1 题，用枚举法可得 5 种。 3. 有 4 个顶点的图共有多少个？互不同构的有多少个？ 解 由本节内容，有 4 个顶点的图共有 64 个图。用分类计数的方法可得共有 11 个互不同构的图。 4. 如何用圆规 5 等分一个圆？ 解 用初等数学的方法求五边形的边长：作一个顶角为 36°、腰长为 1 的等腰三 角形，设底边长为 a，则 a 就是十边形的边长，以 a 为半径以单位圆周上任意一 点为圆心在圆周上交出两点，则这两点之间的距离就是五边形的边长。那么 a 怎么求呢？只要在那个等腰三角形上作一条补助线�底角的角平分线，再利用 相似三角形边长成比例的关系，可得 ，因而 a 就可作出了。 5．用根式表示 3 次和 4 次代数方程的根。 查看数学手册。因公式较复杂，不在这里列出了。 第 1 章 习题 1.2
2一个班有93%的人是团员80%的人担任过社会工作,70%的人受过奖励问 (1)受过奖励的团员至少占百分之几? 2)三者兼而有之的人至少占百分之几? 解设A为团员的集合,B为担任过社会工作的人的集合,C为受过奖励的人 的集合由包含与排斥原理,可得 (A∩C-4+-A∪c293+70-100=63 所以受过奖励的团员至少占63% (2)A∩B∩C-+|+1-AU-Bucl-Aq+ AuBuC 因为-A∪C|+ AUBUC20.所以 1A∩B∩C24+1+(-AUB-Bu293+80+70-100-100=43 故三者兼而有之的人至少占43% 3求不大于1000的正整数中 (1)不能被5,68中任何一个整数整除的个数 (2既非平方数也非立方数的个数 解利用包含与排斥原理 设为不大于100的正整数集合,A为不能被5整除的正整数集合,B为不能被 整除的正整数集合,C为不能被8整除的正整数集合则 1000 1000 =166 =125 并可求出M时-0-31c-101-4ne--23 2n412其3)录小公记号于是得别所的个数为 10001UB∪C-=100014--+∩B+Bc+A∩c|-A∩BnCl 1000-200-166-125+33+41+25-8=600 (2)设A为x中非平方数的集合,B为中非立方数的个数则 4-√1000-3112=31000-10.A∩-9100-3 故得所求的个数为 1000-A∪B2|=1000-31-10+3=962
4设A=m,|-n求 1)4到的的单射有多少个 (2)当m=3,n=2时,A到B的满射有多少个?(对一般情形求满射数的问题可参看6]2.52-53) 解(1)显然当m>x时,不存在A到B的单射当m≤n时,A到单射的个数等于选排列数 M=n(n-1)…(n-m+1) (2)求满射的个数的问题在里讨论如未学组合数学目前只能用玫举法 不难列出所有的满射为 x122小12 内4b2-/=1a2a3 故共有6个 5证明(0,1)与(-∞,+∞)等势 证作映射f:xH血x 可证是单射任取x2x2∈(0,1,由 为=、x2分1万1-x2x1-=x2-xx2→石=2 x1 所以是单射 再证是满射:任取y∈(-∞,+∞),令y=加,可解出x ∈(01)使 f(x)=y,故是满射 综上提是双射因此(0,1)与(-∞,+a)等势 6.f:A→B,S≤A举例说明f[f(∞]-S是否成立? 解不一定成立(意符号的意义) 先看一个反例例如∫:x→x2(R→R) 取S={12,则f()={14.但f[f()={±1,±2)≠S 般的规律是当是单射时,f(]- 证明如下 因为是单射vx∈s如(x)=a,则a的原像x是唯一的因而 f[f(x)]=x,所以f(S)]
7设A<∞,f:A→A证明以下三个命题等价: (1)是单射 (2)是满射 (3)是双射 证用循环证法 (1)→(2):因为是单射且A有限,故有(4-4所以是满射 2)→(3:因为是是满射故有(A=A不妨设令A={12,…,n, 可得{1,2…,}=A 所以12,…互不相同,是单射 (3)→(:显然 8设A≠②,证明不存在A到A的幂集P(A的双射 证用反证法 假设存在A到A的幂集P(A)的双射f:a→f(a)=S∈P(4 取子集T-{x∈Ax≠显然7cA或T=因而T∈F(4 由于是双射,且A≠②,必有b∈A使f(b)==T则 当b∈T时有bg=T,矛盾 当bgT时有b∈S8=7矛盾 得证 第1章习题1.3
第 1 章 习题 1.3
1A={12345在24中定义~8~7兮阳-四 证明~是等价关系,写出等价类和商集 证易证~满足等价关系的三个条件略) 等价类为-,-1{2)3.4),59 12)={12).1313..4.15,{2,3,24,(25)1343{4 123-{123.(124…,34.5) 12,34}={12,34.…{2,345 A-A 商集为2-{22302342 2S={0.1,…,n,:A→秩(A(Mn(R)→S) 求所决定的等价关系等价类和商集 解所决定的等价关系~为A~B台秩(A=秩(B) 等价类为 AeM,(秩(4)=)k=01,…,n 0 商集为23 =0,1,…,2 3在M,(C中定义二元关系~A~B台3P使P1AP=B, 证明~是等价关系,并选等价类的代表元最简单 证易证~满足等价关系的三个条件略) 等价类的代表元可选约当标准形矩阵
4.S阶实对称矩阵的集合定义~A~B3可逆阵使PAP=B E明是等价关系并求4 证易证~满足等价关系的三个条件(略) 由于8-02 <A+isn 所以m+ 5.举一个偏序集但不是全序集的例子,并画图 解考虑到画图的方便,可举有限集的例子,例如:有限集的幂集对包含关系所 构成的偏序集,有限整数集对整除关系所构成的偏序集。 详解略。 6已知两个偏序集的图形分别写出偏序集的偏序关系 解按偏序的定义,可直接列出有偏序关系的元素对 (a)的偏序集可表为(S,s)其中 S-a, b, c, d,e,f, g), s-ab, a<c, b<d, be, c<f, c<g) ()的偏序集可表为r,,其中 T=a, b, c, d, e,f), s=a<b, a<c, b<d, be, d<f, e<f
5. 举一个偏序集但不是全序集的例子，并画图。 解 考虑到画图的方便，可举有限集的例子，例如：有限集的幂集对包含关系所 构成的偏序集，有限整数集对整除关系所构成的偏序集。 详解略
7.用两种方法定义z的序使它成为一个良序集 解除了普通序外我们可重新定义序首先要使整个集合有最小元例如 (1)定义z中的偏序关系≤为 a<b刚<P或=且a<b, b台a=b 其中右端的<,=为普通的序关系 按此序排列的整数集合为 0,-1,1,-2,2,-3,3,…… 下证它是良序集首先显然他它是全序集其次证明它的任一子集都有最小元 设$是(z,s的任一非空子集任取a∈S由于在(z,s冲≤a的元素为有限个故在S 中≤a的元素也为有限个,可找到最小元此最小元也是的最小元 所以z,是良序集 (2)(1)定义z中的偏序关系≤为 a<b台k-1<p-1或k-1--且a<b b今a=b 其中右端的<,=为普通的序关系 按此序排列的整数集合为 1,0,2,-1,3,-2,4,-3,5,…… 类似可证(2,是良序集 第1章习题1.4 1.a=493,b=391,求(a,b),[a,b]和p,q 解方法一、辗转相除法。列以下算式: a=b+102 b=3×102+85 102=1×85+17 由此得到(a,b)=17,[a,b]=a×b/17=11339 然后回代:17=102-85=102-(b-3×102)=4×102-b=4×(a-b)-b=4a-5b. 所以p=4,q=-5
第 1 章 习题 1.4 1. a=493, b=391, 求(a,b), [a,b] 和 p, q。 解 方法一、辗转相除法。列以下算式： a=b+102 b=3×102+85 102=1×85+17 由此得到 (a,b)=17, [a,b]=a×b/17=11339。 然后回代：17=102-85=102-(b-3×102)=4×102-b=4×(a-b)-b=4a-5b. 所以 p=4, q=-5
方法二、大衍求一术。 公式与计算表格如下 d K rk-2=qkrk-Itrk 1 a=493 b=391 102 1 3(n) 17 4 4(n+1) 由此求得n=3 p=(-1)"cn=4,q=(-1)"d=-5。 2.求n=504的标准分解式和φ(n). 解504=2×32×7 φ(504)=504(1-1/2)(1-1/3)(1-1/7)=144. 3.一队伍成10行、15行、18行、24行均成方形,问需要多少人? 解求最小公倍数:作以下算式 2231824
方法二、大衍求一术。 公式与计算表格如下： k qk rk-2=qkrk-1+rk rk ck ck=qkck-1+ck-2 dk dk=qkdk-1+dk-2 -1 a=493 1 0 0 b=391 0 1 1 1 102 1 1 2 3 85 3 4 3(n) 1 17 4 5 4(n+1) 5 0 由此求得 n=3 d=(a,b)=17, p=(-1)n-1 cn=4, q=(-1)n dn=-5。 2. 求 n=504 的标准分解式和φ(n). 解 504=23×3 2×7. φ(504)=504(1-1/2)(1-1/3)(1-1/7)=144. 3. 一队伍成 10 行、15 行、18 行、24 行均成方形，问需要多少人？ 解 求最小公倍数：作以下算式 5 | 10, 15, 18, 24 2 | 2 3 18 24 3 | 1 3 9 12
1134 得[10,15,18,24]=5×2×3×3×4=360。 所以需要360k(k>0)人。 4.方程ax+by=c在整数范围内有解的充分必要条件是(a,b)|c 证必要性:由于(a,b)|a,(a,b)|b,所以(a,b)|ax+by=c 充分性:设d=(a,b),于是存在整数p,q使pa+qb=d。 又由dc,可设c=dh。因而有 aph+bgh=dh=c 所以x=pbh,y=qh就是一个解 5.分别解同余方程:(1)258x≡131(mod348).(2)56x=88(mod96) 解由书中解同余方程的四个步骤求解。 (1)求(a,m)=(258,348)=6 6不能整除131,所以此同余方程无解。 (2)求(a,m)=(56,96)=8,由于8能整除88,所以此同余方程有解。 a1=56/8=7,b:=88/8=11,m=96/8=12. 用辗转相除法求p,q满足pa+qm=1,得p=-5 所以方程的解为x≡pb(modm)≡-5×11(mod12)≡5(mod12)。 或x=5+12k(k为任意整数) 6.解同余方程组 x≡3(mod5) x≡7(mod9) 解按解同余方程组的三个步骤:
1 1 3 4 得 [10，15，18，24]=5×2×3×3×4=360。 所以需要 360k(k>0) 人。 4. 方程 ax+by=c 在整数范围内有解的充分必要条件是 (a,b)|c 。 证 必要性：由于 (a,b)|a, (a,b)|b，所以 (a,b)|ax+by=c 。 充分性：设 d=(a,b), 于是存在整数 p, q 使 pa+qb=d 。 又由 d|c ，可设 c=dh 。因而有 aph+bqh=dh=c 。 所以 x=ph , y=qh 就是一个解。 5. 分别解同余方程：（1）258x≡131(mod348). (2) 56x=88(mod96). 解 由书中解同余方程的四个步骤求解。 （1）求 (a,m)=(258,348)=6, 6 不能整除 131，所以此同余方程无解。 （2）求 (a,m)=(56,96)=8，由于 8 能整除 88，所以此同余方程有解。 a1=56/8=7, b1=88/8=11, m1=96/8=12. 用辗转相除法求 p,q 满足 p a1+q m1=1，得 p=-5。 所以方程的解为 x≡pb1 (mod m1) ≡-5×11(mod12) ≡5(mod12)。 或 x=5+12k(k 为任意整数)。 6. 解同余方程组： x≡3(mod5) x≡7(mod9) 解 按解同余方程组的三个步骤：
首先,计算M=5×9=45,M1=9,M=5 其次,解两个一次同余式,由于这两个同余式有其特殊性:右端都是1,且 (a,m)=1。因而 有时可用观察法得到pa+qm=1,从而得到p。 1)9x≡1(mod5) 观察得到-9+2×5=1,p=-1. 所以此一次同余式的一个特解为c=-1≡4(mod5) 2)5x≡1(mod9) 观察得到2×5-9=1,p=2. 所以此一次同余式的一个特解为c=2(mod9) 最后,将得到的一次同余式的一个特解代入公式,得到同余方程组的解: x=bclM+b2cMl=3×4×9+2×7×5(mod45)=43(mod45)。 7.5行多1,6行多5,7行多4,11行多10,求兵数 解设兵数为x,则x满足以下同余方程组: x=l(mod) x=5(mod) x=4 (mod7) x=10(mod1) 按解同余方程组的步骤,计算如下: M=5×6×7×11=2310,M=462,M=385,M=330,M=210. 分别解以下一次同余式 462x=1(mod5),得c=3. 385x=1(mod6),得c2=1
首先，计算 M=5×9=45, M1=9, M2=5. 其次，解两个一次同余式，由于这两个同余式有其特殊性：右端都是 1，且 (a,m)=1。因而 有时可用观察法得到 pa+qm=1,从而得到 p。 1) 9x≡1(mod5), 观察得到 -9+2×5=1, p=-1. 所以此一次同余式的一个特解为 c=-1≡4(mod5). 2)5x≡1(mod9), 观察得到 2×5-9=1, p=2. 所以此一次同余式的一个特解为 c=2(mod9). 最后，将得到的一次同余式的一个特解代入公式，得到同余方程组的解： x=b1c1M1+b2c2M2=3×4×9+2×7×5(mod45)=43(mod45)。 7. 5 行多 1，6 行多 5，7 行多 4，11 行多 10，求兵数。 解 设兵数为 x，则 x 满足以下同余方程组： x=1(mod5) x=5(mod6) x=4(mod7) x=10(mod11) 按解同余方程组的步骤，计算如下： M=5×6×7×11=2310, M1=462, M2=385, M3=330, M4=210. 分别解以下一次同余式： 462x=1(mod5), 得 c1=3. 385x=1(mod6), 得 c2=1
