離散數(shù)學(xué)(劉任任版)第4章答案

1、習(xí)題四1.2.3.(1). 設(shè)A=1,2,200。(2)設(shè)有52個(gè)整數(shù)a1,a2, ,a52。 若存在1=ij=52, 使ai=aj, 則100|(ai-aj)。 否則不妨設(shè)a1a2a52 。 令bi=a52-ai, i=1, ,51 (1) cj=a52+aj, j=1, ,51 (2) 假設(shè)結(jié)論不成立, 則bi,cj均不能被100整除。設(shè)100除bi余數(shù)為ri, i=1,51 ; 100除ci余為si, i=1,51 ，則 1=ri,si=99 。由于(1), (2)式共有102個(gè), 因此，余數(shù)也有102個(gè)。故由抽屜原理知必有i, j使得 ri=rj (i=ij=51) (a-1)或 ri

2、=sj (1=ij=51) (b-1)或 si=sj (1=ij=51) (c-1)即 (a52-ai)-100ki=(a52-aj)-100kj (a-2)或 (a52-ai)-100ki=(a52+aj)-100kj (b-2)或 (a52+ai)-100ki=(a52+aj)-100kj (c-2)于是有 (ai-aj)=100*(kj-ki)或 (a-3) (ai+aj)=100*(kj-ki)或 (b-3) (ai-aj)=100*(ki-kj) 或 (c-3)此與假設(shè)矛盾。故本題得證。(其中ki,kj是商數(shù))4證明: (1) 對(duì)任意集合A, 因?yàn)锳A, 所以|A|=|A| 。 (2

3、) 若|A|=|B| , 則AB, 即存在雙射 于是 存在且為雙射, 故BA, 即 |B|=|A| 。 (3) 若 |A|=|B|,|B|=|C|,則存在雙射 于是是雙射，因此，AC。故 |A|=|C|。 再證定理4.2.3。 (1)令 ， 于是 是單射。故|A| |A|. (2)設(shè)|A| |B| 且 |B| |A|, 則存在單射: , 若 不是滿射, 則可推得 不是單射, 矛盾。故 必為雙射, 即|A|=|B|。(3)設(shè)|A| |B| 且 |B| |C|, 則存在單射 , (由習(xí)題3的第4題) 是單射。故 |A| |C|。 5證明: 必要性。 設(shè) |B| |A| , 則存在單射 (1)若 是滿射, 則 是雙射，因此 也是滿射。 (2)若 不是滿射, 因?yàn)锽 ,任取 ，令 如下： 顯然， 是A到B的滿射。充分性。 設(shè) 是滿射, 則 ，于是|B|=| (A)| |A|, 故|B| |A|。 6證明: 先證任何無限集均包含一個(gè)可數(shù)子集。 設(shè)A為無限集, 任取 , 因A無限, 故存在 如此下去, 有 , 顯然 是A的可數(shù)子集。令 則 再證存在雙射 令顯然， 是A到B的雙射。故結(jié)論成立。 78題6已證。9.將NN的元素如下排列,