Homework 7 - Counting and Functions PDF

Homework 7. Counting and Functions Due Wednesday, 11/20, by 11:59 pm (Submit clear pictures of your homework as a single pdf file titled yourname.pdf through Gradescope on Canvas) (1) How many pairs of subsets A, B ⊆ {1, 2,... , n} are there with A ⊆ B?...

Homework 7. Counting and Functions Due Wednesday, 11/20, by 11:59 pm (Submit clear pictures of your homework as a single pdf file titled yourname.pdf through Gradescope on Canvas) (1) How many pairs of subsets A, B ⊆ {1, 2,... , n} are there with A ⊆ B? Explain your answer. List all such pairs for n = 2. Solution: 3n. For each element there are three independent choices: to in- clude it in B, but not in A; to include it in both A and B; to include it in nei- ther A nor B. For n = 2 the pairs are {∅, ∅}, {∅, {1}}, {∅, {2}}, {∅, {1, 2}}, {{1}, {1}}, {{1}, {1, 2}}, {{2}, {2}}, {{2}, {1, 2}}, {{1, 2}, {1, 2}}. (2) How many ways are there to split a class of 2n people into n pairs (order is irrelevant)? Explain your answer. List all such splittings for n = 2. Solution: There are 2n − 1 ways to find a partner to person 1, then 2n − 3 ways to find a partner to a remaining person with least number, then 2n−5 ways to find a partner to a remaining person with least number, and so on. So it is 1·3·· · ··(2n−3)·(2n−1). For n = 2 the splittings are {{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}. (3) You’re dealt a 6-card hand from a standard deck of 52 playing cards, where the sequence of the cards doesn’t matter. How many possible hands possess the following characteristics? Here you must provide five answers with explanations. (a) Every card in the hand is red. (b) The hand includes one jack, two queens, and three aces. (c) At most two of the cards in the hand are kings. (d) Each card in the hand represents a unique denomination. (e) Only two distinct denominations are represented among the cards in the hand. Solution:   26 (a) , since you are drawing 6 out of 26 red cards. 6       4 4 4 4 (b) , since there are ways to pick k cards out 1 2 3 k of four of the corresponding denomination for k = 1, 2, 3.          4 48 4 48 4 48 (c) + + , where the sum- 0 6 1 5 2 4 mands correspond to cases of picking 0, 1, and 2 kings respectively.   13 (d) · 46. In the deck, there are 13 denominations. We need to 6 choose 6 of them, and for each denomination, there are 4 suits. 1 2        2 4 4 13 4 (e) 13·12· · + ·. Here the first summand cor- 2 4 2 3 responds to cases with 2 cards of one denomination and 4 cards of the other denomination. The second summand corresponds to cases with 3 cards of one denomination and 3 cards of the other denomination. The second case  is symmetric,  so for choosing two denominations here 13 13·12 we must use = 2 instead of 13 · 12, as in the first case. 2 (4) Function f : R → R is given by f (x) = a1 · sin x + a2 · sin 2x + · · · + a100 · sin 100x for some fixed a1 , a2 ,... , a100 ∈ R. Prove that function f is not one-to-one. Prove that function f is not onto. Solution: f is not one-to-one, since 0 = f (0) = f (π). f is not onto, since | sin y| ≤ 1 for all y ∈ R, so |f (x)| ≤ |a1 | · | sin x| + |a2 | · | sin 2x| + · · · + |a100 | · | sin 100x| ≤ |a1 | + |a2 | + · · · + |a100 |, so f for instance doesn’t take value |a1 | + |a2 | + · · · + |a100 | + 1. (5) m, n ∈ N. Consider a function f : N → {0, 1, 2,... , m − 1} × {0, 1, 2,... , n − 1}; f (a) = (remainder of a divided by m, remainder of a divided by n). Prove that f is not one-to-one for any m, n ∈ N. Prove that f is not onto for m = 4, n = 6. Prove that f is not onto for any m, n ∈ N with gcd(m, n) > 1. Solution: f is not one-to-one, since f (1) = (1, 1) = f (mn + 1). To prove that f is not onto it is enough to show that f doesn’t take value (0, 1). Indeed, suppose f (a) = (0, 1) for some a ∈ N. Consider first the case m = 4, n = 6. Then a is divisible by 4, so it must be even. On the other hand, a = 6k + 1, so a must be odd. Contradiction. Consider now the general case for m, n ∈ N with gcd(m, n) > 1. Let d = gcd(m, n) > 1. Then a is divisible by m, so by d. On the other hand a = kn + 1 for some integer k and kn is divisible by d, so 1 = a − kn is divisible by d. Contradiction.