Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\W{\mathbb W}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cN{\mathcal N}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\cF{\mathcal F}
\def\cX{\mathcal X}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\newcommand{\pile}[1]{\bullet{#1}}
\def\g{g}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Chapter 17 Inclusion/Exclusion
Exercises Practice Problems
1. Rolling 10 Dice.
We roll 6-sided die 10 times, and then list the outcomes in order as \((x_1, x_2, \ldots , x_{10} )\text{.}\) We are interested in counting the total number outcomes in which both 1 appears and 2 appears. We break this process into multiple steps.
Let \(X\) be the set of all possible outcomes \((x_1, x_2, \ldots , x_{10} )\text{.}\) What is \(|X|\text{?}\)
Let \(X_1\) be the set of outcomes that do not contain any 1's. I would call \(X_1\) the set of "bad outcomes for 1." What is \(|X_1|\text{?}\)
Define \(X_2\) in the same way as in part (b), where \(X_2\) is the set of "bad outcomes for 2." What is \(|X_2|\text{?}\)
How many outcomes are there in which neither 1 or 2 appears? How would you describe this set using the symbols \(X_1\) and \(X_2\text{?}\)
Use inclusion-exclusion to find the number of outcomes in which either 1 does not or appear or 2 does not appear (or both do not appear). This account for all the "bad outcomes."
Now use your answer from part (d) to find the number of "good outcomes." Namely, how many outcomes contain both 1 and 2?
2. I Hate 2, 5, and 7.
In this question, you will determine how many numbers between 1 and 140 are not divisible by any of 2, 5 or 7. As in the previous question, we start by counting the complement of the set we are interested in (because it is easier to count).
Negate the statement "\(n\) is not divisible by any of 2, 5 and 7."
The set of numbers that you described in part (a) can be found using inclusion-exclusion. Do so.
Use your answer to (b) to find how many numbers in [140] are not divisible by any of 2, 5 and 7.