CompSci 102 Discrete Mathematics for CSSpring 2005 Forbes In-class Questions 5These questions will also serve as part of the warmup for recitation 71. Suppose that next June, the Durham Bulls play at leats 1 game a day, but leq45 games total.Show that there must be some sequence of days in June during which they play exactly 14games.2. An inventory list contains a list of 80 items, each marked “available” or “unavailable.” Thereare 50 available items. Show that there are at least two unavailable items in the list eitherthree or six items apart.13. We want show that if X is any (n + 2) element subset of {1, 2, . . . , 2n + 1} and m is thegreatest element in X, there exist distinct i and j in X with m = i + j.For each element k ∈ X − {m}, letak=(k ifk ≤m2m − k ifk >m2(a) How many elements are in the domain of a?(b) Show that the range of a is contained in {1, 2, 3 . . . , n}.(c) Explain why the previous two results imply that ai= ajfor some i 6= j.(d) Explain why the previous result implies that there exist distinct i and j in X withm = i + j.CompSci 102, Spring 2005, In-class Questions 5 24. How many bit strings of length 10 contain(a) exactly four 1s?(b) at most four 1s?(c) at least four 1s?(d) an equal number of 0s and 1s?CompSci 102, Spring 2005, In-class Questions 5 35. How many possibilities are there for win, place, and show positions in a horse race with 12horses if all orders of finish are possible?6. How many ways are there for a horse race with three horses to finish if ties of two or threehorses are possible?7. If there are 6 runners in the 100 meter dash, how many ways are there for three medals to beawarded if ties are possible?CompSci 102, Spring 2005, In-class Questions 5
View Full Document