Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section7.7Exercises

1

A school has \(147\) third graders. The third grade teachers have planned a special treat for the last day of school and brought ice cream for their students. There are three flavors: mint chip, chocolate, and strawberry. Suppose that \(60\) students like (at least) mint chip, \(103\) like chocolate, \(50\) like strawberry, \(30\) like mint chip and strawberry, \(40\) like mint chip and chocolate, \(25\) like chocolate and strawberry, and \(18\) like all three flavors. How many students don't like any of the flavors available?

2

There are \(1189\) students majoring in computer science at a particular university. They are surveyed about their knowledge of three programming languages: C++, Java, and Python. The survey results reflect that \(856\) students know C++, \(792\) know Java, and \(692\) know Python. Additionally, \(639\) students know both C++ and Java, \(519\) know both C++ and Python, and \(632\) know both Java and Python. There are \(488\) students who report knowing all three languages. How many students reported that they did not know any of the three programming languages?

3

How many positive integers less than or equal to \(100\) are divisible by \(2\text{?}\) How many positive integers less than or equal to \(100\) are divisible by \(5\text{?}\) Use this information to determine how many positive integers less than or equal to \(100\) are divisible by neither \(2\) nor \(5\text{.}\)

4

How many positive integers less than or equal to \(100\) are divisible by none of \(2\text{,}\) \(3\text{,}\) and \(5\text{?}\)

5

How many positive integers less than or equal to \(1000\) are divisible by none of \(3\text{,}\) \(8\text{,}\) and \(25\text{?}\)

6

The State of Georgia is distributing $\(173\) million in funding to Fulton, Gwinnett, DeKalb, Cobb, and Clayton counties (in millions of dollars). In how many ways can this distribution be made, assuming that each county receives at least $\(1\) million, Clayton county receives at most $\(10\) million, and Cobb county receives at most $\(30\) million? What if we add the restriction that Fulton county is to receive at least $\(5\) million (instead of at least $\(1\) million)?

7

How many integer solutions are there to the equation \(x_1 + x_2 + x_3 + x_4 = 32\) with \(0\leq x_i\leq 10\) for \(i=1,2,3,4\text{?}\)

8

How many integer solutions are there to the inequality

\begin{equation*} y_1 + y_2 + y_3 + y_4 \lt 184 \end{equation*}

with \(y_1>0\text{,}\) \(0\lt y_2\leq 10\text{,}\) \(0\leq y_3\leq 17\text{,}\) and \(0\leq y_4 \lt 19\text{?}\)

9

A graduate student eats lunch in the campus food court every Tuesday over the course of a \(15\)-week semester. He is joined each week by some subset of a group of six friends from across campus. Over the course of a semester, he ate lunch with each friend \(11\) times, each pair \(9\) times, and each triple \(6\) times. He ate lunch with each group of four friends \(4\) times and each group of five friends \(4\) times. All seven of them ate lunch together only once that semester. Did the graduate student ever eat lunch alone? If so, how many times?

10

A group of \(268\) students are surveyed about their ability to speak Mandarin, Korean, and Japanese. There are \(37\) students who do not speak any of the three languages surveyed. Mandarin is spoken by \(174\) of the students, Japanese is spoken by \(139\) of the students, and Korean is spoken by \(112\) of the students. The survey results also reflect that \(102\) students speak both Mandarin and Japanese, \(81\) students speak both Mandarin and Korean, and \(71\) students speak both Japanese and Korean. How many students speak all three languages?

11

As in Example 7.4, let \(X\) be the set of functions from \([n]\) to \([m]\) and let a function \(f\in X\) satisfy property \(P_i\) if there is no \(j\) such that \(f(j)=i\text{.}\)

  1. Let the function \(f\colon [8]\to [7]\) be defined by Table 7.18. Does \(f\) satisfy property \(P_2\text{?}\) Why or why not? What about property \(P_3\text{?}\) List all the properties \(P_i\) (with \(i\leq 7\)) satisfied by \(f\text{.}\)

  2. Is it possible to define a function \(g\colon [8]\to [7]\) that satisfies no property \(P_i\text{,}\) \(i\leq 7\text{?}\) If so, give an example. If not, explain why not.

  3. Is it possible to define a function \(h\colon [8]\to [9]\) that satisfies no property \(P_i\text{,}\) \(i\leq 9\text{?}\) If so, give an example. If not, explain why not.

\(i\) 1 2 3 4 5 6 7 8
\(f(i)\) 4 2 6 1 6 2 4 2
Table7.18A function defined by a table
12

As in Example 7.5, let \(X\) be the set of permutations of \([n]\) and say that \(\sigma\in X\) satisfies property \(P_i\) if \(\sigma(i) = i\text{.}\)

  1. Let the permutation \(\sigma\colon [8]\to [8]\) be defined by Table 7.19. Does \(\sigma\) satisfy property \(P_2\text{?}\) Why or why not? What about property \(P_6\text{?}\) List all the properties \(P_i\) (with \(i\leq 8\)) satisfied by \(\sigma\text{.}\)

  2. Give an example of a permutation \(\tau\colon[8]\to[8]\) that satisfies properties \(P_1\text{,}\) \(P_4\text{,}\) and \(P_8\) and no other properties \(P_i\) with \(1\leq i\leq 8\text{.}\)

  3. Give an example of a permutation \(\pi\colon [8]\to[8]\) that does not satisfy any property \(P_i\) with \(1\leq i\leq 8\text{.}\)

