悬赏1000伪币水果问题应征 - 未名空间MITBBS历史存档

a*02007-11-03 07:11

1 楼

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

d*q2007-11-03 07:11

2 楼

中间有一点没看懂
先给你M上
然后让大家看看先
呵呵

【在 a*****0 的大作中提到】

: 100个箱子，里面放苹果、梨、橘子，可以混合
: 问：不管怎么放这些水果，是不是总能挑出51个箱子，使这51个箱子里的苹果、梨、橘
: 子分别都不少于其他49个箱子里的苹果、梨、橘子？
: =====================================================================
: 先做些准备工作：
: （1）
: 对于N个含同一种类水果的箱子，可以找到N/2（N是偶数），或（N+1）/2（N是奇数）
: 个箱子，使得这N/2或（N+1）/2个箱子中的水果大于等于其余箱中的水果。这是显而易
: 见的，比如，100个箱子，按箱内水果数量从多到少排序，前50个箱子的水果之和肯定
: 大于等于后50个箱子的水果之和。

o*s2007-11-03 07:11

3 楼

http://blog.wenxuecity.com/blogview.php?date=200711&postID=2401

a*02007-11-03 07:11

4 楼

发帖时间也很接近噢~
2-3分钟之内，周六凌晨3点~

【在 o******s 的大作中提到】

: http://blog.wenxuecity.com/blogview.php?date=200711&postID=2401

a*02007-11-03 07:11

5 楼

a*02007-11-03 07:11

6 楼

M*H2007-11-03 07:11

7 楼

每个箱子必须满吗？

【在 a*****0 的大作中提到】

: 100个箱子，里面放苹果、梨、橘子，可以混合
: 问：不管怎么放这些水果，是不是总能挑出51个箱子，使这51个箱子里的苹果、梨、橘
: 子分别都不少于其他49个箱子里的苹果、梨、橘子？
: =====================================================================
: 先做些准备工作：
: （1）
: 对于N个含同一种类水果的箱子，可以找到N/2（N是偶数），或（N+1）/2（N是奇数）
: 个箱子，使得这N/2或（N+1）/2个箱子中的水果大于等于其余箱中的水果。这是显而易
: 见的，比如，100个箱子，按箱内水果数量从多到少排序，前50个箱子的水果之和肯定
: 大于等于后50个箱子的水果之和。

a*02007-11-03 07:11

8 楼

你是说题意？我的理解是可以空着，你甚至可以有100个空箱子，那么原题假设仍然成
立，仍然可以找到51个空箱子，使得这51个空箱子里的0不少于49个空箱子里的0

【在 M******H 的大作中提到】

: 每个箱子必须满吗？

d*e2007-11-03 07:11

9 楼

还没看完，但是好像有点小问题。

这里只需要97+1吧？
假设另4个箱子两种水果数如下：
4 1
3 2
2 3
1 4
需要全取才行。
数

【在 a*****0 的大作中提到】

: 100个箱子，里面放苹果、梨、橘子，可以混合
: 问：不管怎么放这些水果，是不是总能挑出51个箱子，使这51个箱子里的苹果、梨、橘
: 子分别都不少于其他49个箱子里的苹果、梨、橘子？
: =====================================================================
: 先做些准备工作：
: （1）
: 对于N个含同一种类水果的箱子，可以找到N/2（N是偶数），或（N+1）/2（N是奇数）
: 个箱子，使得这N/2或（N+1）/2个箱子中的水果大于等于其余箱中的水果。这是显而易
: 见的，比如，100个箱子，按箱内水果数量从多到少排序，前50个箱子的水果之和肯定
: 大于等于后50个箱子的水果之和。

a*02007-11-03 07:11

10 楼

3 个箱子，在最坏情况下，要取2个箱子，才能确保取的不小于剩的
4个箱子在两个种水果里分，1-3，和 2-2，至于0-4，肯定不是worst case。

【在 d*e 的大作中提到】

: 还没看完，但是好像有点小问题。
:
: 这里只需要97+1吧？
: 假设另4个箱子两种水果数如下：
: 4 1
: 3 2
: 2 3
: 1 4
: 需要全取才行。
: 数

