数学

直击竞赛－－数论中很常见的数学思想（基础轮～一轮难度）

1月21日，用${LaTeX}$翻新一遍

数论中的常见思想有很多，我们这次先来讲讲“抓大抓小”

那什么是抓大抓小呢？抓大抓小，指一种首先处理较大情况的解题策略，即我们在推导的过程中需要一些无伤大雅的附加条件，他们在一般情况下都能成立，但在一些特殊的情况下不成立，此时不妨先假设此附加条件成立完成题目主体部分的推导，在专门对特殊情况进行处理。

举个例子，对于每个正整数$n$，某国银行均发行面值为$\frac{1}{n}$的硬币.现有有限枚这样的硬币（同一面值的硬币可能有多枚）面值之和不超过$\frac{199}{2}$,证明：可以将这些硬币分为100组，每组面值之和不超过1.

证明：  首先我们先来证明一个稍强的结论：对任意有限枚总面值不超过$n—$$\frac{1}{2}$的硬币，总可以分成n组，每组面值之和不超过1.

如果将n进行归纳，当$n＝1$时，显然成立

假设结论对不超过$n-1$的情况都成立，下面来考虑n的情况.

先处理普通的情况，若有$d$枚硬币恰好是1，那么将每枚面值为1的硬币分为一组，剩下的相当于把面值之和不超过$(n-d)$—$\frac{1}{2}的硬币分成$n-d$组，每组面值之和不超过1，根据假设归纳可以做到.

接下来处理最一般的情况，直接思考如何分组可能稍微有点困难，我们来考虑一个反面的问题：怎样会导致分组失败？不难想象，如果我们每枚硬币的面值都很小，分组就 不会失败，具体来说，我们最后不可能剩下面值小于$\frac{1}{2n}$的硬币，这是因为面值总和不超过n-$\frac{1}{2}$，分成$n$组之后必有一组不超过平均值1—$\frac{1}{2n}$

这就意味着面值不超过$\frac{1}{2n}$的硬币一定可以找到一个合适的组填进去，这启发我们仅需考虑那些面值较大的硬币，也就是面值为$\frac{1}{2}$，$\frac{1}{3}$,...,$\frac{1}{2n—1}$的硬币，为了不浪费太多地方，我们当然希望尽量把面值相近的硬币放在一起，例如面值为$\frac{1}{2k—1}$，$\frac{1}{2k}$的硬币如果不超过$2k-1$枚，那么当然可以放成一组，如果至少有$2k$枚，那么有两种情况：

1.面值为$\frac{1}{2k—1}$的硬币至少有$2k-1$枚，那么取其中的$2k-1$枚可以合并为1枚面值为1的硬币，单独分组即可

2.面值为$\frac{1}{2k}$的硬币有至少两枚，那么可以合并为1枚面值为$\frac{1}{k}$的硬币.

注意每次合并操作会导致硬币数量减少，而硬币的数量有限，因此有限次合并后操作必定停止，此时可以将所有面值为$\frac{1}{2k—1}$,$\frac{1}{2k}$的硬币放在一组且面值不超过1，因为$\frac{1}{2}$自己一组，$\frac{1}{3}$,${1}{4}$一组，以此类推到$\frac{1}{2n—1}$正好$n$组，所以组数不超过$n$,而剩下的更小的硬币都可以找到合适的组放进去，从而命题得证。不难发现，这是组合味道很强的数论题，经过分析可发现，大的硬币才对分组产生本质困难，而小的实质上这无需考虑.