Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A farmer has c chickens who have each laid e eggs, which she will put into b baskets. Each basket has a probability p(d) of being dropped, which breaks all the eggs in the basket. How should the farmer distribute the eggs into the baskets in such a way that she minimizes the number of chickens whose eggs all get broken?

share|improve this question
    
Do all baskets have the same $P(d)$ or does each basket have a different probability $P(d_b)$? –  KeithS Aug 20 '12 at 14:49
    
I intended same P(d), but I'd also be interested to see how things change if it were variable. –  jfager Aug 20 '12 at 15:01
7  
Very gently.... –  Graphth Aug 20 '12 at 15:10
    
I've asked a follow-up about minimizing the probability of s or more sad chickens, rather than simply minimizing the expected number of sad chickens. –  jfager Aug 21 '12 at 0:14
    
@Graphth I wouldn't comment about it but... I laughed so hard at it. –  Vladimir Putin Aug 21 '12 at 10:40

3 Answers 3

up vote 5 down vote accepted

We assume that the probability any particular basket gets dropped is $p$, and that droppings are independent. Let $S$ be the total number of sad chickens (a chicken is sad eggsactly if all her eggs get broken).

The number $S$ of sad chickens is a random variable. We interpret minimizing $S$ as minimizing the expectation of $S$.

For each chicken $C_i$, distribute her eggs so that as many baskets as possible have an egg from $C_i$. The number of baskets that have some of her eggs is then $m$, where $m=\min(e,b)$. Let $S_i=1$ if $C_i$ becomes sad, and $0$ otherwise. Then $S=\sum S_i$.

We have $E(S_i)=p^m$, so by the linearity of expectation, $E(S)=cp^m$. Thus as long as we do the obvious spreading out of each chicken's eggs, the expected number of sad chickens does not depend on other details of the distribution process.

share|improve this answer
    
Consider the situation: 2 chickens laying 3 eggs each, and 4 baskets. Now if you impose the condition that all eggs of one chicken should be in different baskets, you have two possibilities: First, for each chicken, put one egg each in basket 1 to 3, and leave basket 4 empty. The expected number of sad chickens is $2p^3$. Second, put the eggs of chicken 1 in baskets 1 to 3, and the eggs of chicken 2 in baskets 2 to 4. Now the expected number of sad chickens is $2p^3-p^4<2p^3$ because only if you drop all four baskets both chickens will be sad. –  celtschk Aug 20 '12 at 15:41
    
@celtschk: In your second distribution, probability of exactly $1$ sad is $2p^3(1-p)$, probability of $2$ sad is $p^4$, expectation is $(1)(2p^3(1-p))+2p^4=2p^3$. –  André Nicolas Aug 20 '12 at 15:55
    
Oops, you're right, I miscalculated. –  celtschk Aug 20 '12 at 16:05
    
@celtschk: One nice thing about linearity of expectation is that one does not have to worry about possibly complex dependencies. –  André Nicolas Aug 20 '12 at 16:08
    
That's a fact I wasn't previously aware of, but which now allowed me to solve the general case (non-equal probabilities). –  celtschk Aug 20 '12 at 16:39

The question leads to two very important lemmas:

  • The eggs $e$ from each chicken $c$ should be distributed among as many baskets as possible.
  • More eggs should go into the baskets least likely to be dropped (assuming each basket has a different probability of being dropped).

The first lemma is easy enough to plan for; for eggs $e$ and baskets $b$, $\dfrac{e}{b}$ eggs should go into each basket. If all baskets have the same $P(d)$, then really we're done here; all we can do is ensure that at least one of each chicken's eggs have the maximum chance to survive by maximizing the number of baskets containing an egg from each chicken (and thus minimizing the probability that all baskets containing one chicken's eggs are dropped; the probability of all baskets being dropped is equal to the product of the probabilities of each basket being dropped).

The second lemma is trickier, but straightforward; the baskets least likely to be dropped should be preferred to those more likely to be dropped for each chicken's eggs. To figure that, first find the mean of all $P(d_b)$, $\overline{P(d)}$. Then, the bias for or against any egg to be placed in any basket is $\dfrac{P(d_b)}{\overline{P(d)}}$. So, the number of eggs each basket should get is $\dfrac{e}{b} * \dfrac{P(d_b)}{\overline{P(d)}}$.

Now, this is extremely likely to produce a fractional rational result. Also, if there is one basket with a relatively very small chance to be dropped, this could result in all eggs going into that one basket; if the one basket's chance to be dropped is still higher than the chance of every other basket being dropped at the same time, this is not the best method. Since we're dealing with whole eggs (and want to keep it that way), you may instead distribute the eggs into the baskets, one at a time, in order of the "best" basket (highest value) to the "worst"; thus, the best basket gets more eggs than the worst (if they don't divide evenly) but the eggs are still distributed evenly enough to maximize the chances of at least one basket with each chicken's eggs surviving.

share|improve this answer

With different dropping probabilities for each basket, you should employ the following strategy:

For each chicken, put the first egg into the basket with the least probability to be dropped, the second egg into the basket with the second-least probability to be dropped, and so on. As soon as each basket has an egg of the chicken, it no longer matters where you put the other eggs (because the quantity you want to minimize is the number of chickens losing all eggs, not the expected number of broken eggs; as soon as all baskets have at least one egg of a chicken, you lose all eggs of that chicken iff you drop all baskets, no matter how the eggs are distributed).

This can be seen as follows:

First, the probability of a given chicken losing all eggs is the probability of losing all baskets which contain at least one egg. Therefore if there's at least one basket with more than one egg, and at least one basket without one egg, you can decrease the probability by moving one of the eggs from the two-egg basket to the no-egg basket (unless the probability of losing that basket is $1$, of course).

Second, you obviously can decrease the probability of losing all eggs of one chicken if you move all eggs from one basket into another empty basket that has less probability of being dropped.

So as long as you can do one of those moves, you are not at the minimum. Especially, for the minimum there may not be an empty basket with less probability than a non-empty basket, and furthermore, if not all baskets are filled, each basket may contain only one egg. The above filling rule ensures the two properties.

Note that "empty" in those considerations above has to be considered for each chicken separately. That is, a basket that contains eggs from another chicken is still considered "empty" if it doesn't contain any eggs from the chicken under consideration.

Note that this rule works even if you have a different numkber of eggs for each chicken.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.