d*e2007-11-03 07:11

11 楼

哦。我对题目的理解有问题，这个分别不少于因该是水果的总数。不好意思

【在 a*****0 的大作中提到】

:
: 3 个箱子，在最坏情况下，要取2个箱子，才能确保取的不小于剩的
: 4个箱子在两个种水果里分，1-3，和 2-2，至于0-4，肯定不是worst case。

h*02007-11-03 07:11

12 楼

有一点问题。所谓的“最坏”情况没有定义，在100种水果时的最坏情况，未必是3种水
果时的最坏情况。似乎最后只证明了没有混和水果时的情况。还得证明有混和时不比没
有混和时“坏”。

【在 a*****0 的大作中提到】

: 100个箱子，里面放苹果、梨、橘子，可以混合
: 问：不管怎么放这些水果，是不是总能挑出51个箱子，使这51个箱子里的苹果、梨、橘
: 子分别都不少于其他49个箱子里的苹果、梨、橘子？
: =====================================================================
: 先做些准备工作：
: （1）
: 对于N个含同一种类水果的箱子，可以找到N/2（N是偶数），或（N+1）/2（N是奇数）
: 个箱子，使得这N/2或（N+1）/2个箱子中的水果大于等于其余箱中的水果。这是显而易
: 见的，比如，100个箱子，按箱内水果数量从多到少排序，前50个箱子的水果之和肯定
: 大于等于后50个箱子的水果之和。

a*02007-11-03 07:11

13 楼

这里所谓的“最坏情况”，就是要取出的箱子数尽可能高。否则，如果所有水果都集中
在一个箱子里，那么，只取出一个箱子就足够了。
在水果混合状态下，也是成立的，原贴中限于篇幅，没有列出来。下面说一下：
1）100个箱子，99种水果：
水果#100不得不变成其它水果，如果箱子#100只含单一种类水果（水果#1-#99中任何一
种），那么已经在原贴中证明。如果是混合状态，就要把所含所有种类一一过一遍。因
为各种水果是单独结算的，所以，在过所含的每一种水果，可以忽略其它水果。所以，
混合水果和单一水果的情况没有区别，只增加了O（n）的工作量而已，唯一的区别是，
混合水果是有可能减少应该取出的总箱数，使问题向“最坏情况”的相反方向发展。而
不是向“更坏”方向发展。比如，如果箱子#100有两种水果：#1和#2，如果取出它，可
以“一举两得”，顶了水果#1和#2的两个单箱。实际上降低了所要取出的箱数。
2）100个箱子，98种水果：
同样，只增加O(n)的工作量，只能使使问题向“最坏情况”的相反方向发展。而不是向
“更坏”方向发展。
3）100个箱子，3种水果：
同上。
所以，混合水果情况和单一水果比，

【在 h*****0 的大作中提到】

: 有一点问题。所谓的“最坏”情况没有定义，在100种水果时的最坏情况，未必是3种水
: 果时的最坏情况。似乎最后只证明了没有混和水果时的情况。还得证明有混和时不比没
: 有混和时“坏”。

y*z2007-11-03 07:11

14 楼

你这个证明是不成立的

数

【在 a*****0 的大作中提到】

: 100个箱子，里面放苹果、梨、橘子，可以混合
: 问：不管怎么放这些水果，是不是总能挑出51个箱子，使这51个箱子里的苹果、梨、橘
: 子分别都不少于其他49个箱子里的苹果、梨、橘子？
: =====================================================================
: 先做些准备工作：
: （1）
: 对于N个含同一种类水果的箱子，可以找到N/2（N是偶数），或（N+1）/2（N是奇数）
: 个箱子，使得这N/2或（N+1）/2个箱子中的水果大于等于其余箱中的水果。这是显而易
: 见的，比如，100个箱子，按箱内水果数量从多到少排序，前50个箱子的水果之和肯定
: 大于等于后50个箱子的水果之和。

d*q2007-11-03 07:11

15 楼

说说问题吧
虽然我也觉得中间有点不是很清楚
呵呵

【在 y*z 的大作中提到】

: 你这个证明是不成立的
:
: 数