第二章抽屜原理課后題

第二章抽屜原理抽屜原理習題1在1,4,7,10,13,…,100中任意選出20個數，證明其中至少有不同的兩對數，每對數的和都等于104抽屜原理習題1分析:本題中要求選出20個數,且至少有不同的兩對數和為104,故應構造少于20個數組,且同一組數的和為104解答:將本題中給出的數分成(4,100)(7,97)…(49,55)(52)(1)共18個數組,每個數組中的數的和為104,從這18個抽屜中任取20個數,有下述兩種情況：1)取到1和52,則剩下的18個數取自余下的16個抽屜,故至少有2對數取自某兩個抽屜，即和為1042)不全取1和52,則有多于18個數取自16個抽屜中,同樣至少有2對數取自某兩個抽屜，即和為104抽屜原理習題2在{1,2,…,2n}中任取n+1個數，證明其中必有兩個數互素抽屜原理習題2分析:本題中要求選出n+1個數,且必有兩個數互素,故應構造至多n個數組,且每組兩數互素解答:將本題中給出的數分成(1,2)(2,3)…(2n-1,2n)共n個數組,每個數組中兩數互素,從這n個抽屜中取n+1個數,必有兩數取自同一個抽屜，即取到的兩數互素抽屜原理習題3從1,2,3,…,2005中刪去一些數，使得剩下的數中任何一個數都不等于其余兩個不同數的積，問至少要刪去多少個數才能做到這一點？抽屜原理習題3分析:本題較難,因難以據題意決斷構造幾個抽屜,但知道每個抽屜需滿足任何一個數等于其余兩個不同數的積解答:將本題中給出的數分成(44,45,44×45)(43,46,43×46)…(3,86,3×86)(2,87,2×87)共43組,故至少刪去43個數,即2,3,4,…44后,剩下的數就滿足題中條件抽屜原理習題4在不超過91的正整數中任取10個不同的數，證明這10個數中一定有兩個數的比值在[2/3,3/2]內抽屜原理習題4分析:本題中要求任取10個數,且必有兩個數的比值在[2/3,3/2]之間,故應構造至多9個數組,且同一組中任兩個數的比值在[2/3,3/2]之間解答:把不超過91的正整數分成(1)(2,3)(4,5,6)(7,8,9,10)(11,12,13,14,15,16)(17,18,19,20,21,22,23,24,25)(26,27,28,29,30,31,…39)(40,41,42,…,60)(61,62,63,…,90)共9個數組,每個數組中的任意兩數的比值在[2/3,3/2]之間,從這9個抽屜中任取10個數,有下述兩種情況：1)取到1,則剩下的9個數取自余下的8個抽屜,則必有兩個數取自同一個抽屜，即兩數的比值在[2/3,3/2]之間2)不取1,則10個數取自余下的8個抽屜,必有兩個數取自同一個抽屜，即兩數的比值在[2/3,3/2]之間分情況討論抽屜原理習題5任給7個實數，證明其中必有兩個數x,y滿足抽屜原理習題5分析:由要證明的不等式形式想到兩角差的正切公式,且兩角差小于π/6解答:首先,7個實數中至少有4個數同為非正或非負(抽屜原理的簡單應用)不妨設4個數同為非負數,設為tanθ1,tanθ2,tanθ3,tanθ4,因非負θi∈[0,π/2),i=1,2,3,4

4個數中必有2個數的差滿足條件,故將4個數分成3組,故將[0,π/2)分為3個抽屜[0,π/6),[π/6,π/3),[π/3,π/2).這樣必有兩個θm,θn取自同一個抽屜,不妨設θm＞θn,則0＜θm–θn＜π/6,0＜tan(θm–θn)＜√3/3.故必存在數x=tanθm,y=tanθn滿足條件多次運用抽屜原理抽屜原理習題6坐標平面內任給13個整點，其中任3點均不共線，求證必有以其中3點為頂點的三角形其重心也是整點抽屜原理習題6分析:因為三角形的重心公式為((x1+x2+x3)/3,(y1+y2+y3)/3),若為整點則要求3/(x1+x2+x3),3/(y1+y2+y3),對于整除性問題通常按剩余類分組,即[0][1][2],當x1,x2,x3或y1,y2,y3取自同一個剩余類時，則3可以整除它們之和解答:設平面內13個點的坐標為pn

(xn,yn),n=1,2,3,…13,于是pn中必有[13/3]+1=5個點的橫坐標同在3的一個剩余類中，為使重心為整點還需其縱坐標之和也是3的整數倍,下面在這5個點中考慮其縱坐標,應有以下兩種情況：1)5個點的縱坐標中,3的3個剩余類均存在，即存在pi,

pj,pk,使其縱坐標yi≡3(0),yj≡3(