《Mathematics for Computer》Problem Set 7 Solutions

6.042/18.] Mathematics for Computer Science March 29, 2005 Srini devadas and Eric Lehman Problem set 7 Solutions Due: Monday, April 4 at 9 PM Problem 1. Every function has some subset of these properties injective surjective lective Determine the properties of the functions below, and briefly explain your reasoning (a) The function f: R-R defined by f(r)=er Solution. This function is injective, since ef takes on each nonnegative real value for exactly one r. However, the function is not surjective, because e never takes on negative values. Therefore the function is not bijective either (b)The function f: R-R+t defined by f(a)=er Solution. The function et takes on every nonnegative value for exactly one so it is injective, surjective, and bijective (c) The function f: R- R defined by f(ar)=(+1)a(a-1 Solution. This function is surjective, since it is continuous, it tends to +oo for large itive z, and tends to -oo for large negative r. Thus, the function takes on each real value for at least one However, this function is not injective, since it takes on the value 0 at a =-l, =0, and a= 1. Therefore, the function is not bijective either (d) Let S be the set of all 20-bit sequences. Let T be the set of all 10-bit sequences. Let f: S-T map each 20-bit sequence to its first 10 bits. For exampl ∫(11101010101010010)=11101010 Solution. This function is surjective since the sequence b1b2... b10 is mapped to by b1b2 .b1000.0, for example. However, the function is not injective, because this sequence is also mapped to by b1b2.boll.1. Consequently, the function is not bijective either. Problem 2. There are 20 books arranged in a row on a shelf

6.042/18.062J Mathematics for Computer Science March 29, 2005 Srini Devadas and Eric Lehman Problem Set 7 Solutions Due: Monday, April 4 at 9 PM Problem 1. Every function has some subset of these properties: injective surjective bijective Determine the properties of the functions below, and briefly explain your reasoning. x (a) The function f : R R → defined by f(x) = e . Solution. This function is injective, since ex takes on each nonnegative real value for exactly one x. However, the function is not surjective, because ex never takes on negative values. Therefore, the function is not bijective either. x (b) The function f : R R+ → defined by f(x) = e . Solution. The function ex takes on every nonnegative value for exactly one x, so it is injective, surjective, and bijective. (c) The function f : R → R defined by f(x) = (x + 1)x(x − 1). Solution. This function is surjective, since it is continuous, it tends to +∞ for large positive x, and tends to −∞ for large negative x. Thus, the function takes on each real value for at least one x. However, this function is not injective, since it takes on the value 0 at x = −1, x = 0, and x = 1. Therefore, the function is not bijective either. (d) Let S be the set of all 20­bit sequences. Let T be the set of all 10­bit sequences. Let f : S T → map each 20­bit sequence to its first 10 bits. For example: f(11110110101101010010) = 1111011010 Solution. This function is surjective since the sequence b1b2 . . . b10 is mapped to by b1b2 . . . b1000 . . . 0, for example. However, the function is not injective, because this sequence is also mapped to by b1b2 . . . b1011 . . . 1. Consequently, the function is not bijective either. Problem 2. There are 20 books arranged in a row on a shelf

Problem set 7 (a) Describe a bijection between ways of choosing 6 of these books so that no two elected and 15-bit Solution. There is a bijection from 15-bit sequences with exactly six 1's to valid book selections: given such a sequence, map each zero to a non-chosen book, each of the chosen book. For example, here is a configuration of books and the correspondin.? first five 1s to a chosen book followed by a non-chosen book, and the last 1 to ng Inary sequence Selected books are darkened. Notice that the first fives ones are mapped to a chosen book and an non-chosen book in order to ensure that the binary sequence maps to a alid selection of books (b) How many ways are there to select 6 books so that no two adjacent books are selected? Solution. By the Bijection Rule, this is equal to the number of 15-bit sequences with exactly 6 ones, which is equal to 15 6!9! by the bookkeeper Rule Problem 3. Answer the following questions and provide brief justifications. Not every problem can be solved with a cute formula; you may have to fall back on case analysis, explicit enumeration or ad hoc methods. You may leave factorials and binomial coefficients in your answers (a) In how many different ways can the letters in the name of the popular 1980s band BANAN A be arranged? Solution. There are 5 As, 2 Ns, 1 B, 1 R, and 1 m. therefore the number of arrangements Is 5!2!1!1!! by the bookkeeper rule (b) How many different paths are there from point(0, 0, 0)to point( 12, 24, 36)if ev- ery step increments one coordinate and leaves the other two unchanged? Solution. There is a bijection between the set of all such paths and the set of strings containing 12X,s, 24Y's, and 36Z's. In particular, we obtain a path by working

2 Problem Set 7 (a) Describe a bijection between ways of choosing 6 of these books so that no two adjacent books are selected and 15­bit sequences with exactly 6 ones. Solution. There is a bijection from 15­bit sequences with exactly six 1’s to valid book selections: given such a sequence, map each zero to a non­chosen book, each of the first five 1’s to a chosen book followed by a non­chosen book, and the last 1 to a chosen book. For example, here is a configuration of books and the corresponding binary sequence: 1 ���� 0 ���� 0 ���� 0 1 � �� � � �� � � �� � � �� � ���� � �� � 0 ���� 0 1 ���� 0 ���� 0 ���� 0 1 1 ���� 0 ���� 1 Selected books are darkened. Notice that the first fives ones are mapped to a chosen book and an non­chosen book in order to ensure that the binary sequence maps to a valid selection of books. (b) How many ways are there to select 6 books so that no two adjacent books are selected? Solution. By the Bijection Rule, this is equal to the number of 15­bit sequences with exactly 6 ones, which is equal to � � 15! 15 = 6! 9! 6 by the Bookkeeper Rule. Problem 3. Answer the following questions and provide brief justifications. Not every problem can be solved with a cute formula; you may have to fall back on case analysis, explicit enumeration, or ad hoc methods. You may leave factorials and binomial coefficients in your answers. (a) In how many different ways can the letters in the name of the popular 1980’s band BANANARAMA be arranged? Solution. There are 5 A’s, 2 N’s, 1 B, 1 R, and 1 M. Therefore, the number of arrangements is 10! 5! 2! 1! 1! 1! by the Bookkeeper Rule. (b) How many different paths are there from point (0, 0, 0) to point (12, 24, 36) if ev￾ery step increments one coordinate and leaves the other two unchanged? Solution. There is a bijection between the set of all such paths and the set of strings containing 12 X’s, 24 Y’s, and 36 Z’s. In particular, we obtain a path by working

Problem Set 7 through a string from left to right. An X corresponds to a step that increments the first coordinate, a y increments the second coordinate and a Z increments the third The number of such strings is Therefore, this is also the number of paths 361 12!24!3 (c) In how many different ways can 2n students be paired up? Solution. Pair up students by the following procedure. Line up the students and pair the first and second, the third and fourth, the fifth and sixth, etc. The students can be lined up in(2n)! ways. However, this overcounts by a factor of 2n, because we would get the same pairing if the first and second students were swapped, the third and fourth were swapped, etc. Furthermore, we are still overcounting by a factor of n!, because we would get the same pairing even if pairs of students were permuted g. the first and second were swapped with the ninth and tenth. Therefore, number of pairings is: (d) How many different solutions over the natural numbers are there to the follow- ing equation? +x8=100 A solution is a specification of the value of each variable r. Two solutions are dif- ferent if different values are specified for some variable x Solution. There is a bijection between sequences containing 100 zeros and 7 ones Specifically, the 7 ones divide the zeros into 8 segments. Let a, be the number of zeros in the i-th segment. Therefore, the number of solutions is (e) In how many different ways can one choose n out of 2n objects, given that n of the 2n objects are identical and the other n are all unique? Solution. We can select n objects as follows. First, take a subset of the unique objects. Then take however many identical elements are needed to bring the total m. The first step can be done in 2n ways, and the second can be done in only 1 w Therefore there are 2n ways to choose n objects (f) How many undirected graphs are there with vertices U1, U2,..., Un if self-loops ar permitted? Solution. There are (2)+n potential edges, each of which may or may not appear in a given graph. Therefore, the number of graphs 2(2)+n

� � � � Problem Set 7 3 through a string from left to right. An X corresponds to a step that increments the first coordinate, a Y increments the second coordinate, and a Z increments the third. The number of such strings is: 72! 12! 24! 36! Therefore, this is also the number of paths. (c) In how many different ways can 2n students be paired up? Solution. Pair up students by the following procedure. Line up the students and pair the first and second, the third and fourth, the fifth and sixth, etc. The students can be lined up in (2n)! ways. However, this overcounts by a factor of 2n, because we would get the same pairing if the first and second students were swapped, the third and fourth were swapped, etc. Furthermore, we are still overcounting by a factor of n!, because we would get the same pairing even if pairs of students were permuted, e.g. the first and second were swapped with the ninth and tenth. Therefore, the number of pairings is: (2n)! 2n · n! (d) How many different solutions over the natural numbers are there to the follow￾ing equation? x1 + x2 + x3 + . . . + x8 = 100 A solution is a specification of the value of each variable xi. Two solutions are dif￾ferent if different values are specified for some variable xi. Solution. There is a bijection between sequences containing 100 zeros and 7 ones. Specifically, the 7 ones divide the zeros into 8 segments. Let xi be the number of zeros in the i­th segment. Therefore, the number of solutions is: 100 + 7 7 (e) In how many different ways can one choose n out of 2n objects, given that n of the 2n objects are identical and the other n are all unique? Solution. We can select n objects as follows. First, take a subset of the unique objects. Then take however many identical elements are needed to bring the total to n. The first step can be done in 2n ways, and the second can be done in only 1 way. Therefore, there are 2n ways to choose n objects. (f) How many undirected graphs are there with vertices v1, v2, . . . , vn if self­loops are permitted? n Solution. There are + n potential edges, each of which may or may not appear 2 in a given graph. Therefore, the number of graphs is: 2( n 2)+n

Problem set 7 (g In how many different ways can 10 indistinguishable balls be placed in four dis tinguishable boxes, such that every box gets 1, 2, 3, or 4 balls? Solution. First, we might as well put 1 ball in every box. Now the problem is to put the remaining 6 balls into 4 boxes so that no box gets more than 3 balls. Now we turn to case analysis. For example, we could put 3 balls in two boxes and o balls in the other two boxes. There are 2l2=6 ways to do this. All cases are listed below distribution of balls of ways 3,3,0,0 6 3.2.1.0 1!=24 2,2,2,0 2,2,1,1 22=6 Thus, there are 6+24+4+4+6= 44 ways in all (h) There are 15 sidewalk squares in a row. Suppose that a ball can be thrown so that it bounces on o, 1, 2, or 3 distinct sidewalk squares. Assume that the ball alw from left to right. How many different throws are possible? As an example, a two-bounce throw is illustrated below Solution 15 15 15 0 Gi) In how many different ways can the numbers shown on a red die, a green die, and a blue die total up to 15? Assume that these are ordinary 6-sided dice Solution. We fall back on explicit enumeration. Let R, G, and b be the values shown on the three dice R=1,B+G=14→0ways R=2,B+G=13→0wav R=3,B+G=12→1way R=4,B+G=11 R=5,B+G=10→3ways R=6,B+G=9 4 way Gj) The working days in the next year can be numbered 1, 2, 3, ., 300. I'd like to avoid as many as possible

