Section Solutions for Chapter 10
Solutions to Exercise 10.1.11
10.1.11.1 Since there are \(\displaystyle 8\) rows on a chessboard, and \(\displaystyle 17>2(8)\text{,}\) the Generalised Pigeonhole Principle says that there must be at least \(\displaystyle 2+1=3\) rooks that are all in the same row of the board. Choose such a row, and call it Row A. Note that Row A contains at most \(\displaystyle 8\) rooks.
There are at least \(\displaystyle 17-8=9\) rooks that are not in Row A. Since there are \(\displaystyle 7\) other rows on the chessboard, and \(\displaystyle 9>1(7)\text{,}\) the Pigeonhole Principle says that there must be at least \(\displaystyle 1+1=2\) rooks that are in the same row, from amongst the other rows of the board. Choose such a row, and call it Row B. Note that Row B also contains at most \(\displaystyle 8\) rooks.
There is at least \(\displaystyle 17-8-8=1\) rook remaining, so there must be a rook somewhere on the board that is in neither Row A nor Row B. Choose such a rook, Rook \(\displaystyle 1\text{,}\) and call the row that it is in Row C. Since there are at least \(\displaystyle 2\) rooks in Row B, at least one of them must not be in the same column as Rook \(\displaystyle 1\text{.}\) Choose such a rook, Rook \(\displaystyle 2\text{.}\) Since there are at least \(\displaystyle 3\) rooks in Row A, at least one of them must not be in the same column as either Rook \(\displaystyle 1\) or Rook \(\displaystyle 2\text{.}\) Choose such a rook, and call it Rook \(\displaystyle 3\text{.}\) Now Rooks \(\displaystyle 1\text{,}\) \(\displaystyle 2\text{,}\) and \(\displaystyle 3\) do not threaten each other, so fulfil the requirements of the problem.10.1.11.3 We use the even more generalised pigeonhole principle with \(\displaystyle n-1=15\) for the adults, and \(\displaystyle n_2=23\) for the children (and \(\displaystyle m=2\) categories: adults and children). The principle tells us that as long as at least
\begin{equation*}
n_1+n_2-m+1=15+23-2+1=37
\end{equation*}
people are approached, the artist will have enough people to carry their art in the parade.Solutions to Exercise 10.2.8
10.2.8.2 Of the basic pieces of information that we need to complete a Venn diagram, one has not been given to us: the number of Kevin's apps that are free and require internet access. Fortunately, we can use inclusion-exclusion to work this out from the others. We use \(\displaystyle F\) to represent the set of free apps; \(\displaystyle G\) to represent the games, and \(\displaystyle I\) to represent the apps that require internet. Then we have been told:
\begin{equation*}
|F|=78, |I|=124, |G|=101, |F\cap G|=58, |G\cap I|=62, |F\cap G\cap I|=48, |F \cup G \cup I|=165\text{.}
\end{equation*}
Using inclusion-exclusion, we have
\begin{equation*}
165=78+124+101-58-62-|F \cap I|+48\text{,}
\end{equation*}
so
\begin{equation*}
|F\cap I|=78+124+101-58-62+48-165=66\text{.}
\end{equation*}
The value we have been asked for is
\begin{equation*}
|F \cap I \cap \overline{G}|=|F\cap I|-|F\cap I\cap G|=66-48=18\text{.}
\end{equation*}
10.2.8.3 The number of integers between \(\displaystyle 1\) and \(\displaystyle 60\) that are divisible by \(\displaystyle 2\) is \(\displaystyle 60/2=30\text{.}\) Call the set of these integers \(\displaystyle A\text{.}\) The number of integers between \(\displaystyle 1\) and \(\displaystyle 60\) that are divisible by \(\displaystyle 3\) is \(\displaystyle 60/3=20\text{.}\) Call the set of these integers \(\displaystyle B\text{.}\) The number of integers between \(\displaystyle 1\) and \(\displaystyle 60\) that is divisible by \(\displaystyle 5\) is \(\displaystyle 60/5=12\text{.}\) Call the set of these integers \(\displaystyle C\text{.}\) Then \(\displaystyle |A\cap B|\) is the number of integers between \(\displaystyle 1\) and \(\displaystyle 60\) that are divisible by \(\displaystyle 2\) and \(\displaystyle 3\text{;}\) that is, the number that are divisible by \(\displaystyle 6\text{.}\) This is \(\displaystyle 60/6=10\text{.}\) Similarly, \(\displaystyle |A\cap C|\) is the number of integers between \(\displaystyle 1\) and \(\displaystyle 60\) that are divisible by \(\displaystyle 2\) and \(\displaystyle 5\text{;}\) that is, the number that are divisible by \(\displaystyle 10\text{.}\) This is \(\displaystyle 60/10=6\text{.}\) Also, \(\displaystyle |B\cap C|\) is the number of integers between \(\displaystyle 1\) and \(\displaystyle 60\) that are divisible by \(\displaystyle 3\) and \(\displaystyle 5\text{;}\) that is, the number that are divisible by \(\displaystyle 15\text{.}\) This is \(\displaystyle 60/15=4\text{.}\) Finally, \(\displaystyle |A\cap B\cap C|\) is the number of integers between \(\displaystyle 1\) and \(\displaystyle 60\) that are divisible by \(\displaystyle 2\text{,}\) \(\displaystyle 3\text{,}\) and \(\displaystyle 5\text{;}\) that is, the number that are divisible by \(\displaystyle 30\text{.}\) This is \(\displaystyle 60/30=2\text{.}\) We have been asked for \(\displaystyle |A\cup B \cup C|\text{.}\) Using inclusion-exclusion, we see that the answer is \(\displaystyle 30+20+12-10-6-4+2=44\text{.}\)