三种类型的球从袋 [英] Three type of Balls from Bag

问题描述

我有一个问题，听起来像这样：
我们有一个有球的袋子。有R红球，B蓝球和G绿球。
我需要找到从包中提取的最少数量，我确信我将至少有K个相同颜色的球。

任何人都可以帮助任何想法？ c> 如果 K> max（R，G，B）那么问题没有解决方案。所以让我们假设 K <= max（R，G，B）。

对于哪个球被提取的任何控制，你将最多需要（即，这是下界） min（R，（K-1））+ min （K-1））+ min（B，（K-1））+ 1 提取出现明显的原因：提取 K-1 （或者如果 R ，则所有红色球），然后提取 K-1 G ），最后提取 K-1 蓝色球> B ）。现在有至少一个球剩余---因为 max（R，G，B）> = K 通过假设---当我们提取它， code> K 相同颜色的球。 （这显然是最坏的情况。）

你显然需要至少 K 提取（这是最好的情况）。

由于您使用 probability 标记问题，也许你只能随机提取一个均匀选择的球。在这种情况下，我们可以谈论预期的提取次数，然后我们结束相同颜色的 K 球。这是一个有趣的问题。

I have a problem which sounds like this: We have a bag with balls in. There are R red balls, B blue balls and G green balls. I need to find the minimum number of extractions from the bag such that i am sure that i will have at least K balls of same colour.

Anyone can help with any idea? Or tips, etc?

解决方案

If K>max(R,G,B) then the problem has no solution. So let's assume K <= max(R,G,B).

If you don't have any control over which ball gets extracted, you'll need at most (i.e. this is a lower bound) min(R, (K-1))+min(G, (K-1))+min(B, (K-1))+1 extractions for obvious reasons: extract K-1 red balls (or all red balls if R<K), then extract K-1 green balls (or all green balls if G<K), and finally extract K-1 blue balls (or all blue balls if B<K). Now there is at least one ball remaining---because max(R,G,B)>=K by assumption---and when we extract it we have K balls of the same color. (This is clearly the worst case.)

You obviously need at least K extractions (this is the best case).

Since you tagged the question with probability, maybe you can only extract a ball chosen uniformly at random. In that case we can talk of the expected number of extractions needed before we end up with K balls of the same color. This is an interesting question.

这篇关于三种类型的球从袋的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！