將2n個數分成A={1,2,....n},B={n+1,n+2,........2n} B中所有數的乘積=2^n*(1*3*5*7*......2n-1) 不超過2n的偶數均可歸類為A中奇數的2^k倍 1.當我們某個奇數或其相對的偶數倍數時,即不可再挑選其相對應的其他偶數或奇數 例如:3,3*2,3*2^2,3*2^3...,從中挑選一數時,即不可挑選其他數 2.而這些數分類後,在屬於A中的奇數,至多(n+1)/2個,均可找到2^k倍的倍數,B中所有奇數的個數至多n/2個,均無法在1~2n中找到屬於偶數倍數 3.如此,最多找到n/2+n/2=n個數,其中無一數是另一數的倍數 4.再挑第n+1個數時,因B中奇數均已選出,必須從A中奇數及其2^k倍的倍數中尋找 如此必造成至少有一個數是另一個數的倍數
例如1~40可分配至編號1,3,5,7,9,.......39共20個集合中 1:{1,2,4,8,16,32},3:{3,6,12,24},5:{5,10,20,40}, 7:{7,14,28},9:{9,18,36} 11:{11,22},13:{13,26},15:{15,30},17:{17,34},19:{19,38} {21},{23},{25},{27},{29},{31},{33},{35},{37},{39} 為避免成倍數關係,必須分別從每個集合中分別挑選,按鴿籠原理最後必定造成至少有一個數是另一個數的倍數
|