7.7: Exercises

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? How many positive integers less than or equal to 100 are divisible by 5? Use this information to determine how many positive integers less than or equal to 100 are divisible by neither 2 nor 5.

4. How many positive integers less than or equal to 100 are divisible by none of 2, 3, and 5?

5. How many positive integers less than or equal to 1000 are divisible by none of 3, 8, and 25?

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\)?

8. How many integer solutions are there to the inequality

\(y_1+y_2+y_3+y_4<184\)

with \(y_1>0\), \(0<y_2 \leq 10\), \(0 \leq y_3≤17\), and \(0 \leq y_4<19\)?

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\).

a. Let the function \(f:[8] \rightarrow [7]\) be defined by Figure 7.18. Does \(f\) satisfy property \(P_2\)? Why or why not? What about property \(P_3\)? List all the properties \(P_i\) (with \(i \leq 7\)) satisfied by \(f\).

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

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

Figure 7.18. A 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\).

a. Let the permutation \(\sigma:[8] \rightarrow [8]\) be defined by Figure 7.19. Does σ satisfy property \(P_2\)? Why or why not? What about property \(P_6\)? List all the properties \(P_i\) (with \(i \leq 8\)) satisfied by \(\sigma\).

b. Give an example of a permutation \(\mathcal{τ}:[8] \rightarrow [8]\) that satisfies properties \(P_1, P_4, and P_8\) and no other properties \(P_i\) with \(1 \leq i \leq 8\).

c. Give an example of a permutation \(\pi:[8] \rightarrow [8]\) that does not satisfy any property \(P_i\) with \(1 \leq i \leq 8\).

Figure 7.19. A permutation defined by a table

13. As in Example 7.6, let \(m\) and \(n\) be positive integers and \(X=[n]\). 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\).

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

b. 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\).

c. 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.

d. 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]\). (For brevity, you may write a permutation \(\sigma\) as a string \(\sigma(1) \sigma(2) \sigma(3) \sigma(4)\).)

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\). Using this initial information, it is possible to give a recursive form for \(d_n\). In this exercise, we consider two recursions for \(d_n\).

a. 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\).

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

Hint

a. For a derangement \(\sigma\), consider the integer \(k\) with \(\sigma(k)=1\). Argue based on the number of choices for \(k\) and then whether \(\sigma(1)=k\) or not.

b. You may find it easiest to prove this using the other recursive formula and mathematical induction.

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)\).

25. Given that \(1625190883965792=(2)^5(3)^4(11)^2(13)(23)^3(181)^2\), compute

\(\phi(1625190883965792)\).

26. Prove Proposition 7.15.

27. At a very small school, there is a class with nine students in it. The students, whom we will denote as A, B, C, D, E, F, G, H, and I, walk from their classroom to the lunchroom in the order ABCDEFGHI. (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, so G is following F again and I is following H again.)

a. 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.

b. 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)?

c. 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?