手感可以区分形状,所以可以按形状取糖。
在一个黑色的袋子里放有三种口味的糖果,每种糖果有两种不同的形状(圆形和五角星形,不同的形状靠手感可以分辨)。参赛者需要在活动前决定摸出的糖果数目。最少取出多少个糖果,才能保证手中有圆形苹果味匹配五角星桃子味,或者圆形桃子味匹配五角星苹果味?
| 形状 | 苹果味 | 桃子味 | 西瓜味 |
|---|---|---|---|
| 圆形 | 7 | 9 | 8 |
| 五角星形 | 7 | 6 | 4 |
先取 12 个五角星形:非苹果味只有 6 + 4 = 10 个,非桃子味只有 7 + 4 = 11 个。所以 12 个中必有苹果味,也必有桃子味。
再取 9 个圆形:西瓜味圆形只有 8 个,所以必有至少一个苹果味或桃子味圆形。它一定能与刚才的五角星形糖果跨口味配对。
因此,12 + 9 = 21 个足够。
为什么 20 个不够?
设取 20 个,其中圆形有 r 个、五角星形有 20 − r 个。每一种形状分配,都能遇到无法配对的情况:
- r ≤ 8:所有圆形都可能是西瓜味。
- 9 ≤ r ≤ 15:两种形状都可能只有苹果味和西瓜味(分别有 15 个圆形、11 个五角星形可供抽取),没有桃子味。
- 16 ≤ r ≤ 20:五角星形至多 4 个,都可能是西瓜味。
因此 20 个无法保证,最小值为 21。更少数量也不可能保证,否则补取到 20 个仍会保证,与上述反例矛盾。
这里按题意利用手感主动选择形状,不提前识别口味。若完全不利用形状信息、混合随机抓取,则另一种问题的保证数量为 29 个:最多可有 28 个仍不配对(12 个西瓜味 + 9 个圆形桃子味 + 7 个圆形苹果味 = 28 个)。