《Mathematics for Computer》Notes for Recitation 13

6.042/18.] Mathematics for Computer Science March 30, 2005 Srini devadas and Eric Lehman Notes for Recitation 13 Basic Counting notions a bijection or bijective function is a function f: X Y such that every element of the codomain is related to exactly one element of the domain. here is an example of lection X 1 codomain Rule 1 (Bijection Rule). If there exists a bijection f: A-B, then A=B Rule 2(Sum Rule). If A1,..., An are disjoint sets, the k=1 Rule 3 (Product Rule). IfPi, P2,... Pn are sets, then ×P2×…Pn=|f1|·|P…|Pn two different elements of X that are mapped to the same element ofr. f: X-Y there exist Rule 4(Pigeonhole Principle). IfX>Y then for every functio If more than n pigeons are assigned to n holes, then there must exist two pigeons assigned to the same hole

� � � � 6.042/18.062J Mathematics for Computer Science March 30, 2005 Srini Devadas and Eric Lehman Notes for Recitation 13 Basic Counting Notions A bijection or bijective function is a function f : X Y → such that every element of the codomain is related to exactly one element of the domain. Here is an example of a bijection: X f Y a PP 1 PPPP domain �q b PP 2 codomain c P �PPqP PP 3 PPPPq d � 4 e - 5 Rule 1 (Bijection Rule). If there exists a bijection f : A → B, then |A| = | | B . Rule 2 (Sum Rule). If A1, . . . , An are disjoint sets, then: n |A1 ∪ · · · ∪ An| | = Ak| k=1 Rule 3 (Product Rule). If P1, P2, . . . Pn are sets, then: |P1 × P2 × · · · × Pn| = | | · · · | P1| · |P2 Pn| Rule 4 (Pigeonhole Principle). If |X > | | |Y , then for every function f : X Y there exist two different elements of X that are mapped to the same element of Y . → “If more than n pigeons are assigned to n holes, then there must exist two pigeons assigned to the same hole

