組合數(shù)學(西安電子科技大學(第二版))習題5.doc

習 題 五習題五（抽屜原理）1證明：在邊長為2的等邊三角形中任取5點，至少有兩個點相距不超過1。證明：如圖所示，將正三角形分成4個邊長為1的小等邊三角形，現(xiàn)在取5點，有4個小等邊三角形，根據(jù)抽屜原理，則至少有兩點落在同一個小等邊三角形中，其距離不超過1。2在一個邊長為1的正方形內任取9個點，證明以這些點為頂點的各個三角形中，至少有一個三角形的面積不大于。證明：如圖所示，將正方形分為4個邊長為的小正方形，現(xiàn)取9個點，則至少有三個點落在同一個小正方形中，以這三點為頂點的三角形的面積不大于。3把從1到326的326個正整數(shù)任意分成5組，試證明其中必有1組，該組中至少有一個數(shù)是同組中某兩個數(shù)之和，或是同組中某個數(shù)的兩倍。證明：用反證法。設任何一組中的每一個數(shù)，它既不等于同組中另外兩數(shù)之和，也不等于同組中另一數(shù)的兩倍。即任何一組數(shù)中任意兩個數(shù)之差總不在該組中。（1）由抽屜原理知，五組中必有一組其中至少有66個數(shù)，設為A組。從中取66個數(shù)，記為，不妨設最大，令 ，顯然，由假設知 ，故這65個數(shù)必在另外四組B、C、D、E中。 （2）由抽屜原理知，B、C、D、E四組中必有一組至少含有17個，設為B組，從中取17個，記為，同理不妨設最大， 令 ，顯然，且由假設知， 又 ， 所以這16個數(shù)必在C、D、E中。（3）由抽屜原理知，C、D、E三組中必有一組至少含有6個，設為C組， 從中取6個，記為，同理不妨設最大， 令 ，顯然，且由假設知， 又 所以這五個數(shù)必在D、E組中。 （4）由抽屜原理知，D、E兩組中必有一組至少含有3個，設為D組， 從中取3個，記為，同理不妨設最大， 令，顯然，且由假設知， 同理可得，故。 （5）不妨設，令 ，則，且由假設知， 同理可知， 即e不在A、B、C、D、E任一組中，又，與題設矛盾。 所以，命題成立。證畢。4任意一個由數(shù)字1，2，3組成的30位數(shù)，從中任意截取相鄰的三位，證明在各種不同位置的截取中，至少有兩個三位數(shù)是相同的。數(shù)的位數(shù)30還可以再減少嗎？為什么？解：設由數(shù)字1，2，3組成的30位數(shù)為：，則任意截取相鄰的三位，可能的截法有28種： ，而由1，2，3組成的三位數(shù)最多有個，則根據(jù)抽屜原理，這28個數(shù)中必至少有2個是相同的。 由證明過程可以知道，數(shù)的位數(shù)30不可以再減少了。因為若改為29個，則可得到27個三位數(shù)，就不能保證有2個是相同的。 若改為截取相鄰的5位，首先可知元素1、2、3的5可重排列共有個。其次，由問題的性質可知至少要能截取出不同的244段才能保證結論成立，從而知該數(shù)至少應該有248位。 問題的一般描述是：任意一個由數(shù)字1，2，m組成的n位數(shù)，從中任意截取相鄰的k位，則在各種不同位置的截取中，至少有兩個k位數(shù)是相同的。若希望至少有r個k位數(shù)是相同的，則應有n。5任取11個整數(shù)，求證其中至少有兩個數(shù)的差是10的倍數(shù)。證明：設這11個整數(shù)為：，不妨設，令，則，由抽屜原理知，必存在，使得，則 。證畢。 問題的一般描述：任取n1個整數(shù)，其中至少存在兩數(shù)，其差是n的倍數(shù)。6一次考試采用百分制，所有考生的總分為10101，證明如果考生人數(shù)不少于202，則必有三人得分相同。證明：采用百分制，則所有可能的分數(shù)為，共101個分數(shù)，現(xiàn)人數(shù)不少于202，則平均每個分數(shù)有兩個人得分相同。分情況討論：（1）若有某些分數(shù)沒有考生得該分數(shù)，則202名考生，可能的考生成績最多100種，根據(jù)抽屜原理，必有三個的得分相同。（2）若有1個考生的分數(shù)與其他人都不同，則其余201名考試可能的分數(shù)只有100種，則必有三人的得分相同。 （3）若每個分數(shù)線都有兩個人，則所有考生的總分為：，與題目矛盾。所以這種情況不可能存在。綜上所述，必有三人得分相同。證畢。 方法二：反證法。假設沒有三個考生考試成績相同，因為分數(shù)的分布為0100分，共101種分數(shù)，若考生人數(shù)大于202人，則根據(jù)抽屜原理必然有三人考試成績相同，矛盾；若考生人數(shù)恰好202個，要求沒有三個考生考試成績相同，則所有考生必然恰好兩兩得分相同。而此時所有考生的總分為：，矛盾。故結論成立。 方法三：此題的另一種理解是將10101個物品放入202個盒子，每個盒子最多放100個，也可以不放，則至少有三個盒子中所放物品個數(shù)相同。如若不然，至多有兩個盒子的物品一樣多，則只能恰好用去10100個物品，剩下一個物品，就無法處理，一旦將其放入某個有k個物品的盒子，那么，就有3個盒子放了k1個物品。 此問題的一般提法是：所有考生的總分為5050rt ，如果考生人數(shù)不多于101r人，則至少有r1人得分相同。7將n個球放入m個盒子中，試證其中必有兩個盒子有相同的球數(shù)。證明：（反證法）。 假設m個盒子中的球數(shù)均不相同，則m個盒子中球的總數(shù)至少為： ，矛盾， 故必然有兩個盒子的球數(shù)是相同的。8設有三個7位二進制數(shù)：、和，試證存在整數(shù)i和j，使得下列等式中至少有一個成立： ，證明：因為二進制數(shù)只有0,1兩種數(shù)位，從而有只有兩種狀態(tài)，又，根據(jù)抽屜原理可知，在這7個元素中，至少有四個元素的取值相同，或均為1，或均為0。不妨設這四個元素為，且設（同理可討論的情況），因為，由抽屜原理可知，在這四個元素中，必至少有兩個元素取值相同，或均為1，或均為0。不妨設這兩個元素為：，（1） 若，則得 ，滿足結論，（2）若，則 若，則，滿足結論； 否則，中至少有一個取0。不妨設，從而有。因為由，由抽屜原理可知，在中應至少有兩個元素取值相同，不妨設是，則u 若，則有，滿足結論；u 若，則有，滿足結論。綜上所述，結論必成立。證畢。 證法二：顯然，每組中，必有兩數(shù)字相同，共有種模式，其值或為或為，故共有種選擇?，F(xiàn)在有7組，因為，由抽屜原理可知，必有組數(shù)在相同的兩行i、j上選擇相同的數(shù)字，即存在整數(shù)i和j，使得下式之一必然成立： ， 證法三：考慮將3個7位二進制數(shù)視為一個37的方格棋盤，用紅、藍兩色（分別用0、1表示）之一對每個方格進行染色，則問題變成：證明至少有4個格子同色，且此4個格子位于由若干個小方格組成的某個長方形的4個角上。也就是說必存在兩行兩列，其交叉處的4個格子同色001110001101010101011000110110由于顏色數(shù)比行數(shù)少一，故對每列而言，至少有兩格同色。如圖5.2.3（a），設第一列的前兩行為紅色，后一行為藍色，則后6列中的任何一列的前兩行都不能再為紅色，否則即會出現(xiàn)4個同色格子構成長方形的情形，即結論成立。由此看出，兩個紅色方格同列的情形最多只能有3列。而圖5.2.3（b）的染法，只能使得這樣的列數(shù)最多為1列，其后每列最多只能有一個紅格子，且各列紅格子所處的行還不能相同?？傊?，對每種顏色，在某列中被用了兩次的列最多為列。當顏色數(shù)為2時，這樣的列最多只有26個，現(xiàn)在總列數(shù)為7，故由抽屜原理，必有某兩列中相同的兩行的4個格子所染顏色相同。9證明：把110這10個數(shù)隨機地寫成一個圓圈，則必有某3個相鄰數(shù)之和大于或等于17。若改為126，則相鄰數(shù)之和應大于或等于41。證明：設這10個數(shù)圍成的圓圈為， 令， 則， 現(xiàn)在有10個數(shù)，故必存在某個。證畢。 同理，若是126，則同樣可構造出3個相鄰數(shù)之和， 且有， 故必存在某個。 一般情形： 已知n個正整數(shù)數(shù)，將其隨機地寫成一個圓圈，則必有某k個相鄰數(shù)之和大于或等于M，那么，M10某學生準備恰好用11個星期時間做完數(shù)學復習題，每天至少做一題，一個星期最多做12題，試證必有連續(xù)幾天內該學生共做了21道題。證明：11個星期總共有77天，每天做的題數(shù)設為， 則， 構造序列，則， 若存在某個，則問題得證。 否則，所有的，令集合， 則有， 集合A中共有154個數(shù)，每個數(shù)的取值在1153之間，由抽屜原理知，必有兩個數(shù)相等。又時，從而，所以，相等的兩個數(shù)必為，顯然，故 。證畢。11行列的格子用m種顏色著色，每格著一種色，證明其中必有一個4角的格子同色的矩形。證明：每列有行，只有m種顏色，因此，根據(jù)抽屜原理，一列中必有兩格同色。一列中同色的兩個格子的行號有種取法，故有種同色模式。現(xiàn)有列，所以，根據(jù)抽屜原理，必有兩列的同色模式相同。因此，這兩列對應于同色模式的兩行上有4個格子同色，它們正好是一個矩形的4個角上的格子。證畢。12證明：（1）平面上任取5個整點（坐標為整數(shù)的點），其中至少有兩個點，由它們所連線段的中點也是整點。 （2）從三維空間任取9個整點中至少有兩個點，其連線的中點為整點。證明：平面上的整點的坐標為，而x、y只可能為奇數(shù)或偶數(shù)，故可能的坐標只有四種：（奇，奇）、（奇、偶）、（偶，奇）、（偶，偶），現(xiàn)在取5個整點，則必有兩個整點的奇偶性是一樣的，設這兩個整點為，則奇偶性相同，奇偶性相同，而這兩個點的連線中點的坐標為：，因為奇偶性相同，奇偶性相同，所以，均為偶數(shù)，所以為整點。 （2）三維空間的點的坐標為，根據(jù)x，y，z的奇偶性可將坐標分為8類：（奇,奇,奇）、（奇,奇,偶）、（奇,偶,奇）、（奇,偶,偶）、（偶,奇,奇）、（偶,奇,偶）、（偶,偶,奇）、（偶,偶,偶），現(xiàn)在取9個點，則必有2個點的類型相同，設這兩個整點為：，則奇偶性相同，奇偶性相同，奇偶性相同，而這兩個點的連線中點的坐標為：，因為，均為偶數(shù)，所以該點為整點。(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(2,2)13在平面直角坐標系中至少任取多少個整點，才能保證其中存在3個點構成的三角形的重心是整點。解： 設三角形三個頂點的坐標為：， 則其重心坐標為：，因為平面直角坐標系中的整點的坐標模3后只有如表所示的9種可能；而滿足3點重心是整點的條件類型有以下4種情況：（1）3點在同一格子中；（2）3點占滿一行的格子；（3）3點占滿一列的格子；（4）3點均勻分布，不同行也不同列，由下面四種模式：(0,0)，(1,1)，(2,2)（ ）（主對角線）；(1,0)，(2,1)，(0,2)（ ）；(0,2)，(1,1)，(2,0)（ ）（副對角線）；(0,1)，(1,2)，(2,0)（ ）；因而任取9個點中，必至少存在著3個點，其重心是整點。下面證明。（反證法）假設任取9個點，不存在3個點構成的三角形的重心是整點。則每個格子最多有2個點，否則有三個點在同一格子中，滿足（1），其重心是整點，與假設矛盾。因為格，根據(jù)抽屜原理，則9個點至少落入5個格子中，若5個格子中有三個在同一行，即滿足（2），則與假設矛盾，故每行最多有占2格，又行，根據(jù)抽屜原理，則每行都有點；同理，若5個格子中有三個在同一列，即滿足（3），與假設矛盾，故每列最多占2格，同理列，根據(jù)抽屜原理可知，每列都有點；由證明過程知，每行每列都有點，又不滿足（1）（2）（3），則必是（4）的情況，這與假設矛盾。因此，因而任取9個點中，必至少存在著3個點，其重心是整點。但是8個點中不能保證其中存在著3個點其重心一定是整點。因為存在著一種情況：8個點分布在表1的4個格子中，每格2個點，而不滿足3點重心是整點的條件類型的4種情況。例如若8個點落在表1的左上角(0,0),(0,1),(1,0),(1,1)這4個格子中，每格2個點，則顯然不滿足3點重心是整點的條件類型的4種情況。因此，在平面直角坐標系中，最少需任取9個整點，才能保證其中存在3個點構成的三角形的重心是整點。第二版新增部分習題：11求證在任意給的11個整數(shù)中，一定存在6個整數(shù)，它們的和是6的倍數(shù)。證明：設這11個數(shù)為， 令，則的可能取值為0，1，2（看為3個抽屜）， 根據(jù)抽屜原理，至少有3個整數(shù)的相同，不妨設這3個整數(shù)為，令，則，剩下8個整數(shù)中，根據(jù)抽屜原理，至少有3個整數(shù)的相同，不妨設為，令，則,剩下5個整數(shù)中，若有3個整數(shù)的相同，則它們之和必然被3整除，否則相同的整數(shù)最多2個，則必存在三個整數(shù)，其取值都不相同，則它們之和也是3的倍數(shù)，因此從5個數(shù)中，必然可以找到3個數(shù)，其和是3的倍數(shù)，不妨設這三個數(shù)為，令，則,對于這三個數(shù)而言，令，則根據(jù)抽屜原理，至少有2個數(shù)的ti相同，不妨設這兩個數(shù)為，則，而又有，故。證畢。12證明任意給定的52個整數(shù)中，總存在兩個數(shù)它們的和或差能被100整除。證明：設52個整數(shù)為， 令，則的可能取值為0，1，2，99。 現(xiàn)將分為51類：0,1,99,2,98,，49,51,50（看為51個抽屜）， 則根據(jù)抽屜原理，至少有2個屬于同一類，假設屬于同一類，則或者或者，若，則能被100整除，若，則能被100整除。證畢。13證明：（1）每年至少有一個13日是星期五。 （2）每年至多有三個13日是星期五。證明：（假設1年365天）（1）每年中共有12個13日，它們是1.13，2.13，3.13，12.13。 （反證法）假設它們都不是星期五，則是星期一、星期二、星期三、星期四、星期六、星期日之一（用mi表示） 因為2.13和3.13相差28天，3.13和11.13相差245天，都是7的倍數(shù)，因此這3天星期幾相同，用m1表示星期幾（星期天用7表示）； 而1.13和10.13相差274天屬于同一個星期幾，用m2表示； 同理，4.13和7.13相差91天，同屬于一個星期幾，用m3表示； 9.13和12.13相差91天，同屬于1個星期幾，用m4表示； 且（它們相差不是7的倍數(shù)，因此不會相等），則剩下的3天5.13，6.13，8.13的星期幾只能在剩下的兩個mi中選，根據(jù)抽屜原理，至少有2個的星期幾相同，但是這時不可能的，因為這3天相隔都不是7的倍數(shù)，產生矛盾，因此必有一個13日是星期五。（2）從（1）的討論可知，至多只有3個月，它們兩兩之間的間隔天數(shù)都是7的整數(shù)倍，因此只有2.13，3.13，11.13可能同時為星期五，不可能有4個月的13日全為星期五。14設是整數(shù)的任意一個排列，證明：當n是奇數(shù)時，乘積肯定是偶數(shù)。證明：n為奇數(shù)時，中有個奇數(shù)，個偶數(shù)， 則這個數(shù)中，必至少有1個是奇數(shù)， 從而中，必至少有1個是偶數(shù)， 因此乘積肯定是偶數(shù)。證畢。17在平面直角坐標系中任取5個整點（兩個坐標都是整數(shù)），證明其中一定存在3個點，由其構成的三角形（包含3點在一條直線上）的面積是整數(shù)（可以為0）。解：任一整點(a,b)的坐標只有如下4種可能：（奇數(shù)，偶數(shù)），（奇數(shù)，奇數(shù)），（偶數(shù)，奇數(shù)），（偶數(shù)，偶數(shù)）。根據(jù)抽屜原理，5個點中必至少有2個點的奇偶模式相同，設(x1,y1)，(x2,y2)是5個點中奇偶模式相同的那2個點，則有2(x1-x2)，2(y1-y2)，故可設x1-x2=2k，y1-y2=2m。再在剩下的3個點中任取一點(x3,y3)，則這3點構成的三角形D的面積是整數(shù)。18用4種顏色給平面上的完全圖（66個頂點，每個頂點間