\(i\) 1 2 3 4 5 6 7 8
\(\sigma(i)\) 3 1 8 4 7 6 5 2
Table7.19A permutation defined by a table
13

As in Example 7.6, let \(m\) and \(n\) be positive integers and \(X=[n]\text{.}\) Say that \(j\in X\) satisfies property \(P_i\) for an \(i\) with \(1\leq i\leq m\) if \(i\) is a divisor of \(j\text{.}\)

  1. Let \(m=n=15\text{.}\) Does \(12\) satisfy property \(P_3\text{?}\) Why or why not? What about property \(P_5\text{?}\) List the properties \(P_i\) with \(1\leq i\leq 15\) that \(12\) satisfies.

  2. Give an example of an integer \(j\) with \(1\leq j\leq 15\) that satisfies exactly two properties \(P_i\) with \(1\leq i\leq 15\text{.}\)

  3. Give an example of an integer \(j\) with \(1\leq j\leq 15\) that satisfies exactly four properties \(P_i\) with \(1\leq i\leq 15\) or explain why such an integer does not exist.

  4. Give an example of an integer \(j\) with \(1\leq j\leq 15\) that satisfies exactly three properties \(P_i\) with \(1\leq i\leq 15\) or explain why such an integer does not exist.

14

How many surjections are there from an eight-element set to a six-element set?

15

A teacher has \(10\) books (all different) that she wants to distribute to John, Paul, Ringo, and George, ensuring that each of them gets at least one book. In how many ways can she do this?

16

A supervisor has nine tasks that must be completed and five employees to whom she may assign them. If she wishes to ensure that each employee is assigned at least one task to perform, how many ways are there to assign the tasks to the employees?

17

A professor is working with six undergraduate research students. He has \(12\) topics that he would like these students to begin investigating. Since he has been working with Katie for several terms, he wants to ensure that she is given the most challenging topic (and possibly others). Subject to this, in how many ways can he assign the topics to his students if each student must be assigned at least one topic?

18

List all the derangements of \([4]\text{.}\) (For brevity, you may write a permutation \(\sigma\) as a string \(\sigma(1)\sigma(2)\sigma(3)\sigma(4)\text{.}\))

19

How many derangements of a nine-element set are there?

20

A soccer team's equipment manager is in a hurry to distribute uniforms to the last six players to show up before a match. Instead of ensuring that each player receives his own uniform, he simply hands a uniform to each of the six players. In how many ways could he hand out the uniforms so that no player receives his own uniform? (Assume that the six remaining uniforms belong to the last six players to arrive.)

21

A careless payroll clerk is placing employees' paychecks into envelopes that have been pre-labeled. The envelopes are sealed before the clerk realizes he didn't match the names on the paychecks with the names on the envelopes. If there are seven employees, in how many ways could he have placed the paychecks into the envelopes so that exactly three employees receive the correct paycheck?

22

The principle of inclusion-exclusion is not the only approach available for counting derangements. We know that \(d_1=0\) and \(d_2=1\text{.}\) Using this initial information, it is possible to give a recursive form for \(d_n\text{.}\) In this exercise, we consider two recursions for \(d_n\text{.}\)

  1. Give a combinatorial argument to prove that the number of derangements satisfies the recursive formula \(d_n = (n-1)(d_{n-1}+d_{n-2})\) for \(n\geq 2\text{.}\)

  2. Prove that the number of derangements also satisfies the recursive formula \(d_n = nd_{n-1} + (-1)^n\) for \(n\geq 2\text{.}\)

Hint
23

Determine \(\phi(18)\) by listing the integers it counts as well as by using the formula of Theorem 7.14.

24

Compute \(\phi(756)\text{.}\)

25

Given that \(1625190883965792 = (2)^5(3)^4(11)^2(13)(23)^3(181)^2\text{,}\) compute

\begin{equation*} \phi(1625190883965792). \end{equation*}
27

At a very small school, there is a class with nine students in it. The students, whom we will denote as \(A\text{,}\) \(B\text{,}\) \(C\text{,}\) \(D\text{,}\) \(E\text{,}\) \(F\text{,}\) \(G\text{,}\) \(H\text{,}\) and \(I\text{,}\) walk from their classroom to the lunchroom in the order \(ABCDEFGHI\text{.}\) (Let's say that \(A\) is at the front of the line.) On the way back to their classroom after lunch, they would like to walk in an order so that no student walks immediately behind the same classmate he or she was behind on the way to lunch. (For instance, \(ACBDIHGFE\) and \(IHGFEDCBA\) would meet their criteria. However, they would not be happy with \(CEFGBADHI\) since it contains \(FG\) and \(HI\text{,}\) so \(G\) is following \(F\) again and \(I\) is following \(H\) again.)

  1. One student ponders how many possible ways there would be for them to line up meeting this criterion. Help him out by determining the exact value of this number.

  2. Is this number bigger than, smaller than, or equal to the number of ways they could return so that no student walks in the same position as before (i.e., \(A\) is not first, \(B\) is not second, …, and \(I\) is not last)?

  3. What fraction (give it as a decimal) of the total number of ways they could line up meet their criterion of no student following immediately behind the same student on the return trip?