抽屜原理的典型問題(編輯修改稿)
2025-04-21 02:31 本頁面
【文章內(nèi)容簡介】 少有三條線段是同一種顏色，假定是紅色，現(xiàn)在我們再單獨(dú)來研究這三條紅色的線。這三條線段的另一端或許是不同顏色，假設(shè)這三條線段(虛線)中其中一條是紅色的，那么這條紅色的線段和其他兩條紅色的線段便組成了我們所需要的同色三角形，如果這三條線段都是藍(lán)色的，那么這三條線段也組成我們所需要的同色三角形。因而無論怎樣著色，在這六點(diǎn)之間的所有線段中至少能找到一個(gè)同色三角形。例3′(六人集會(huì)問題)證明在任意6個(gè)人的集會(huì)上，或者有3個(gè)人以前彼此相識(shí)，或者有三個(gè)人以前彼此不相識(shí)。”例3”：17個(gè)科學(xué)家中每個(gè)人與其余16個(gè)人通信，他們通信所討論的僅有三個(gè)問題，而任兩個(gè)科學(xué)家之間通信討論的是同一個(gè)問題。證明：至少有三個(gè)科學(xué)家通信時(shí)討論的是同一個(gè)問題。 解：不妨設(shè)A是某科學(xué)家，他與其余16位討論僅三個(gè)問題，由鴿籠原理知，他至少與其中的6位討論同一問題。設(shè)這6位科學(xué)家為B，C，D，E，F(xiàn)，G，討論的是甲問題?！ ∪暨@6位中有兩位之間也討論甲問題，則結(jié)論成立。否則他們6位只討論乙、丙兩問題。這樣又由鴿籠原理知B至少與另三位討論同一問題，不妨設(shè)這三位是C，D，E，且討論的是乙問題?！ ∪鬋，D，E中有兩人也討論乙問題，則結(jié)論也就成立了。否則，他們間只討論丙問題，這樣結(jié)論也成立?！ ±? 從…、30這15個(gè)偶數(shù)中，任取9個(gè)數(shù)，證明其中一定有兩個(gè)數(shù)之和是34?！ 》治雠c解答 我們用題目中的15個(gè)偶數(shù)制造8個(gè)抽屜： 凡是抽屜中有兩個(gè)數(shù)的，都具有一個(gè)共同的特點(diǎn)：這兩個(gè)數(shù)的和是34。現(xiàn)從題目中的15個(gè)偶數(shù)中任取9個(gè)數(shù)，由抽屜原理(因?yàn)槌閷现挥?個(gè))，這兩個(gè)數(shù)的和是34?！ ±?：從…、120這20個(gè)自然數(shù)中，至少任選幾個(gè)數(shù)，就可以保證其中一定包括兩個(gè)數(shù)，它們的差是12?！ 》治雠c解答在這20個(gè)自然數(shù)中，差是12的有以下8對：{20，8｝，{19，7｝，{186｝，{17，5｝，{16，4｝，{15，3｝，{14，2｝，{13，1｝。 另外還有4個(gè)不能配對的數(shù){9｝，{10｝，{11｝，{12｝，共制成12個(gè)抽屜(每個(gè)括號(hào)看成一個(gè)抽屜).只要有兩個(gè)數(shù)取自同一個(gè)抽屜，那么它們的差就等于12，根據(jù)抽屜原理至少任選13個(gè)數(shù)，即可辦到(取12個(gè)數(shù)：從12個(gè)抽屜中各取一個(gè)數(shù)(例如取1，2，3，…，12)，那么這12個(gè)數(shù)中任意兩個(gè)數(shù)的差必不等于12)?！ ±?： 從1到20這20個(gè)數(shù)中，任取11個(gè)數(shù)，必有兩個(gè)數(shù)，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)?！ 》治雠c解答根據(jù)題目所要求證的問題，應(yīng)考慮按照同一抽屜中，看成10個(gè)抽屜(顯然，它們具有上述性質(zhì))： {1，2，4，8，16｝，{3，6，12｝，{5，10，20｝，{7，14｝，{9，18｝，{11｝，{13｝，{15｝，{17｝，{19｝?！ 倪@10個(gè)數(shù)組的20個(gè)數(shù)中任取11個(gè)數(shù)，根據(jù)抽屜原理，所以這兩個(gè)數(shù)中，其中一個(gè)數(shù)一定是另一個(gè)數(shù)的倍數(shù)?！ ±?：某校校慶，來了n位校友，在這n個(gè)校友中至少有兩人握手的次數(shù)一樣多?！ 》治雠c解答共有n位校友，每個(gè)人握手的次數(shù)最少是0次，即這個(gè)人與其他校友都沒有握過手。最多有n1次，如果有一個(gè)校友握手的次數(shù)是0次，那么握手次數(shù)最多的不能多于n2次。如果有一個(gè)校友握手的次數(shù)是n1次，、 …、n2，還是后一種狀態(tài)…、n1，到會(huì)的n個(gè)校友每人按照其握手的次數(shù)歸入相應(yīng)的“抽屜”，根據(jù)抽屜原理，至少有兩個(gè)人屬于同一抽屜，則這兩個(gè)人握手的次數(shù)一樣多?！ ≡谟行﹩栴}中，“抽
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1