For Halloween this year, you have purchased 150 pieces of candy. However, you’re not sure how many trick-or-treaters will visit you. Based on previous years, it could be anywhere from 50 to 150 (inclusive), with each number being equally likely.
As the trick-or-treaters arrive, you can decide to give each of them one, two or three candies. You want to avoid running out of candy, but you also want to avoid having any candy left over. Let X represent the number of trick-or-treaters who won’t get candy (if you do run out) or the number of leftover pieces (if you don’t run out).
This year, the day before Halloween, you come up with a strategy to minimize the expected value of X. What is this minimum expected value?
Let $t$ represent the the number of trick or treaters.
I looked at a few "lazy" strategies first.
Every trick-or-treater will receive candy, but any number of trick-or-treaters less than 150 will correspond to that many leftover candies.
X can be represented as:
$$X(t) = 150-t, 50 \le t \le 150$$The Expected Value is $\dfrac{\sum \limits _{x = 0}^{100} x}{101} = 50$.
There will never be leftover, but every trick-or-treater after the 50th will receive nothing.
X can be represented as:
$$X(t) = t-50, 50 \le t \le 150$$The Expected Value is again $\dfrac{\sum \limits _{x = 0}^{100} x}{101} = 50$.
Any number of trick-or-treaters less than 75 will correspond to twice that many leftover candies.
Every trick-or-treater after the 75th will receive nothing.
X can be represented as:
$$X(t) = \Bigg[ \begin{array}{c} 2(75-t), 50 \le t \le 75 \\ t-75, 75 < t \le 150 \end{array}$$The Expected Value is $\dfrac{2\sum \limits _{x = 0}^{25} x + \sum \limits _{x = 0}^{75} x}{101} = \dfrac{3500}{101} \approx 34.65$.
$X = 0$ exactly once, that is, when the number of trick-or-treaters matches that of the prediction in your strategy. This leaves 100 nonzero values of X. Since the sum of consecutive integers increases quadratically, the minimum expected value occurs when the numerator is two equal summations, which would be $\sum \limits _{x = 1}^{50} x$.
The minimum Expected Value is $\dfrac{\sum \limits _{x = 1}^{50} x + \sum \limits _{x = 1}^{50} x}{101} = \dfrac{2550}{101} \approx 25.25$
This corresponds to strategies which require two simple criteria:
All strategies that satisfy the conditions above are as follows:
The total number of strategies to choose from is the coefficient of $x^{100}$ in the expansion of $(x+x^2+x^3)^{50}$, or more simply the coefficient of $x^{50}$ in the expansion of $(1+x+x^2)^{50}$.