MATHCOUNTS Exercises – 10

Solution 1 – Brute Force Label the backpacks 1, 2, 3, 4, owned by Joseph, Pedro, Samuel and David respectively. There are total $P(4)=4!=24$ possible assignments of backpacks to the four boys:

$$\begin{array}{l|c|c|c|c} Joseph&\texttt{111111}&\texttt{222222}&\texttt{333333}&\texttt{444444} \\ Pedro &\texttt{223344}&\texttt{113344}&\texttt{112244}&\texttt{112233} \\ Samuel&\texttt{342423}&\texttt{341413}&\texttt{241412}&\texttt{231312} \\ David &\texttt{434232}&\texttt{434131}&\texttt{424121}&\texttt{323121} \\ &\texttt{xxxxxx}&\texttt{x*x**x}&\texttt{x*xx**}&\texttt{*xxx**} \\ \end{array} $$

Therefore, there are 9 ways to assign backpacks to four boys without each of them taking his own. So the answer to the question is $$\dfrac{9}{24}=\dfrac{3}{8}$$

Solution 2 There are 2 ways when Joseph gets his own backpack, while none of the other three boys get their own backpacks. Therefore, there are ${4\choose 1}\times 2=4\times 2=8$ ways to have exactly one boy getting his own backpack.

There is only 1 way for both Joseph and Pedro get their own backpacks, but Samuel and David do not. Therefore, there are ${4\choose 2}\times 1=6$ ways to have exactly two boys getting their own backpacks.

There is only 1 way for all four boys getting their own backpacks. Additionally, it is impossible to have exactly three boys getting their own backpacks, as the remaining boy must also have his own backpack.

Therefore there are $8+6+1=15$ ways to have at least one boy getting his own backpack. Using the complementary principle, the probability of none of the boys getting his backpack is $$1-\dfrac{15}{24}=\dfrac{3}{8}$$

Solution 3 Define $f(m,n)$ as the number of ways to assign $m$ backpacks so that exactly $n$ out of $m$ boys have their own backpacks. We have

$$\begin{array}{ll} f(1,1)&=1 \\ f(1,0)&=0 \\ \\ f(2,2)& = 1 \\ f(2,1)& = 0 \\ f(2,0)& = 1 \\ \\ f(3,3)& = 1 \\ f(3,2)& = 0 \\ f(3,1)& = 3 \\ f(3,0)& = 2 \\ \\ f(m,m)& = 1 \\ f(m,m-1)& = 0 \\ f(m,m-2)& = {m\choose m-2}f(2,0) \\ f(m,m-3)& = {m\choose m-3}f(3,0) \\ … \\ f(m,n)&={m\choose n}f(m-n,0) \\ … \\ f(m,1)&={m\choose 1}f(m-1, 0) \\ f(m,0)&=P(m)-\sum_{i=1}^{m}f(m, i) \\ &= P(m)-1-\sum_{i=1}^{m-2}f(m, i)\\ &= P(m)-1-\sum_{i=1}^{m-2}{m\choose i }f(m-i,0)\\ \end{array} $$

Therefore, the total number of ways that none of the four boys getting his own backpack, is

$$\begin{align} f(4,0)&=P(4)-1-\sum_{i=1}^{2}{4\choose i}f(4-i,0)\\ & = P(4)-1-{4\choose 1}\cdot f(3,0)-{4\choose 2}\cdot f(2,0) \\ & =24-1-4\cdot 2-6\cdot 1=9\\ \end{align}$$

Finally, the probability of none of the boys getting his backpack is $$\dfrac{9}{24}=\dfrac{3}{8}$$

Solution 4 – Use Inclusion-Exclusion Principle Define $g(m,n)$ as ways (or permutation set) to assign $m$ backpacks so that the $n^{th}$ boy getting his own backpack. Therefore, the total number ways to have at least one boy getting his own backpack is the size of set

$$g(m,1)\cup g(m,2)\cup … \cup g(m,m)$$

According to the inclusion-exclusion principle, the size of the above set is

$$ |g(m,1)|-|g(m,2)|+|g(m,3)|-…+(-1)^{m+1}|g(m,m)| \tag{1}$$ Because $$|g(m,n)|={m\choose n}\cdot(n-k)!=\dfrac{m!}{n!}$$

therefore $(1)$ becomes

$$\dfrac{m!}{1!}-\dfrac{m!}{2!}+\dfrac{m!}{3!}-…+(-1)^{m+1}\dfrac{m!}{m!} \tag{2}$$

Therefore, the number of ways that none of boys gets his backpack is

$$m!-\left(\dfrac{m!}{1!}-\dfrac{m!}{2!}+\dfrac{m!}{3!}-…+(-1)^{m+1}\dfrac{m!}{m!}\right)$$

i.e.

$$m!\sum_{n=0}^{m}\dfrac{(-1)^n}{n!} \tag{3}$$

The probability that none of the boys gets his backpack is

$$\sum_{n=0}^{m}\dfrac{(-1)^n}{n!} \tag{4}$$

For $m=4$, we have

$$\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}=\dfrac{9}{24}=\dfrac{3}{8}$$

Note: As $m$ grows, $(4)$ is getting closer to $\dfrac{1}{e} \approx 0.367879$.