We are, in effect, asked to minimize our expected regret \(X\) which can be caused by candyless trick or treaters (call this \(X_1\) ), or leftover candy \(X_2\).  

We don’t know the number of kids that will come knocking beforehand—only the distribution of the number of kids. So we have to evaluate how any strategy performs against 101 equally likely possibilities (when we could end up with anywhere between 50 and 150 trick or treaters). Each possibility has a probability \(p = \displaystyle \frac{1}{101} \)

Let us plan to have our last piece(s) of candy be handed out to kid number \(N\).

Kids \(N+1\) to 150 will not get any candy. We will possibly disappoint 1,2,3…., OR at most \(150-N\) kids, each with probability \(p\).  Hence \(X_1\) the expected regret from running out of candy too early is:

\begin{align*}
X_1 &= p\left [ 1 \ + \ 2 \ + \ 3\ + \ … \ +\ (150-N) \ \right ] \\ \\
&= p \left [ \frac{(150 – N)(1 + 150 – N)}{2} \right ] \quad \textit{(sum of first 150-N integers)} \\ \\
&= \frac{p}{2} \left [ (150 – N)(151 – N) \right ]
\end{align*} 

Now consider instances when fewer than \(N\) kids show up: i.e. 50, 51, 52….., or \(N-1\) kids show up, each instance having a probability \(p\) . Let us also assume that as part of our strategy we plan to give out \(c_x\) pieces to kid number \(x\) where each \( c_x\) is 1,2, or 3 and \(x\) is between 50 and \(N-1\). 

Our leftover candy regret \(X_2 \) is now:

\begin{align*}
X_2 &= p\left [(c_N) \ + \ (c_N + c_{N-1}) \ + \ … \ + \ (c_N + c_{N-1} + … + c_{51} ) \right ]
\end{align*}

It should be obvious that no matter what \(N\) we pick, it’s best to handout exactly one candy to each kid after the first 50 to minimize \(X_2\),  i.e. each \(c_x\) is 1.  Consequently \(X_2\) can now be written as:

\begin{align*}
X_2 &= p\left [1 \ + \ 2 \ + \ … \ + \ (N – 50 ) \right ] \\ \\
&= p\left [ \frac{(N-50)(1 + N-50)}{2} \right ]  \quad \textit{(sum of first N – 50 integers)} \\ \\
&= \frac{p}{2}\left [(N-50)(N-49) \right ]
\end{align*}

Our total regret \(X\) is then the sum of \(X_1\) and \(X_2\):

\begin{align*}
X &= X_1 + X_2 \\ \\
&= \frac{p}{2}\left [(150 – N)(151 – N) \ + \ (N-50)(N-49) \right ] \\ \\
&= \frac{p}{2}\left [ 2N^2 \ – \ 400N \ + \ 25100 \right ]
\end{align*}

Intuitively, the symmetry of the situation with leftover candy and disappointed kids counting the same, tells us that the optimum value of \(N\) has to be such that we have equal likelihood of running out of candy as we do of running out of trick or treaters. i.e. \(N = 100\).

This can be seen by differentiating \(X\) w.r.t. \(N\) (treating N as continuous) and setting to zero (and verifying \(X”\) is positive):

\begin{align*}
X’ &= \frac{p}{2}\left [ 4N – 400 \right ] \\ \\
& \textit{ N = 100 is an extremum and a minimum since…} \\ \\
X” &= \frac{p}{2} . 4 \ = 2p \ > \ 0
\end{align*}

If we plan to run out of candy at kid #100 and also plan to give 1 each to number 51 through number 100, we will need to give away 100 candies to the first 50 trick or treaters.

Hence our optimal strategy is to plan to run out of candy at kid 100 by giving away 100 to the first 50 (say by handing out 2 each to the first 50 trick or treaters) and 1 each thereafter. The expected regret \(X\) = 25.25%  i.e. on average we will either have a little over 25 pieces of candy left over or disappoint a little over 25 kids.