俄罗斯奥赛题解答

100个箱子，里面放苹果、梨、橘子，可以混合

问：不管怎么放这些水果，是不是总能挑出51个箱子，使这51个箱子里的苹果、梨、橘子分别都不少于其他49个箱子里的苹果、梨、橘子？

=====================================================================

先做些准备工作：

（1）
对于N个含同一种类水果的箱子，可以找到N/2（N是偶数），或（N+1）/2（N是奇数）个箱子，使得这N/2或（N+1）/2个箱子中的水果大于等于其余箱中的水果。这是显而易见的，比如，100个箱子，按箱内水果数量从多到少排序，前50个箱子的水果之和肯定大于等于后50个箱子的水果之和。

（2）
对于N个箱子，每个箱子里含有N种水果（水果的数量可以为0），则在最坏情况下，你需要全部N个箱子，来满足题中的条件，即：使得选中的这N个箱子中的每样水果数量不少于余下箱子中相应水果的数量。一个例子是：正交矩阵，行代表箱子，列代表水果

箱子\\水果
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1

显然，任何N
现在开始解题：

如果箱子数和水果数不等，比如这里，100个箱子，3种水果，我们可以先把它看作是100个箱子，100种水果。那么，我们知道，最坏情况下，我们有一个100 X 100的正交矩阵，我们只有取全部100个箱子，才能确保这一百个箱子满足题里的条件。

那么，想象这个正交矩阵的前99列（即前99种水果）不变，最后一种水果消失，必须变成前99种水果中的一种，那么，我们有98个箱子，#1到#98，每个箱子都只含有一种水果种类（#1,…,#98），和另外2个箱子，#99，#100，两个箱子中都只含有水果#99。

根据定理（2），为了满足条件，#1到#98这98个箱子，必须全部取出。

根据定理（1），#99和#100这两个箱子，只需取一个出来，取那个多的出来。

因此，100个箱子，含99种水果，至少要取99个箱子出来，才能满足条件。

当然，这里的第100种水果消失后，箱子#100也可能包含多种水果的组合，但是，结论相同。这里，我们考虑的是最坏情况。

现在考虑100个箱子，98种水果，思路同上，最后，我们可能得到2种情况：

1）97个箱子，分别只含水果#1到#97，和3个箱子，都含水果#98，根据上面定理，我们需要：97+2=99

2）96个箱子，分别只含水果#1到#96，和2个箱子，含水果#97，2个箱子，含水果#98，根据上面定理，我们需要：96+1+1=98

两者中取最坏：我们至少需要取99个箱子。

现在考虑100个箱子，3种水果的情况，只有3种水果保留，其余97种不得不变成所保留的3种水果之一。有很多种方法，但是，只含水果#1的箱子数 X1+只含水果#2的箱子数 X2+只含水果#3的箱子数 X3 = 100。

最坏情况下，X1，X2，X3中两个奇数，一个偶数，所以，最终所需要取的箱子数为51。

用此方法，可以给出100个箱子，不同水果种类的所需的最小数量箱子的全部结论：

水果种类，所需取的最小箱子数
100，100
99，99
98，99
97，98
96，98
..........
..........
..........
9，54
8，54
7，53
6，53
5，52
4，52
3，51
2，51
1，50

用公式表示，100个箱子，N种水果（N〈=100），则至少需要取：

50 + N/2 （N为偶数）
50 +（N-1）/2 （N为奇数）

个箱子，来确保这些箱子中的每种水果之和都大于其余箱子中对应水果之和。