奇葩的题目与奇怪的解法

01 题目

02 解读

实际上，这道题目中一个较大的难点是审题。首先，我们需要理解题目中给的定义。题目中要给n个小孩分配糖果，并且每个小孩所获得的糖果是从n个不同的口味中挑选的，也就是说每个小孩可以得到0到n种口味的糖果。同时，题目给了很高的自由度，因为并没有限制每种口味的数量，因此不需要考虑分配时缺少某种口味的情况。题目中对于k—好的定义也比较容易理解，本质上就是其中任意k个小孩的糖果合起来至少有k个不同口味的糖果。

接下来，我们需要理解问题本身。对于任意给定的n≥1, 我们要找出所有可能的S。这里挑选S的标准是（即S所满足的充要条件）：只要任意一个糖果的分配对于所有k都是k—好的（其中k为S中的任意一个元素），那么该分配一定是1—好，2—好，3—好，...，n—好的。

这里一般会想到用数学语言重新表述，但这个题目中是不必要的，且容易将问题复杂化。在这里我还是展示一下如何严谨地表述题目条件。

03 题目抽象化

04 初步处理

一个比较常规的处理方式是计算n较小的情况，并从其中找出一些规律，用这种方法可以较快地找出合理的思路。

但是，我一开始并没有这么做，而是尝试了很多奇怪的方法，最后用了接近1小时才解决......

这里分享一些我找到的（有用的）结论：

1. 无法由一种分配k—好推出该分配(k+1)—好

2. 无法由一种分配(k+1)—好推出该分配k—好

3. 无法从一种分配(k+1)—好且(k-1)—好推出该分配k—好

4. 无法从一种分配(k+m)—好且(k-n)—好推出该分配k—好

这些结论的证明非常简单，可以自己尝试。虽然我用了不到10分钟得出了这些结论，但一开始走了很多弯路才到了这一步。

05 结论与构造

有了以上的结论，很容易就知道唯一满足条件的子集是{1, 2, 3, ..., n}, 并且该子集显然符合题意。

实际上，如果第一步选择了正确的处理，可以直接通过构造来证明结论。不妨设存在S，满足S是{1, 2, 3, ..., n}的子集且|S|=n-1（该条件强于任意|S|≤n-2的情况且能被这种情况验证，因此无需进一步讨论）。这就说明

{1, 2, 3, ..., n}中的一个元素不在S里，称该元素为k. 由题意知此时的分配必须是1, 2, ..., k-1, k+1, ..., n-1, n—好的。若S符合条件，则任意 1, 2, ..., k-1, k+1, ..., n-1, n—好的分配也必须是k—好的分配。可构造以下情况：

1. 有k-1个小孩各有k-1个不同种类的糖果，

   且这k-1个小孩所拥有的糖果完全相同

2. 另外n-k+1个小孩中n-k个小孩均有n个糖果

3. 剩下的1个小孩没有糖果

显然，S不符合条件。证毕。

06 补充

许多人在审题阶段对题目条件产生了误解，两个常见的误解是没有意识到糖果数量不存在限制和没注意到分配方面的规则。

我个人认为这道题目本来应该是非常简单的，而我被题目带偏了很多次。但是，不排除这也是很多人都面临的情况，且组委会也意识到了这一点（毕竟这道题目在第二题的位置上）