Five pills problem from exercises based on Feynman's lectures

236 Views Asked by At

enter image description here I have some questions about the solution to the five pills problem which is part of the list of exercises based on Feynman's lectures. form

In the solution above m is the number of types of pills and there are n pills of each type for a total of mn pills. K is the number of pills drawn without replacement.

I understand how the principle of inclusion exclusion was used to find L(m,n,k) but am unsure how in the above solution the expression for O(m,n,k) was arrived at. Also, how can it be valid if in the summation j ranges from 0 to m and j-m-1 is negative for these values of j?

2

There are 2 best solutions below

7
On BEST ANSWER

There are altogether $\binom{mn}k$ combinations of $k$ pills, and $L(m,n,k)$ of them lack at least one pill type, so $\binom{mn}k-L(m,n,k)$ of them contain all types. And

$$\begin{align*} \binom{mn}k&-L(m,n,k)\\ &=\binom{mn}k-\sum_{j=1}^m(-1)^{j-1}\binom{m}j\binom{mn-jn}k\\ &=(-1)^0\binom{m}0\binom{mn-0\cdot n}k-\sum_{j=1}^m(-1)^{j-1}\binom{m}j\binom{mn-jn}k\\ &=(-1)^0\binom{m}0\binom{mn-0\cdot n}k+\sum_{j=1}^m(-1)^j\binom{m}j\binom{mn-jn}k\\ &=\sum_{j=0}^m(-1)^j\binom{m}j\binom{(m-j)n}k\\ &=\sum_{j=0}^m\binom{j-m-1}j\binom{(m-j)n}k \end{align*}$$

by virtue of the identity

$$\binom{r}k=(-1)^k\binom{k-r-1}k$$

(with the factor of $(-1)^k$ brought over to the other side).

The binomial coefficient $\binom{r}k$ is defined for all real (and even complex) numbers $r$ and integers $k$ as follows:

$$\binom{r}k=\begin{cases} \frac{r^{\underline{k}}}{k!},&\text{if }k\ge 0\\ 0,&\text{if }k<0\,, \end{cases}$$

where

$$r^{\underline{k}}=r(r-1)\ldots(r-k+1)=\prod_{i=0}^{k-1}(r-i)$$

is a falling factorial. Thus, negative values of $j-m-1$ are not a problem. In fact you can see that $(j-m-1)^{\underline{j}}$ is a product of $j$ negative numbers and so is negative when $j$ is odd and positive when $j$ is even, just like $(-1)^j$.

5
On

I am going to answer the question, "how can it be valid" in an anecdotal way, which applies to my solution as a whole, and not just the one step quoted here by RobPratt.

Matthew Sands, coauthor of The Feynman Lectures on Physics, posed the "five pills" problem to me, on (as I recall) my 2nd or 3rd visit to his home in Santa Cruz, California in 2002. He was, in fact, at the time, taking one each of 5 types of pills a day, inadvertently conducting the experiment described in the exercise, and he had noticed that on the first day of each month (when there were ~150 pills in the bottle) he had to spill out "about 10" pills - twice as many as he needed to take - before he got one of each of the five types, and wondered why that was so. This was a problem I worked on occassionally over a couple of years. My first attempt used questionable methods of approximation that resulted in an answer of 8, which Matt was very displeased with, since it disagreed with his experimental observations! Then I decided to solve the problem numerically, using brute force, by calculating the length and probability of every possible sequence of pills that included at least one of each type! That way I would at least know what the answer should be. After that I thought about it occasionally during my early morning dog walks, until one day it dawned on me how to solve it exactly. When I had made the calculation using my exact solution, it matched my numerical approximation to about 20 decimal places, so I figured I must have got it right both times (otherwise such an exact match from two entirely different ways of calculating the answer would be extremely unlikely), and I let Matt know the result of his experiment should be "about 11," which he seemed happier with. Anyway... that was how I validated my solution(s) to this problem.