一道数学竞赛题的探究

钟佩吟

引 言

在中学数学竞赛中，“极端原则”是一个重要知识点，本文选取了“极端原则”的一个典型案例，即“从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

本文为中学数学竞赛类似题型提供一个较简洁明了的解决方法，同时也可以作为一个数学公式为学习提供方便.