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 sumRecitation 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