Recitation 13 Sum and product rules Problem 1. A license plate consists of either: 3 letters followed by 3 digits(standard plate 5 letters(vanity plate) Let L be the set of all possible license plates (a)Express L in terms of A={A,B,C,…,公} {0,1,2 using unions (U) and set products(x) Solution L=(A3×D3)∪A5 rules. pute Ll, the number of different license plates, using the sum and product Solution L|=|(A3×D3)UA5 (A3×D>)+|A° Sum rule A.D+Al Product rule =263·103+265 Bijections Problem 2. For each part below, describe a bijection between the two sets mentioned. The existence of such a bijection proves that the two sets are the same size. a good approach is to describe an element of the first set using variables and then describe the corresponding element of the second set in terms of those variables. For example, we might describe a bijecton from ways of selecting a dozen doughnuts from five varieties to a 16-bit string with four 1s as follows:

� � � � � � � � � � � � Recitation 13 2 Sum and Product Rules Problem 1. A license plate consists of either: • 3 letters followed by 3 digits (standard plate) • 5 letters (vanity plate) Let L be the set of all possible license plates. (a) Express L in terms of A = {A, B, C, . . . , Z} D = {0, 1, 2, . . . , 9} using unions ( ) ∪ and set products (×). Solution. L = (A3 × D3 ) ∪ A5 (b) Compute |L|, the number of different license plates, using the sum and product rules. Solution. (A3 × D3 ) ∪ A5 A5 | | L = = (A Sum Rule 3 × D3 ) + 3 3 5 = |A| · |D| | + |A Product Rule = 263 103 + 265 · Bijections Problem 2. For each part below, describe a bijection between the two sets mentioned. The existence of such a bijection proves that the two sets are the same size. A good approach is to describe an element of the first set using variables and then describe the corresponding element of the second set in terms of those variables. For example, we might describe a bijecton from ways of selecting a dozen doughnuts from five varieties to a 16­bit string with four 1’s as follows:

Recitation 13 Map a dozen doughnuts consisting of c chocolate, l lemon-filled, s sugar, g glazed and p plain to the sequence 0-010:010:010010 Everyone in your group should write out complete answers-you'll all benefit from the practice! (a) Describe a bijection between the set of 30-bit sequences with 10 zeros and 20 ones and paths from(0, 0)to(10, 20) consisting of right-steps(which increment the first coordinate)and up-steps( which increment the second coordinate Solution. Map the 30-bit sequence blb2... b3o to a path where the i-th step is right if bi=0 and up if bi=1 (b) Find a bijection between the set of n-bit sequences and the set of all subsets of Solution. Map the n-bit sequence bb2... bn to a subset that contains ci if and only if (c) Mr. and Mrs. Grumperson have collected 13 identical pieces of coal as Christmas presents for their beloved children, Lucy and Spud. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the two children and the set of 14-bit sequences with exactly 1 one Solution. Map a distribution in which lucy get l pieces and Spud gets s pieces to a 14-bit sequence with I zeros, a one and then s zeros. (d)On Christmas Eve, Mr and Mrs. Grumperson remember that they have a third child, little Bottlecap, locked in the attic. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three children and the set of 15-bit sequences with exactly 2 ones Solution. Map a distribution in which Lucy gets l pieces, Spud gets s pieces, and Bottlecap gets b pieces to a 15-bit sequence with l zeros, a one, s zeros, a one, and b (e)On reflection, Mr. and mrs. Grumperson decide that each of their three children should receive at least two pieces of coal for Christmas. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three Grumperson children given this constraint and the set of 9-bit sequences with exactly 2 ones Solution. Map a distribution in which Lucy gets l>2 pieces, Spud gets s> 2 pieces, and Bottlecap gets b>2 pieces to a 9-bit sequence with exactly l-2 zeros, one. s-2 zeros, a one, and b-2 zeros

Recitation 13 3 Map a dozen doughnuts consisting of: c chocolate, l lemon­filled, s sugar, g glazed, and p plain to the sequence: � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 �� � �� � �� � �� � �� � c l s g p Everyone in your group should write out complete answers— you’ll all benefit from the practice! (a) Describe a bijection between the set of 30­bit sequences with 10 zeros and 20 ones and paths from (0, 0) to (10, 20) consisting of right­steps (which increment the first coordinate) and up­steps (which increment the second coordinate). Solution. Map the 30­bit sequence b1b2 . . . b30 to a path where the i­th step is right if bi = 0 and up if bi = 1. (b) Find a bijection between the set of n­bit sequences and the set of all subsets of {x1, x2, . . . , xn}. Solution. Map the n­bit sequence b1b2 . . . bn to a subset that contains xi if and only if bi = 1. (c) Mr. and Mrs. Grumperson have collected 13 identical pieces of coal as Christmas presents for their beloved children, Lucy and Spud. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the two children and the set of 14­bit sequences with exactly 1 one. Solution. Map a distribution in which Lucy get l pieces and Spud gets s pieces to a 14­bit sequence with l zeros, a one, and then s zeros. (d) On Christmas Eve, Mr. and Mrs. Grumperson remember that they have a third child, little Bottlecap, locked in the attic. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three children and the set of 15­bit sequences with exactly 2 ones. Solution. Map a distribution in which Lucy gets l pieces, Spud gets s pieces, and Bottlecap gets b pieces to a 15­bit sequence with l zeros, a one, s zeros, a one, and b zeros. (e) On reflection, Mr. and Mrs. Grumperson decide that each of their three children should receive at least two pieces of coal for Christmas. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three Grumperson children given this constraint and the set of 9­bit sequences with exactly 2 ones. Solution. Map a distribution in which Lucy gets l ≥ 2 pieces, Spud gets s ≥ 2 pieces, and Bottlecap gets b ≥ 2 pieces to a 9­bit sequence with exactly l − 2 zeros, a one, s − 2 zeros, a one, and b − 2 zeros

Recitation 13 (f)Describe a bijection between the set of 110-bit sequences with exactly 10 ones and solutions over the natural numbers to the equation <100 Solution. Let T1 be the number of zeros before the first 1, c2, be the number of zeros between the first and second 1, etc. note that zeros after the tenth 1 do not contribute to the value of any of the variables 1, .. T10; this allows us to count solutions to the inequality(< 100) rather than the equality( 100) (g Describe a bijection between solutions to the inequality in the preceding problem part and sequences(y1, 32, .. y10)such that 0≤y≤y≤…≤y10≤100 Solution. Let yi=01+..+r for each i from 1 to 10 Pigeonhole principle Problem 3. Solve the following problems using the pigeonhole principle. For each prob lem, try to identify the pigeons, the pigeonholes, and a rule assigning each pigeon to a pi geonhole (a) In a room of 500 people, there exist two who share a birthday. Solution. The pigeons are the 500 people. The pigeonholes are 366 possible birth days. Map each person to his or her own birthday. Since there 500 people and 366 birthdays, some two people must have the same birthday by the Pigeonhole Princi- e (b) Every MIT ID number starts with a 9(we think). Suppose that each of the 75 students in 6.042 sums the nine digits of his or her Id number. Must two peopl arrive at the same sum? Solution. Yes. The students are the pigeons, the possible sums are the pigeonholes, and we map each student to the sum of the digits in his or her MIT ID number Every sum is in the range from 9+80=9 to 9+89=81, which means that there are 73 pigeonholes. Since there are more pigeons than pigeonholes, there must be two pigeons in the same pigeonhole; in other words, there must be two students with the same sum

Recitation 13 4 (f) Describe a bijection between the set of 110­bit sequences with exactly 10 ones and solutions over the natural numbers to the equation: x1 + x2 + · · · + x10 ≤ 100 Solution. Let x1 be the number of zeros before the first 1, x2, be the number of zeros between the first and second 1, etc. Note that zeros after the tenth 1 do not contribute to the value of any of the variables x1, . . . , x10; this allows us to count solutions to the inequality (≤ 100) rather than the equality (= 100). (g) Describe a bijection between solutions to the inequality in the preceding problem part and sequences (y1, y2, . . . , y10) such that: 0 ≤ y1 ≤ y2 ≤ · · · ≤ y10 ≤ 100 Solution. Let yi = x1 + + · · · xi for each i from 1 to 10. Pigeonhole Principle Problem 3. Solve the following problems using the pigeonhole principle. For each prob￾lem, try to identify the pigeons, the pigeonholes, and a rule assigning each pigeon to a pi￾geonhole. (a) In a room of 500 people, there exist two who share a birthday. Solution. The pigeons are the 500 people. The pigeonholes are 366 possible birth￾days. Map each person to his or her own birthday. Since there 500 people and 366 birthdays, some two people must have the same birthday by the Pigeonhole Princi￾ple. (b) Every MIT ID number starts with a 9 (we think). Suppose that each of the 75 students in 6.042 sums the nine digits of his or her ID number. Must two people arrive at the same sum? Solution. Yes. The students are the pigeons, the possible sums are the pigeonholes, and we map each student to the sum of the digits in his or her MIT ID number. Every sum is in the range from 9 + 8 0 = 9 · to 9 + 8 9 = 81 · , which means that there are 73 pigeonholes. Since there are more pigeons than pigeonholes, there must be two pigeons in the same pigeonhole; in other words, there must be two students with the same sum

Recitation 13 (c) In every set of 100 integers, there exist two whose difference is a multiple of 37 Solution. The pigeons are the 100 integers. The pigeonholes are the numbers 0 to 36. Map integer k to k rem 37. Since there are 100 pigeons and only 37 pigeonholes, two pigeons must go in the same pigeonhole. This means ki rem 37=k2 rem 37, which implies that k1- k2 is a multiple of 37. (d) For any five points in a unit square, there are two points at distance less than v2 Solution. The pigeons are the points. The pigeonholes are the four subsquares of the unit square, each of side length There are five pigeons and four pigeonholes, so more than one point must be in the same subsquare. Points in the same subsquare are at distance at most (e) For any five points in an equilateral triangle of side length 2, there are two points at distance less than 1 Solution. The pigeons are the points. The pigeonholes are the four sub-equilateral triangles of side length 1. There are five pigeons and four pigeonholes, so more than one point must be in the same sub-equilateral triangle. Points in the same sub-equilateral triangle are at distance at most 1 (f)Let al,..., a201 be a set of natural numbers less than 300. Then there are i, j such that 3 for some k>0 Solution. The pigeons are the numbers. The pigeonholes are the 200 numbers less than 300 that are not divisible by 3. Write each number ai= 3. bi, where bi is not divisible by 3. Place a; in the pigeonhole b;. Then there are two numbers ai, a, placed in the same pigeonhole, i.e. bi=bi, so ai= 3-c(Assume ci >c without loss of generality

Recitation 13 5 (c) In every set of 100 integers, there exist two whose difference is a multiple of 37. Solution. The pigeons are the 100 integers. The pigeonholes are the numbers 0 to 36. Map integer k to k rem 37. Since there are 100 pigeons and only 37 pigeonholes, two pigeons must go in the same pigeonhole. This means k1 rem 37 = k2 rem 37, which implies that k1 − k2 is a multiple of 37. 1 (d) For any five points in a unit square, there are two points at distance less than √ . 2 Solution. The pigeons are the points. The pigeonholes are the four subsquares of the unit square, each of side length 1 2 . There are five pigeons and four pigeonholes, so more than one point must be in the same subsquare. Points in the same subsquare 1 are at distance at most √2 . (e) For any five points in an equilateral triangle of side length 2, there are two points at distance less than 1. Solution. The pigeons are the points. The pigeonholes are the four sub­equilateral triangles of side length 1. There are five pigeons and four pigeonholes, so more than one point must be in the same sub­equilateral triangle. Points in the same sub­equilateral triangle are at distance at most 1. (f) Let {a1, . . . , a201} be a set of natural numbers less than 300. Then there are i, j such that ai = 3k for some k > 0. aj Solution. The pigeons are the numbers. The pigeonholes are the 200 numbers less than 300 that are not divisible by 3. Write each number ai = 3ci bi, where bi · is not divisible by 3. Place ai in the pigeonhole bi. Then there are two numbers ai, aj placed ai in the same pigeonhole, i.e. bi = bj , so aj = 3ci−cj . (Assume ci > cj without loss of generality)