抽屜原理的典型問題-文庫(kù)吧在線文庫(kù)
【正文】 除以某個(gè)自然數(shù)m的余數(shù)分為m類，叫做m的剩余類或同余類，用[0]，[1]， [2]，…，[m1]，例如[1]中含有1，m+1，2m+1，3m+1，….在研究與整除有關(guān)的問題時(shí)，可以證明：任意n+1個(gè)自然數(shù)中，總有兩個(gè)自然數(shù)的差是n的倍數(shù)。分析與解答首先要確定3枚棋子的顏色可以有多少種不同的情況，可以有：3黑，2黑1白，1黑2白，3白共4種配組情況，至少有兩個(gè)小朋友摸出的棋子的顏色在同一個(gè)抽屜里，也就是他們所拿棋子的顏色配組是一樣的。設(shè)這6位科學(xué)家為B，C，D，E，F(xiàn)，G，討論的是甲問題?，F(xiàn)從題目中的15個(gè)偶數(shù)中任取9個(gè)數(shù)，由抽屜原理(因?yàn)槌閷现挥?個(gè))，這兩個(gè)數(shù)的和是34。 分析與解答共有n位校友，每個(gè)人握手的次數(shù)最少是0次，即這個(gè)人與其他校友都沒有握過(guò)手?！ ⌒问揭唬鹤C明：設(shè)把n+1個(gè)元素分為n個(gè)集合A1，A2，…，An，用a1，a2，…，an表示這n個(gè)集合里相應(yīng)的元素個(gè)數(shù)，需要證明至少存在某個(gè)ai大于或等于2(用反證法)假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai2，則因?yàn)閍i是整數(shù)，應(yīng)有ai≤1，于是有： a1+a2+…+an≤1+1+…+1=n 形式二：設(shè)把n?m+1個(gè)元素分為n個(gè)集合A1，A2，…，An，用a1，a2，…，an表示這n個(gè)集合里相應(yīng)的元素個(gè)數(shù)，需要證明至少存在某個(gè)ai大于或等于m+1。.某兩類各含兩個(gè)數(shù)，第三類包含一個(gè)數(shù). 若是第一種情況，就在至少包含三個(gè)數(shù)的那一類中任取三數(shù)，其和一定能被3整除。 這相當(dāng)于把367個(gè)東西放入 366個(gè)抽屜，至少有2個(gè)東西在同一抽屜里在第二個(gè)結(jié)論中，不妨想象將5雙手套分別編號(hào)，即號(hào)碼為1，2，...，5的手套各有兩只，同號(hào)的兩只是一雙。許多有關(guān)存在性的證明都可用它來(lái)解決。不論哪種情形發(fā)生，都符合問題的結(jié)論。否則連一條藍(lán)線?！薄 ±蒙鲜鲈砣菀鬃C明：“任意7個(gè)整數(shù)中，至少有3個(gè)數(shù)的兩兩之差是3的倍數(shù)。” 大家都會(huì)認(rèn)為上面所述結(jié)論是正確的。(用反證法)假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai 所以，假設(shè)不成立，故必有一個(gè)i,在第i個(gè)集合中元素個(gè)數(shù)ai≥qi 形式五：證明：(用反證法)將無(wú)窮多個(gè)元素分為有限個(gè)集合，假設(shè)這有限個(gè)集合中的元素的個(gè)數(shù)都是有限個(gè)，則有限個(gè)有限數(shù)相加，所得的數(shù)必是有限數(shù)，這就與題設(shè)產(chǎn)生矛盾，所以，假設(shè)不成立，故必有一個(gè)集合含有無(wú)窮多個(gè)元素?！ 〕閷显怼 “寻藗€(gè)蘋果任意地放進(jìn)七個(gè)抽屜里，不論怎樣放，至少有一個(gè)抽屜放有兩個(gè)或兩個(gè)以上的蘋果?！ ±?： 從1到20這20個(gè)數(shù)中，任取11個(gè)數(shù)，必有兩個(gè)數(shù)，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)?！ ∪鬋，D，E中有兩人也討論乙問題，則結(jié)論也就成立了。例3′(六人集會(huì)問題)證明在任意6個(gè)人的集會(huì)上，或者有3個(gè)人以前彼此相識(shí)，或者有三個(gè)人以前彼此不相識(shí)。 同理，剩下的8個(gè)任意整數(shù)中，由例2，必存在：3 | a4+a5++a5+a6=b2。 [證明](反證法)：若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符，故不可能.原理1 2都是第一抽屜原理的表述第二抽屜原理： 把(mn1)個(gè)物體放入n個(gè)抽屜中，其中必有一個(gè)抽屜中至多有(m—1)個(gè)物體。抽屜原理的一般含義為：“如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋果就可以代表一個(gè)元素，假如有n+1或多于n+1個(gè)元素放到n個(gè)集合中去，其中必定至少有一個(gè)集合里至少有兩個(gè)元素?！±? 證明：任取8個(gè)自然數(shù)，必有兩個(gè)數(shù)的差是7的倍數(shù)?！±?：假設(shè)在一個(gè)平面上有任
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1