# Can You Hand Out All The Candy?¶

## Riddler Classic¶

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?

## Solution¶

Let $t$ represent the the number of trick or treaters.

I looked at a few "lazy" strategies first.

### Give 150 trick-or-treaters 1 candy each.¶

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$.

### Give 50 trick-or-treaters 3 candies each.¶

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$.

### Give 75 trick-or-treaters 2 candies each.¶

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:

1. You plan for exactly 100 trick-or-treaters.
2. You plan for the last 50 trick-or-treaters to receive only 1 candy each.

All strategies that satisfy the conditions above are as follows:

• The first 50 receive 2 each. The last 50 receive 1 each.
• The first 50 is some order of 1 receiving 3, 48 receiving 2 each, and 1 receiving 1. The last 50 receive 1 each.
• The first 50 is some order of 2 receiving 3 each, 46 receiving 2 each, and 2 receiving 1 each. The last 50 receive 1 each.
• ...
• The first 50 is some order of 24 receiving 3 each, 2 receiving 2 each, and 24 receiving 1 each. The last 50 receive 1 each.
• The first 50 is some order of 25 receiving 3 each and 25 receiving 1 each. The last 50 receive 1 each.

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}$.