- - - @ � @ � 4 Problem Set 7 (g) In how many different ways can 10 indistinguishable balls be placed in four dis￾tinguishable boxes, such that every box gets 1, 2, 3, or 4 balls? Solution. First, we might as well put 1 ball in every box. Now the problem is to put the remaining 6 balls into 4 boxes so that no box gets more than 3 balls. Now we turn to case analysis. For example, we could put 3 balls in two boxes and 0 balls in the other two boxes. There are 4! = 6 ways to do this. All cases are listed below: 2! 2! distribution of balls # of ways 4! 3, 3, 0, 0 2! 2! = 6 4! 3, 2, 1, 0 = 24 1! 1! 1! 1! 4! 3, 1, 1, 1 3! 1! = 4 4! 2, 2, 2, 0 3! 1! = 4 4! 2, 2, 1, 1 2! 2! = 6 Thus, there are 6 + 24 + 4 + 4 + 6 = 44 ways in all. (h) There are 15 sidewalk squares in a row. Suppose that a ball can be thrown so that it bounces on 0, 1, 2, or 3 distinct sidewalk squares. Assume that the ball always moves from left to right. How many different throws are possible? As an example, a two­bounce throw is illustrated below.  




@R�




R�@





















Solution. � � � � � � � � 15 15 15 15 + + + 0 1 2 3 (i) In how many different ways can the numbers shown on a red die, a green die, and a blue die total up to 15? Assume that these are ordinary 6­sided dice. Solution. We fall back on explicit enumeration. Let R, G, and B be the values shown on the three dice. R = 1, B + G = 14 → 0 ways R = 2, B + G = 13 → 0 ways R = 3, B + G = 12 → 1 way R = 4, B + G = 11 → 2 ways R = 5, B + G = 10 → 3 ways R = 6, B + G = 9 → 4 ways (j) The working days in the next year can be numbered 1, 2, 3, . . . , 300. I’d like to avoid as many as possible

