抽屜原理的典型問題-閱讀頁
2025-04-09 02:31本頁面
【正文】 {14，2｝，{13，1｝?！ ±?： 從1到20這20個(gè)數(shù)中，任取11個(gè)數(shù)，必有兩個(gè)數(shù)，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)。 從這10個(gè)數(shù)組的20個(gè)數(shù)中任取11個(gè)數(shù)，根據(jù)抽屜原理，所以這兩個(gè)數(shù)中，其中一個(gè)數(shù)一定是另一個(gè)數(shù)的倍數(shù)?！ 》治雠c解答共有n位校友，每個(gè)人握手的次數(shù)最少是0次，即這個(gè)人與其他校友都沒有握過手。如果有一個(gè)校友握手的次數(shù)是n1次，、 …、n2，還是后一種狀態(tài)…、n1，到會(huì)的n個(gè)校友每人按照其握手的次數(shù)歸入相應(yīng)的“抽屜”，根據(jù)抽屜原理，至少有兩個(gè)人屬于同一抽屜，則這兩個(gè)人握手的次數(shù)一樣多?！ 〕閷显怼 “寻藗€(gè)蘋果任意地放進(jìn)七個(gè)抽屜里，不論怎樣放，至少有一個(gè)抽屜放有兩個(gè)或兩個(gè)以上的蘋果。它是組合數(shù)學(xué)中一個(gè)重要的原理?！ ⌒问揭唬鹤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è)ai≥m+1 高斯函數(shù)：對(duì)任意的實(shí)數(shù)x,[x]表示“不大于x的最大整數(shù)”. 例如：[]=3，[]=2，[]=3，[7]=7，……一般地，我們有：[x]≤x[x]+1 形式三：證明：設(shè)把n個(gè)元素分為k個(gè)集合A1，A2，…，Ak，用a1，a2，…，ak表示這k個(gè)集合里相應(yīng)的元素個(gè)數(shù)，需要證明至少存在某個(gè)ai大于或等于[n/k]。(用反證法)假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai 所以，假設(shè)不成立，故必有一個(gè)i,在第i個(gè)集合中元素個(gè)數(shù)ai≥qi 形式五：證明：(用反證法)將無窮多個(gè)元素分為有限個(gè)集合，假設(shè)這有限個(gè)集合中的元素的個(gè)數(shù)都是有限個(gè)，則有限個(gè)有限數(shù)相加，所得的數(shù)必是有限數(shù)，這就與題設(shè)產(chǎn)生矛盾，所以，假設(shè)不成立，故必有一個(gè)集合含有無窮多個(gè)元素。.某一類至少包含三個(gè)數(shù)。.某兩類各含兩個(gè)數(shù)，第三類包含一個(gè)數(shù). 若是第一種情況，就在至少包含三個(gè)數(shù)的那一類中任取三數(shù)，其和一定能被3整除?！薄 皬娜我?雙手套中任取6只，其中至少有2只恰為一雙手套?！薄 〈蠹叶紩?huì)認(rèn)為上面所述結(jié)論是正確的。它的內(nèi)容可以用形象的語言表述為： “把m個(gè)東西任意分放進(jìn)n個(gè)空抽屜里(mn)，那么一定有一個(gè)抽屜中放進(jìn)了至少2個(gè)東西。 這相當(dāng)于把367個(gè)東西放入 366個(gè)抽屜，至少有2個(gè)東西在同一抽屜里在第二個(gè)結(jié)論中，不妨想象將5雙手套分別編號(hào)，即號(hào)碼為1，2，...，5的手套各有兩只，同號(hào)的兩只是一雙。這相當(dāng)于把6個(gè)東西放入5個(gè)抽屜，至少有2個(gè)東西在同一抽屜里?！薄 ±蒙鲜鲈砣菀鬃C明：“任意7個(gè)整數(shù)中，至少有3個(gè)數(shù)的兩兩之差是3的倍數(shù)?！ ∪绻麊栴}所討論的對(duì)象有無限多個(gè)，抽屜原理還有另一種表述： “把無限多個(gè)東西任意分放進(jìn)n個(gè)空抽屜(n是自然數(shù))，那么一定有一個(gè)抽屜中放進(jìn)了無限多個(gè)東西。許多有關(guān)存在性的證明都可用它來解決?！边@個(gè)問題可以用如下方法簡(jiǎn)單明了地證出： 在平面上用6個(gè)點(diǎn)A、B、C、D、E、F分別代表參加集會(huì)的任意6個(gè)人。否則連一條藍(lán)線。根據(jù)抽屜原理可知其中至少有3條連線同色，不妨設(shè)AB，AC，AD同為紅色。不論哪種情形發(fā)生，都符合問題
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1