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 Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 2 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised November 3, 2005, 1272 minutes Problem Set 7 Due: November 9 Reading: 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 every problem 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 band BANANARAMA be arranged? (b) How many different paths are there from point (0, 0, 0) to point (12, 24, 36) if every step 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 following equation? x1 + x2 + x3 + . . . + x8 = 100 A solution is a specification of the value of each variable xi. Two solutions are different if different values are specified for some variable xi. Copyright © 2005, Prof. Albert R. Meyer.- - -@ � @ �2 Problem Set 7 (e) In how many different ways can one choose n out of 2n objects, given that n of the 2n objects are identical and the other n are all unique? (f) How many undirected graphs are there with vertices v1, v2, . . . , vn if self-loops are permitted? (g) There are 15 sidewalk squares in a row. Suppose that a ball can be thrown so that it bounces on 0, 1, 2, or 3 distinct sidewalk squares. Assume that the ball always moves from left to right. How many different throws are possible? As an example, a two-bounce throw is illustrated below. R� @ @ R� (h) The working days in the next year can be numbered 1, 2, 3, . . . , 300. I’d like to avoid as 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 points whose distance is at most √2. (b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of each flavor. Prove that some jar contains at least three jellybeans of one flavor and also at least three jellybeans of some other flavor. (c) Prove that among every set of 30 integers, there exist two whose difference or sum is a 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 specifying a 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 green 1, the blue 4, the indigo 5, and the violet 2.� � � � 3 Problem Set 7 For the problems below, describe a bijection between the specified set of rolls and another set that is easily counted using the Product, Generalized Product, and similar rules. Then write a simple numerical expression for the size of the set of rolls. You do not need to prove that the correspondence between sets you describe is a bijection, and you do not need 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 the set of seven rainbow colors and S be the set {1, . . . , 6} of dice values. Define B ::= S2 × {3, 4} × R3, where S2 is the set of size 2 subsets of S, and R3 is the set of size 3 subsets of R. Then define a bijection from A to B by mapping a roll in A to the sequence in B whose first element is the set of two numbers that came up, whose second element is the number of times the smaller of the two numbers came up in the roll, and whose third element is the set of colors of the three matching dice. For example, the roll (4, 4, 2, 2, 4, 2, 4) ∈ A maps to the triple ({2, 4}, 3, {yellow,green,indigo}) ∈ B. Now by the bijection Rule |A = B , and by the Product rule, | | |6 7 B| = 2 .|2 · · 3 (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 have different 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 all have 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 second value, 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 4 Problem 5. A derangement is a permutation (x1, x2, . . . , xn) of the set {1, 2, . . . , n} such that xi =� i for all i. For example, (2, 3, 4, 5, 1) is a derangement, but (2, 1, 3, 5, 4) is not because 3 appears in the third position. The objective of this problem is to count derangements. It …
View Full Document
Unlocking...