離散數(shù)學(xué)習(xí)題二參考答案

1、離散數(shù)學(xué)習(xí)題二參考答案第二節(jié) 容斥原理和抽屜原理1.從1到500中,有多少數(shù)能被3或5整除？只能被3或5整除的數(shù)又有多少個(gè)解：設(shè)a=“3的倍數(shù)”；b=“5的倍數(shù)”，則能被3或5整除的個(gè)數(shù)n；只能被3或5整除的數(shù)：m2.(1)一個(gè)班級(jí)有50名學(xué)生，第一次考試有26名得a等，第二次考試有21名得a，若兩次考試中都沒有得a的有17名，那么兩次都得a的有多少名？ (2)若50名在兩次考試中得a的人數(shù)相同，兩次中恰有一次得a的為40名，兩次中都沒得a的有4名，那么僅在第一次得a的有多少名。解：設(shè)a=“第一次考試得a等”，b=“第二次考試得a等”，則(1)|a|=26，|b|=21，由，所以兩次都得a的人

2、數(shù)：n=|ab|=50-26-21+17=14（人）(2)由題意得：，又，所以，即僅在第一次中得a的人數(shù)m=。3.在1到3000的整數(shù)中，不能被3，5，7中任何一個(gè)數(shù)整除的有多少個(gè)？又有多少個(gè)數(shù)能被3整除，但不能被5和7整除？解：設(shè)a=“3的倍數(shù)”；b=“5的倍數(shù)”，c=“7的倍數(shù)”，則不能被3，5，7中任何一個(gè)數(shù)整除的個(gè)數(shù)：n=(個(gè)能被3整除，但不能被5和7整除的個(gè)數(shù)m=4.分母是1986的最簡真分?jǐn)?shù)共有多少個(gè)？解：1986=2×3×331，設(shè)a=“1986內(nèi)2的倍數(shù)”；b=“1986內(nèi)3的倍數(shù)”；c=“1986內(nèi)331的倍數(shù)”，則|abc|=|a|+|b|+|c|-|a

3、b|-|ab|-|bc|+|abc|=所以，分母是1986的最簡真分?jǐn)?shù)的個(gè)數(shù)n=1985-1325=660（個(gè)）。5.50名同學(xué)中，愛好美術(shù)的占總數(shù)的3/5，愛好音樂的比愛好美術(shù)的多3名，音樂和美術(shù)都不愛好的人數(shù)比兩項(xiàng)都愛好的人數(shù)的1/3還多1名，問對(duì)兩項(xiàng)都愛好的同學(xué)有多少名？解：設(shè)a=“愛好美術(shù)的人”；b=“愛好音樂的人”，則（人），|b|=|a|+3=33（人），又，所以，50-30-33+|ab|-1=|ab|/3，|ab|=21答：兩項(xiàng)都愛好的同學(xué)有21名。6.證明：在任意m個(gè)相繼的整數(shù)中，存在一個(gè)整數(shù)能被m整除。證明：任意m個(gè)相繼的整數(shù)任取兩個(gè)整數(shù)它們的差一定小于m,即差一定不是m的

4、倍數(shù).(反證)倘若這m個(gè)相繼的整數(shù)中不存在一個(gè)整數(shù)是m的倍數(shù),那么由抽屜原理一定存在兩個(gè)整數(shù)它們對(duì)于除以m的余數(shù)相同,它們的差一定是m的倍數(shù),與前的結(jié)論矛盾.7.證明對(duì)于任意的整數(shù)n，都存在著n的一個(gè)倍數(shù)sn，sn中只含數(shù)字0和7。證明：設(shè)，（1）若存在一個(gè)k,使是n的倍數(shù)，則命題成立，（2）若不存在這樣的k，由抽屜原理在這n個(gè)數(shù)中，一定存在兩個(gè)和，它們除以n的余數(shù)相同，那么-=一定是n的倍數(shù)。9.把一個(gè)圓周分為36段，將36個(gè)數(shù)字1，2，3，4，36，任意地標(biāo)在每段上，使每一段恰有一個(gè)數(shù)字,證明一定在相鄰的三段，它們的數(shù)字的和至少是56。證明：設(shè)表示第k段上的數(shù)字，k=1，2，3，36。并，

