Math 55 Final Exam 11 May 2004NAME (1 pt):TA (1 pt):Name of Neigh bor to yo ur left (1 pt):Name of Neighbor to y our righ t (1 pt):Instructions: This is a closed book, closed notes, closed calculator, closed computer, closednetwork, open brain exam.You get one point each for filling in the 4 lines at the top of this page. All other questionsare worth 10 points.Write all your answers on this exam. If you need scratch paper, ask for it, write y our nameon each sheet, and attach it when you turn it in (we have a stapler).For full credit justify your answers.12345Total11Question 1. (10 points)Question 1a. (5 points) If 61 people are sitting in a row of 80 chairs, prove that there areat least 4 consecutive occupied chairs.Answer: Let the pigeons be the 61 people, and the holes be the 20 disjoint sets of 4consecutive chairs 1-4, 5-8, 9-12, ... , 77-80. By the Generalized Pigeonhole Principle somehole must get at least 61/20 =4pigeons.Question 1b. (5 points) Label each of the following sets as “finite”, “countably infinite”,or “uncoun table”. Justify your answers (you may cite theorems proven in class).1. Set of all correct computer programs in Java.2. Set of all computer programs in Java that have ever been written.3. Set of rational numb ers between 1 and 2.4. Set of functions with domain {0, 1, 2} and codomain N = {1, 2, 3, ...}.5. Set of functions with domain N and codomain {0, 1, 2}.Answer:1. Countably infinite, because it is an infinite subset of the countable set consisting of allfinite strings of characters on the keyboard.2. Finite, because each of finitely many Java programmers (or Java generating programs)can only have written a finite amount of code in the finite amount of time they haveexisted, working at a finite speed.3. Countably infinite. The set of all pairs of integers is countably infinite because it is theCartesian product of two countably infinite sets, by a result in class. Then, the rationalsbetween 1 and 2 are in a one-to-one correspondence with an infinite subset of all pairs(i, j) of integers, namely those where j =0, gcd(i, j)=1,andj ≤ i ≤ 2j.Finally,aninfinite subset of a countable set is countably infinite by a result shown in class.4. Countably infinite, because the set of functions is in one-to-one correspondence withN × N × N.5. Uncountable, because we showed in class that the set of all sequences of 0s and 1s isuncountable by a diagonalization argument, and the set of all sequences of 0s, 1s and 2sis only larger.2Question 1. (10 points)Question 1a. (5 points) If 81 cars are park ed in a row of 100 parking places, prove thatthere are at least 5 consecutive occupied parking places.Answer: Let the pigeons be the 81 cars, and the holes be the 20 disjoint sets of 5consecutive parking places 1-5, 6-10, 11-15, ... , 96-100. By the Generalized PigeonholePrinciple some hole must get at least 81/20 =5pigeons.Question 1b. (5 poin ts) Label each of the following sets as “uncountable”, “countablyinfinite”, or “finite”. Justify your answers (you may cite theorems proven in class).1. Set of rational numb ers between .5and1.2. Set of all correct computer programs in C.3. Set of functions with domain {−1, 0, +1} and codomain Z = {..., −3, −2, −1, 0, 1, 2, 3, ...}.4. Set of functions with domain Z and codomain {−1, 0, +1}.5. Set of all computer programs in C that have ever been written.Answer:1. Countably infinite. The set of pairs of integers is countably infinite, because it is theCartesian product of two countably infinite sets, by a result in class. Then, the rationalsbetween .5 and 1 are in a one-to-one correspondence with an infinite subset of all pairs(i, j) of integers, namely those where j =0, gcd(i, j)=1,andj/2 ≤ i ≤ j.Finally,aninfinite subset of a countable set is countably infinite by a result shown in class.2. Countably infinite, because it is an infinite subset of the countable set consisting of allfinite strings of characters on the keyboard.3. Countably infinite, because the set of functions is in one-to-one correspondence withZ × Z × Z, and the Cartesian product of 3 countably infinite sets is countably infinite.4. Uncountable, because we showed in class that the set of all sequences of 0s and 1s isuncountable by a diagonalization argument, and the set of all sequences of −1s, 0s and1s is only larger.5. Finite, because each of finitely many C programmers (or C generating programs) canonly have written a finite amount of code in the finite amount of time they have existed,working at a finite speed.3Question 2 (10 points)Question 2a (5 points) Prove algebraically that C(n, r) ·C(n −r, k)=C(n, k) ·C(n −k, r).Answer:C(n, r) · C(n − r, k)=n!r!(n − r)!·(n − r)!k!(n − r − k)!=n!r!·1k!(n − r − k)!=n!k!·1r!(n − r − k)!=n!k!(n − k)!·(n − k)!r!(n − r −k)!= C(n, k) · C(n − k, r)Question 2b. (5 points) Prove the same identity using a coun ting argument.Answer: We count the number of ways to choose a subset of r elements and a disjointsubset of k elements from a set of n elements. (1) First choose r elements (there are C(n, r)ways) and then choose k elements from the remaining n − r elements (there are C(n − r, k)ways). Since each pair of choices leads to a different pair of subsets, the product is the numberof ways, namely C(n, r) · C(n − r, k). (2) First choose k elements and then r elements fromthe remaining n − k. The same argument yields the expression C(n, k) · C(n − k, r).4Question 2 (10 points)Question 2a (5 points) Prove algebraically that C(m, s)·C(m−s, j)=C(m, j)·C(m−j, s).Answer:C(m, s) · C(m − s, j)=m!s!(m − s)!·(m − s)!j!(m − s − j)!=m!s!·1j!(m − s − j)!=m!j!·1s!(m − s − j)!=m!j!(m − j)!·(m − j)!s!(m − s − j)!= C(m, j) · C(m − j, s)Question 2b. (5 points) Prove the same identity using a coun ting argument.Answer: We count the number of ways to choose a subset of s elements and a disjointsubset of j elements from a set of m elements. (1) First choose s elements (there are C(m, s)ways) and then choose j elements from the remaining m − s elements (there are C(m − s, j)ways). Since each pair of choices leads to a different pair of subsets, the product is the numberof ways, namely C(m, s) · C(m − s, j). (2) First choose j elements and then s elements fromthe remaining m − j. The same argument yields the expression C(m, j) · C(m − j, s).5Question 3. (10