Problem Set 7 On even-numbered days, I'll say I'm sick On days that are a multiple of 3 I'll say i was stuck in traffic On days that are a multiple of 5, ill refuse to come out from under the blankets In total, how many work days will I avoid in the coming year? Solution. Let D2 be the set of even-numbered days, D3 be the days that are a mul tiple of 3, and D; be days that are a multiple of 5. The set of days I can avoid is D2 U D3 U Ds. By the Inclusion-Exclusion Rule, the size of this set D2 U D3U D D2 D3+IDs I D2∩D3-|D2nDs-|D3nDs +|D2∩D3∩D5 300300300300300300 52.32.53·52.3·5 Problem 4. Use the pigeonhole principle to solve the following problems (a) Prove that among any n=+ l points within an n x n square there must exist two points whose distance is at most Solution. Partition the n x n into m- unit squares. Each of the n2+ 1 points lies in one of these n2 unit squares. (If a point lies on the boundary between squares, assign it to a square arbitrarily. Therefore, by the pigeonhole principle, there exist two points in the same unit square And the distance between those two points can be at most v2 (b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of each flavor. Prove that some jar contains at least three jellybeans of one flavor and also at least three jellybeans of some other flavor Solution. We use the pigeonhole principle twice. Since there are 11 beans of a given flavor and there are only 5 jars, some jar must get at least 111/5=3 beans of that flavor. Since there are 6 flavors and only 5 jars, some jar must get two pairs of same- flavored beans (c) Prove that among every set of 30 integers, there exist two whose difference or sum is a multiple of 51 Solution. Regard the 30 integers as pigeons. Regard the 26 sets 01, ( 1, 501, ( 2, 49) [25, 26) as pigeonholes. Map integer n to the set containing n rem 51. By the pigeonhole principle, some two pigeons(integers a and b)are mapped to the same pigeonhole. Thus, either a rem 51= b rem 51 and so the difference of a and b is a multiple of 51

