8

Shi Yue 999027873

Exercise 1. A survey is conducted among 50 students, asking which of three sports they like: football, basketball, and tennis. The results are as follows:

30 like football,
25 like basketball,
20 like tennis,
15 like both football and basketball,
10 like both basketball and tennis,
12 like both football and tennis,
5 like all three sports.

How many students do not like any of these three sports?

Consider $A=\{\text{students who like football}\}$, $B=\{\text{students who like basketball}\}$, $C=\{\text{students who like tennis}\}$

From above we know $|A|=30$, $|B|=25$, $|C|=20$, $|A\cap B|=15$, $|B\cap C|=10$, $|A\cap C|=12$, $|A\cap B\cap C|=5$

Then by formula we know $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Then $|A\cup B\cup C|=30+25+20-15-10-12+5=43$

Thus there are 43 students like these three sprots

And $\{\text{students}\}=\{\text{students like these three sprots}\}\cup\{\text{students do not like any of these three sports}\}$

Thus there are 7 students do not like any of these three sports.

Exercise 2. Compute the number of even 4-digit positive integers with no repeated digits.

First we decide the possibilities of the fourth digit which must be even. There are $5$ possibilities.

Then if the fourth digit is $0$, then there are $9$ possibilities for the first digit.

Then $8$ possibilities for the second digit, then $7$ possibilities for the third digit

If the fourth digit is not $0$($4$ possibilities), then there are $8$ possibilities for the first digit.

Then $8$ possibilities for the second digit, then $7$ possibilities for the third digit

Finally, there are $1\times9\times8\times7+4\times8\times8\times7=2296$ possibilities of even 4-digit positive integers with no repeated digits.

Exercise 3. A committee of 5 people is to be formed from a group of 8 women and 6 men. How many such committees can be formed if:

(a) There are no restrictions.

$\binom{14}{5}=2002$

(b) The committee must include exactly 3 women.

$\binom83\binom62=840$

(c) The committee must include at least 3 women and 1 man.

$\binom83\binom62+\binom84\binom61=1260$

Exercise 4. Prove the following identities.

(a) If $k \leq m \leq n$ are positive integers, then $\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$

$\binom{n}{k}\binom{n-k}{m-k}=\frac{n!}{\left(n-k\left)!\right.k!\right.}\cdot\frac{\left(n-k\right)!}{\left(n-m\left)!\right.\left(m-k\right)!\right.}=\frac{n!}{\left(n-m\left)!\right.\left(m-k\right)!\right.}\cdot\frac{\left(n-k\right)!}{\left(n-k\left)!\right.k!\right.}=\frac{n!}{\left(n-m\left)!m!\right.\right.}\cdot\frac{m!\left(n-k\right)!}{\left(m-k\right)!\left(n-k\left)!\right.k!\right.}=\binom{n}{m}\frac{m!}{\left(m-k\right)!k!}=\binom{n}{m}\binom{m}{k}$

(b) For any positive integer $n$: $\binom{2n}{n}+\binom{2n}{n+1}=\frac12\binom{2n+2}{n+1}$

Since $\binom{2n}{n}+\binom{2n}{n+1}=\frac12\binom{2n+2}{n+1}\;\iff\;\binom{2n}{n}+\binom{2n}{n-1}=\frac12\binom{2n+2}{n+1}$, then we prove last one

$\binom{2n}{n}+\binom{2n}{n-1}=\frac{2n!}{n!n!}+\frac{2n!}{\left(n-1\left)!\left(n+1\right)!\right.\right.}=\frac{2n!\left(2n+1\right)\left(2n+2\right)}{n!n!\left(2n+1\right)\left(2n+2\right)}+\frac{2n!\left(2n+1\right)\left(2n+2\right)}{\left(n-1\left)!\left(n+1\right)!\right.\right.\left(2n+1\right)\left(2n+2\right)}$

$\quad\quad\quad\quad\quad=\frac{\left(2n+2\left)!\right.\right.}{n!n!\left(2n+1\right)\left(2n+2\right)}+\frac{\left(2n+2\left)!\right.\right.}{\left(n-1\right)!\left(n+1\right)!\left(2n+1\right)\left(2n+2\right)}$

Since $\frac12\binom{2n+2}{n+1}=\frac12\frac{\left(2n+2\right)!}{\left(n+1\left)!\left(n+1\right)!\right.\right.}$, then we need to prove $\frac{1}{n!n!}+\frac{1}{\left(n-1\right)!\left(n+1\right)!}=\frac12\frac{\left(2n+1\right)\left(2n+2\right)}{\left(n+1\left)!\left(n+1\right)!\right.\right.}$

Then N.T.P. $\frac{1}{n!n!}+\frac{1}{\left(n-1\right)!\left(n+1\right)!}=\frac{\left(2n+1\right)}{\left(n+1\left)!n!\right.\right.}\Rightarrow\frac{1}{n!}+\frac{1}{\left(n-1\right)!\left(n+1\right)}=\frac{\left(2n+1\right)}{\left(n+1\left)!\right.\right.}\Rightarrow\frac{\left(n+1\right)!}{n!}+\frac{\left(n+1\right)!}{\left(n-1\right)!\left(n+1\right)}=\left(2n+1\right)$

Then N.T.P. $\left(n+1\right)+\frac{\left(n+1\right)n}{n+1}=\left(2n+1\right)$, then our goal is equivalent to prove this is true

Since $(n+1)+n=2n+1$, thus this is true

Thus $\binom{2n}{n}+\binom{2n}{n-1}=\frac12\binom{2n+2}{n+1}$

Thus $\binom{2n}{n}+\binom{2n}{n+1}=\frac12\binom{2n+2}{n+1}$

$$

‍