5、再設(shè)，則顯然36個(gè)數(shù)的和是1998，一定有一個(gè)數(shù)大于或等于1998÷36=55.5，即一定在相鄰的三段，它們的數(shù)字的和至少是56。10.證明：在任意選取n+1個(gè)整數(shù)中，存在兩個(gè)整數(shù)，它們的差能被n整除。證明：這n+1個(gè)數(shù)除以n后的余數(shù)只有n種情況，有抽屜原理可知，一定有兩個(gè)數(shù)除以n后的余數(shù)是相同的，這兩書的差就一定是n的倍數(shù)，即它們的差能被n整除11.證明：一個(gè)有理數(shù)的十進(jìn)位小數(shù)展開式，自某一位后變?yōu)橹芷诘难h(huán)。證明：一個(gè)有理數(shù)一定可以寫成分?jǐn)?shù)形式任取一個(gè)數(shù)，除以n后的余數(shù)一定是唯一的，并只有n種，所以當(dāng)m除以n時(shí)，余數(shù)在若干次數(shù)后一定重復(fù)，這是商也就重復(fù)了，即自某一位后變?yōu)橹芷诘难?/p>

6、環(huán)。12.一個(gè)人步行了十小時(shí)，共走了45公里，已知他第一小時(shí)走6公里，而最后一小時(shí)只走3公里，證明一定存在相鄰的兩小時(shí)內(nèi)至少走了9公里。（提示：把相鄰兩小時(shí)走的總路程看成盒子）證明：設(shè)表示第k分鐘走的路程，k=1,2,3,4,5,6,7,8,9，10. 并，所以，再設(shè)，則顯然9個(gè)數(shù)的和是81，一定有一個(gè)數(shù)大于或等于9，即一定存在相鄰的兩小時(shí)內(nèi)至少走了9公里。13.從整數(shù)1，2，3，200中，任意選取101個(gè)數(shù)，證明在這101個(gè)整數(shù)中，存在兩個(gè)整數(shù)，使得一個(gè)能被另一個(gè)整除。（提示：把整數(shù)寫成2n a的形式，其中a是奇數(shù)，把a(bǔ)看成盒子）證明：任取一個(gè)200以內(nèi)的整數(shù)n一定能寫成2n a的形式，其中

7、a是奇數(shù)。如果兩數(shù)的a相等，則兩數(shù)一定成倍數(shù)關(guān)系。由于200以內(nèi)只有100個(gè)奇數(shù)，所以任意取出101個(gè)整數(shù)，必有兩個(gè)數(shù)有相同的a，即這兩數(shù)一定成倍數(shù)關(guān)系。14.設(shè)有一個(gè)n個(gè)正整數(shù)序列，其中恰含n個(gè)不同的正整數(shù)，證明若n2n，則在這序列中存在著連續(xù)的一段，其中個(gè)數(shù)的乘積是一個(gè)完全平方數(shù)。例如在含3，7，5的序列3，7，5，3，7，3，5，7中，7，5，3，7，3，5一段中，7×5×3×7×3×5=（7×3×5）2。解：設(shè)a為n個(gè)給定的不同正整數(shù)所成的集合，即a=，任取一個(gè)有n個(gè)數(shù)的序列 ：，其中表示a中任一個(gè)元素，再令是n個(gè)序列， c=，|c|=n，（相當(dāng)與n個(gè)蘋果）再設(shè)一集合b=，所以|b|=（相當(dāng)于個(gè)抽屜）建立一個(gè)從c到b的一個(gè)對(duì)應(yīng)：中如有奇數(shù)個(gè)，則取1，否則取2，同樣中如有奇數(shù)個(gè)，則取1，否則取2，（相當(dāng)于把c中元素（蘋果）放到b的元素（抽屜）中），由于|c|=n，由抽屜原理一