Problem Set 7 5 • On even­numbered days, I’ll say I’m sick. • On days that are a multiple of 3, I’ll say I was stuck in traffic. • On days that are a multiple of 5, I’ll refuse to come out from under the blankets. In total, how many work days will I avoid in the coming year? Solution. Let D2 be the set of even­numbered days, D3 be the days that are a mul￾tiple of 3, and D5 be days that are a multiple of 5. The set of days I can avoid is D2 ∪ D3 ∪ D5. By the Inclusion­Exclusion Rule, the size of this set is: |D2 ∪ D3 ∪ D5| | | | | | = D2| + D3 + D5 − | | − | | − | | D2 ∩ D3 D2 ∩ D5 D3 ∩ D5 + |D2 ∩ D3 ∩ D5| 300 300 300 300 300 300 300 = 2 + 3 + 5 − 2 3 − 2 5 − 3 5 + · · · 2 3 5 · · = 220 Problem 4. Use the pigeonhole principle to solve the following problems. (a) Prove that among any n2 + 1 points within an n × n square there must exist two points whose distance is at most √2. Solution. Partition the n × n into n2 unit squares. Each of the n2 + 1 points lies in one of these n2 unit squares. (If a point lies on the boundary between squares, assign it to a square arbitrarily.) Therefore, by the pigeonhole principle, there exist two points in the same unit square. And the distance between those two points can be at most √2. (b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of each flavor. Prove that some jar contains at least three jellybeans of one flavor and also at least three jellybeans of some other flavor. Solution. We use the pigeonhole principle twice. Since there are 11 beans of a given flavor and there are only 5 jars, some jar must get at least �11/5�= 3 beans of that flavor. Since there are 6 flavors and only 5 jars, some jar must get two pairs of same­ flavored beans. (c) Prove that among every set of 30 integers, there exist two whose difference or sum is a multiple of 51. Solution. Regard the 30 integers as pigeons. Regard the 26 sets {0}, {1, 50}, {2, 49}, . . ., {25, 26} as pigeonholes. Map integer n to the set containing n rem 51. By the pigeonhole principle, some two pigeons (integers a and b) are mapped to the same pigeonhole. Thus, either: • a rem 51 = b rem 51 and so the difference of a and b is a multiple of 51