Problem 1(a)(b)Problem 2(a)(b)(c)(d)(e)(f)(g)(h)Problem 3(a)(b)(c)Problem 4(a)(b)(c)(d)Problem 5(a)(b)(c)(d)(e)(f)(g)Massachusetts Institute of Technology6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 2Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised November 3, 2005, 1272 minutesProblem Set 7Due: November 9Reading: Counting, Notes I. & II.§1–3.Problem 1. There are 20 books arranged in a row on a shelf.(a) Describe a bijection between ways of choosing 6 of these books so that no two adja-cent books are selected and 15-bit sequences with exactly 6 ones.(b) How many ways are there to select 6 books so that no two adjacent books are se-lected?Problem 2. Answer the following questions and provide brief justifications. Not everyproblem 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 bandBANANARAMA be arranged?(b) How many different paths are there from point (0, 0, 0) to point (12, 24, 36) if everystep increments one coordinate and leaves the other two unchanged?(c) In how many different ways can 2n students be paired up?(d) How many different solutions over the natural numbers are there to the followingequation?x1+ x2+ x3+ . . . + x8= 100A solution is a specification of the value of each variable xi. Two solutions are different ifdifferent values are specified for some variable xi.Copyright © 2005, Prof. Albert R. Meyer. All rights reserved.Problem Set 7 2(e) In how many different ways can one choose n out of 2n objects, given that n of the2n objects are identical and the other n are all unique?(f) How many undirected graphs are there with vertices v1, v2, . . . , vnif self-loops arepermitted?(g) There are 15 sidewalk squares in a row. Suppose that a ball can be thrown so thatit bounces on 0, 1, 2, or 3 distinct sidewalk squares. Assume that the ball always movesfrom left to right. How many different throws are possible? As an example, a two-bouncethrow is illustrated below.-@@R-@@R-(h) The working days in the next year can be numbered 1, 2, 3, . . . , 300. I’d like to avoidas many as possible.• 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?Problem 3. 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 pointswhose distance is at most√2.(b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of eachflavor. Prove that some jar contains at least three jellybeans of one flavor and also at leastthree jellybeans of some other flavor.(c) Prove that among every set of 30 integers, there exist two whose difference or sum isa multiple of 51.Problem 4. Suppose you have seven dice— each a different color of the rainbow; other-wise the dice are standard, with six faces numbered 1 to 6. A roll is a sequence specifyinga value for each die in rainbow (ROYGBIV) order. For example, one roll is (3, 1, 6, 1, 4, 5, 2)indicating that the red die showed a 3, the orange die showed 1, the yellow 6, the green1, the blue 4, the indigo 5, and the violet 2.Problem Set 7 3For the problems below, describe a bijection between the specified set of rolls and anotherset that is easily counted using the Product, Generalized Product, and similar rules. Thenwrite a simple numerical expression for the size of the set of rolls. You do not need toprove that the correspondence between sets you describe is a bijection, and you do notneed to simplify the expression you come up with.For example, let A be the set of rolls where 4 dice come up showing the same number,and the other 3 dice also come up the same, but with a different number. Let R to be theset of seven rainbow colors and S be the set {1, . . . , 6} of dice values.Define B ::= S2× {3, 4} × R3, where S2is the set of size 2 subsets of S, and R3is the setof size 3 subsets of R. Then define a bijection from A to B by mapping a roll in A to thesequence in B whose first element is the set of two numbers that came up, whose secondelement is the number of times the smaller of the two numbers came up in the roll, andwhose third element is the set of colors of the three matching dice.For example, the roll(4, 4, 2, 2, 4, 2, 4) ∈ Amaps to the triple({2, 4}, 3, {yellow,green,indigo}) ∈ B.Now by the bijection Rule |A| = |B|, and by the Product rule,|B| =62· 2 ·73.(a) For how many rolls is the value on every die different?(b) For how many rolls do two dice have the value 6 and the remaining five dice all havedifferent values?Example: (6, 2, 6, 1, 3, 4, 5) is a roll of this type, but (1, 1, 2, 6, 3, 4, 5) and (6, 6, 1, 2, 4, 3, 4)are not.(c) For how many rolls do two dice have the same value and the remaining five dice allhave different values?Example: (4, 2, 4, 1, 3, 6, 5) is a roll of this type, but (1, 1, 2, 6, 1, 4, 5) and (6, 6, 1, 2, 4, 3, 4)are not.(d) For how many rolls do two dice have one value, two different dice have a secondvalue, and the remaining three dice a third value?Example: (6, 1, 2, 1, 2, 6, 6) is a roll of this type, but (4, 4, 4, 4, 1, 3, 5) and (5, 5, 5, 6, 6, 1, 2)are not.Problem Set 7 4Problem 5. A derangement is a permutation (x1, x2, . . . , xn) of the set {1, 2, . . . , n} such thatxi6= i for all i. For example, (2, 3, 4, 5, 1) is a derangement, but (2, 1, 3, 5, 4) is not because3 appears in the third position. The objective of this problem is to count derangements.It turns out to be easier to start by counting the permutations that are not derangements.Let Sibe the set of all permutations (x1, x2, . . . , xn) that are not derangements becausexi= i. So the set of non-derangements isn[i=1Si.(a) What is |Si|?(b) What is |Si∩ Sj| where i 6= j?(c) What is |Si1∩ Si2∩ ··· ∩ Sik| where i1, i2, . . . , ikare all distinct?(d) Use the inclusion-exclusion formula to express the number of non-derangements interms of sizes of possible intersections of the sets S1, . . . , Sn.(e) How many terms in the expression in part (d) have the
View Full Document
Unlocking...