一道數學競賽題的探究

鐘佩吟

引 言

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

探 究

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

結 論

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

證 明

先證一個特殊的結論，即當k=2時，

構造抽屜：

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)},…

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

例如，當n=7時，抽屜構造方法如下：

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

A21={4}.

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

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

記k璱為抽屜A﹊j的下標j的最大值，即（*）第i行的抽屜個數，則

于是，抽屜的個數為

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

，結論成立.

例1 求f2(12).

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

事實上，按照上述方法構造抽屜：

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

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

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

,(k≥2).

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

構造抽屜：

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獇,…

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

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

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

記k璱為抽屜A﹊j的下標j的最大值，即（**）第i行的抽屜個數，則

于是，抽屜的個數為

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

本文為中學數學競賽類似題型提供一個較簡潔明了的解決方法，同時也可以作為一個數學公式為學習提供方便.