Massachusetts Institute of Technology Handout 44 6.042J/18.062J: Mathematics for Computer Science October 30, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 7 Solutions

Read section 4.3 in Rosen.

Problem 1. A liscence plate has three digits followed by three letters. However, there are 11 three-letter sequences that the state deems offensive and never uses. These sequences are... never mind. How many inoffensive liscence plates are there?

The number of three-letter sequences is 26^{3} = 17576 by the product rule. Therefore, there are 17576 − 11 = 17565 inoffensive three-letter sequences. The number of three-digit sequences is 10^{3} = 1000 by the product rule. Therefore, the number of inoffensive liscence plates is 17565000, again by the product rule.

Problem 2. How many binary strings b_{1}b_{2} … b_{2n} are there such that for all 1 ≤ k ≤ n, one of b_{2k−1} and b_{2k} is a zero and the other is a one?

This is the set of binary strings that can be formed by concatenating n pairs of binary digits, where each pair is either 01 or 10. Therefore, the number of such strings is 2^{n} by the product rule.

Problem 3. Use inclusion-exclusion to prove that at most a quarter of the numbers less than one million are prime.

We will find a lower bound on the number of composite numbers less than one million. This will give an upper bound on the number of primes less than one million. Define the following sets:

S_{2} = {4, 6, 8, 10, …, 1000000}
S_{3} = {6, 9, 12, 15, …, 999999}
S_{5} = {10, 15, 20, 25, …, 1000000}
S_{7} = {14, 21, 28, 35, …, 999999}

The union of these sets is a subset of the composite numbers less than one million. Therefore, the size of the union of these sets is a lower bound on the number of composite numbers less than 1000000. By the inclusion-exclusion principle,

|S_{2} ∪ S_{3} ∪ S_{5} ∪ s_{7}| = |S_{2}| + |S_{3}| + |S_{5}| + |S_{7}|

−|S_{2} ∪ S_{3}| − |S_{2} ∪ S_{5}| − |S_{2} ∪ S_{7}| − |S_{3} ∪ S_{5}| − |S_{3} ∪ S_{7}| − |S_{5} ∪ S_{7}| +|S_{2} ∪ S_{3} ∪ S_{5}| + |S_{2} ∪ S_{3} ∪ S_{7}| + |S_{2} ∪ S_{5} ∪ S_{7}| + |S_{3} ∪ S_{5} ∪ S_{7}|

−|S_{2} ∪ S_{3} ∪ S_{5} ∪ S_{7}|

We can compute the sizes of all the above sets using simple, if tedious arithmetic. For example:

|S_{3} ∪ S_{5} ∪ S_{7}| = |{105, 210, 315, …, 999915}|
= ⌊\frac{1000000}{105}⌋
= 9523

Plugging the set sizes into the inclusion-exclusion formula gives:

|S_{2} ∪ S_{3} ∪ S_{5} ∪ s_{7}| = 499999 + 333332 + 199999 + 142856

−166666 − 100000 − 71428 − 66666 − 47619 − 28571 +33333 + 23809 + 14285 + 9523 −4761

= 771425

Among numbers less than one million, the number 1 is neither prime nor composite, and at least 771425 numbers are composite. Therefore, there are at most 1000000 − 1 − 771425 = 228574 primes. Thus, at most a quarter of the numbers less than one million are prime.

The actual number of primes less than one million is only 78498, so our upper bound is quite loose.

Problem 4. Suppose that two teams play a series of games against each other until one team is ahead by two games or one team wins a total of three games. How many series are possible?

We can compute the solution with a tree diagram. We have created an equivalent outline of the possibilities below.

  Team A beats team B.
    Team A beats team B.  Team A wins.  (Case 1.)

Team B beats team A.
Team A beats team B.
Team A beats team B.  Team A wins.  (Case 2.)
Team B beats team A.
  Team A beats team B.  Team A wins.  (Case 3.)
  Team B beats team A.  Team B wins.  (Case 4.)
Team B beats team A.
Team A beats team B.
  Team A beats team B.  Team A wins.  (Case 5.)
  Team B beats team A.  Team B wins.  (Case 6.)
Team B beats team A.  Team B wins.  (Case 7.)
Team B beats team A.
Team A beats team B.
Team A beats team B.
Team A beats team B.  Team A wins.  (Case 8.)
Team B beats team A.
  Team A beats team B.  Team A wins.  (Case 9.)
  Team B beats team A.  Team B wins.  (Case 10.)
Team B beats team A.
Team A beats team B.
  Team A beats team B.  Team A wins.  (Case 11.)
  Team B beats team A.  Team B wins.  (Case 12.)
Team B beats team A.  Team B wins.  (Case 13.)
Team B beats team A.  Team B wins.  (Case 14.)

There are 14 possible series.

Problem 5. Determine the cardinality of each of the following sets.

(a) The set of bijective functions from the set of n-bit strings to itself.

By the product rule, the number of n-bit strings is 2^{n}. Order these strings in an arbitrary way. Some string maps to the first binary string, some string maps to the second binary string, and so forth. Thus, there is a one-to-one correspondence between bijective functions and permutations of the n-bit strings. Therefore, the number of such functions is 2^{n}!.

(b) The set of n × n matrices such that each of the numbers 1 to 2n appears at most once in each column.

We first compute the number of possible columns. The top entry in a column can be chosen in 2n ways, the next entry can be chosen in 2n − 1 ways, and so 4 Handout 44: Problem Set 7 Solutions

forth. Thus, overall, a column can be chosen in (2n)!/n! ways. Since the matrix consists of n columns, the number of matrices is given by the product rule:

(\frac{(2n)!}{n!})^{n}