鐘佩吟

引 言

在中學(xué)數(shù)學(xué)競賽中，“極端原則”是一個(gè)重要知識(shí)點(diǎn)，本文選取了“極端原則”的一個(gè)典型案例，即“從1,2,…，n這n個(gè)正整數(shù)中，最多可選出f璳(n)個(gè)數(shù)，使得在選出的數(shù)中，每個(gè)數(shù)都不是另一個(gè)數(shù)的k倍”，給出了f璳(n)的表達(dá)式，并利用抽屜原理給出嚴(yán)謹(jǐn)證明，這也是選取這f璳(n)個(gè)數(shù)的一個(gè)具體操作方法，該結(jié)果簡潔整齊（類似歐拉公式），可計(jì)算性強(qiáng)，避免了通常情況下的窮舉法和舉反例等繁瑣的操作，可作為一個(gè)數(shù)學(xué)公式來學(xué)習(xí)和使用.

探 究

從1,2，…，n這n個(gè)正整數(shù)中，最多可選出f璳(n)個(gè)數(shù)，使得在選出的數(shù)中，每個(gè)數(shù)都不是另一個(gè)數(shù)的k倍，問：ゝ璳(n)等于多少？(k=2,3,4,…）

結(jié) 論

f璳(n)=А苅≥0(-1)琲n[]k琲,(k≥2)（其中［x］表示不大于x的最大整數(shù)）.

證 明

先證一個(gè)特殊的結(jié)論，即當(dāng)k=2時(shí)，

構(gòu)造抽屜：

A11={1,2},A12={3，6}，…，A1j={2j+1,2(2j+1)},…

A21={4，8}，A22={12，24}，…,A2j={22?(2j+1),2?22（2j+1)},…

螅*）

A﹊1={22i,2?22i獇,A﹊2={22i?3,2?22i?3},…，A﹊j={22i?(2j+1),2?22i(2j+1)},…

在構(gòu)造抽屜的過程中，保證每個(gè)抽屜中的元素都不大于n，并且抽屜中較大的元素是較小的2倍，如果較小元的2倍大于n，則該抽屜只包含較小元1個(gè)元素，其2倍數(shù)自動(dòng)舍去.

例如，當(dāng)n=7時(shí)，抽屜構(gòu)造方法如下：

A11={1,2},A12={3,6},…,A14={7}，

A21={4}.

按照上述的構(gòu)造方法，有{1,2,…,n}=А泉﹊,j≥1A﹊j，且A﹊j(i,j∈N+)兩兩互不相交.

要滿足1,2，…,n中選出的兩個(gè)數(shù)中，每一個(gè)都不是另一個(gè)的2倍，則每個(gè)抽屜至多選出一個(gè)數(shù)，即選出的數(shù)的個(gè)數(shù)最多只能是上述抽屜的個(gè)數(shù).否則，若取出的數(shù)大于上述抽屜的個(gè)數(shù)，則根據(jù)抽屜原理，必有兩個(gè)數(shù)同時(shí)落入同一個(gè)抽屜中，此時(shí)這兩個(gè)數(shù)一個(gè)是另一個(gè)的2倍，不符題意.

記k璱為抽屜A﹊j的下標(biāo)j的最大值，即（*）第i行的抽屜個(gè)數(shù)，則

于是，抽屜的個(gè)數(shù)為

即f2(n)=А苅≥0(-1)琲n[]2琲

，結(jié)論成立.

例1 求f2(12).

解 f2(12)=А苅≥0(-1)琲12[]2琲

事實(shí)上，按照上述方法構(gòu)造抽屜：

A11={1,2},A12={3,6},A13={5},A14={7},A15={9},A16={11},A21={4,8},A22={12},共有8個(gè)抽屜.

因此，最多可取出8個(gè)數(shù)，比如{1,3,5,7,9,11,4,12}，此時(shí)選出的數(shù)每個(gè)都不是另一個(gè)的2倍.

下證一般的結(jié)論f璳(n)=А苅≥0(-1)琲n[]k琲

,(k≥2).

對(duì)于k≥2，k∈N+,記1,2,…，n中不是k的倍數(shù)的為c1，c2，…，c璴.

構(gòu)造抽屜：

A11={c1,c1k},A12={c2,c2k},…，A1j={c璲,c璲k},…

A21={c1k2,c1k3},A22={c2k2,c2k3},…,A2j={c璲k2,c璲k3},…

螅**）

A﹊1={c1k2i,c1k2i+1獇,A﹊2={c2k2i,c2k2i+1獇,…，A﹊j={c璲k2i,c璲22i獇,…

在構(gòu)造抽屜的過程中，保證每個(gè)抽屜中的元素都不大于n，并且抽屜中較大的元素是較小的k倍，如果較小元的k倍大于n，則該抽屜只包含較小元1個(gè)元素，其k倍數(shù)自動(dòng)舍去.

按照上述的構(gòu)造方法，有{1,2,…，n}=А萯,j≥1A﹊j，且A﹊j(i,j∈N+)兩兩互不相交.

要滿足1,2,…,n中選出的兩個(gè)數(shù)中，每一個(gè)都不是另一個(gè)的k倍，則每個(gè)抽屜至多選出一個(gè)數(shù)，即選出的數(shù)的個(gè)數(shù)最多只能是上述（**）抽屜的個(gè)數(shù).否則，若取出的數(shù)大于上述抽屜的個(gè)數(shù)，則根據(jù)抽屜原理，必有兩個(gè)數(shù)同時(shí)落入同一個(gè)抽屜中，此時(shí)這兩個(gè)數(shù)一個(gè)是另一個(gè)的k倍，不符題意.

記k璱為抽屜A﹊j的下標(biāo)j的最大值，即（**）第i行的抽屜個(gè)數(shù)，則

于是，抽屜的個(gè)數(shù)為

А苅≥1k璱=n-n[]k

本文為中學(xué)數(shù)學(xué)競賽類似題型提供一個(gè)較簡潔明了的解決方法，同時(shí)也可以作為一個(gè)數(shù)學(xué)公式為學(xué)習(xí)提供方便.