Massachusetts Institute of Technology Handout 23 6.042J/18.062J: Mathematics for Computer Science March 16, 2000 Professors David Karger and Nancy Lynch

Problem Set 5 Solutions

Problems:

Problem 1 Let (x_{i}, y_{i}), i = 1, 2, 3, 4, 5 be a set of five distinct points in the plane with integer coordinates. Show that the midpoint of the line segment joining at least one pair of these points has integer coordinates. Solution. The midpoint of the segment whose endpoints are (a, b) and (c, d) is (\frac{a+c}{2}, \frac{b+d}{2}). Clearly the coordinates of these fractions will be integers as well if and only if a and c share parity (both odd or even) and b and d also share parity. Thus, there are four possible pairs of parities: (odd,odd), (odd,even), (even,odd), (even,even). Since we are given five points, the pigeonhole principle guarantees that at least two of them will have the same pair of parities; therefore, the midpoint of the line segment joining those two points will have integral coordinates.

Problem 2 Divisibility

(a) Show that in any set of n + 1 positive integers not exceeding 2n there must be two that are relatively prime.^{1}

(b) Problem removed Solution. Partition the set of numbers from 1 to 2n into the n pigeonholes {1, 2}, {3, 4}, …, {2n− 1, 2n}. If we have n + 1 numbers from this set (the pigeons), then two of them must be in the same hole. This means that among our collection are two consecutive numbers. Clearly consecutive numbers are relatively prime (since every common divisor must divide their difference, 1).

Problem 3 Problem removed

Problem 4 Jelly beans of 8 different colors are in 6 jars. There are 20 jelly beans of each color. Use the pigeonhole principle to prove that there is some jar that contains at least two beans each from two different colors of jelly beans. Solution. There are 20 beans of each color. Since there are 6 jars, by the strong pigeonhole principle for each color there is a jar containing at least 20/6 ≥ 2 beans of that color. Since the number of colors is greater then the number of jars, using the pigeonhole principle again, there must be a jar containing two pairs of jelly beans from two different colors of jelly beans.

1If integers a and b are relatively prime, then they do not share any factors; i.e., for c ∈ ℕ, c|a and c|b implies that c = 1.

Problem 5 Fourteen hackers and eight theoreticians are on the faculty of a school’s EECS department. The individuals are distinguishable. How many ways are there to select a committee of six members if at least 1 hacker must be on the committee? You may express this in terms of binomial coefficients. Solution. We need to count all possible combinations of people such that there is at least one woman in every combination, but we must remember not to count any combinations multiple times. We can have committees with 1 woman, 4 men: \binom{6}{1}\binom{9}{4} 2 women, 3 men: \binom{6}{2}\binom{9}{3} 3 women, 2 men: \binom{6}{3}\binom{9}{2} 4 women, 1 man: \binom{6}{4}\binom{9}{1} 5 women, 0 men: \binom{6}{5}\binom{9}{0}

So there are \binom{6}{1}\binom{9}{4} + \binom{6}{2}\binom{9}{3} + \binom{6}{3}\binom{9}{2} + \binom{6}{4}\binom{9}{1} + \binom{6}{5}\binom{9}{0} = 2877 different possibilities for committees.

Another way to solve this problem is to say that there are \binom{15}{5} different committees, and \binom{9}{5} committees of just men. So there are \binom{15}{5} − \binom{9}{5} different possibilities for committees.

Note that 6 · \binom{14}{4} = 6006 is not a correct answer. The product rule only applies when you are choosing two separate sets of items which are independent of each other. In this case, a woman is chosen and then the remainder of the committee is chosen, but since there may be women in the last set of 4 chosen, we will be double counting. For example, if A and B are women, and C, D, and E are men, then we will count A, {BCDE} as well as B, {ACDE}.

Problem 6 Consider the Towers of Hanoi game with n disks and 3 distinct poles. An arrangement of the disks on the poles is said to be legal if no disk rests on a smaller disk. How many different legal arrangements of the n disks on the 3 poles are there?

Problem 7 How many integers in the range from 1 to 1000 are not divisible by any of the numbers 6, 10, and 15? Solution. Here we use inclusion-exclusion to count the number of integers from 1 to 1000 not divisible by 6, 10, or 15. Make a table, and add the numbers with appropriate signs:

divisible by least common multiple number of integers include/exclude
each of  of divisors  from 1 to 1000  +/−
1  1000  +
6  6  166  −
10  10  100  −
15  15  66  −
6, 10  30  33  +
6, 15  30  33  +
10, 15  30  33  +
6, 10, 15  30  33  −

These add up to 734.

Problem 8 A positive integer is called square-free if it is not divisible by the square of any positive integer greater than 1. For example 35 = 5 · 7 is square-free but 18 = 2 · 3^{2} is not. 1 is square-free.

Use inclusion-exclusion to find the number of square-free positive integers strictly less than 151. Solution. We use inclusion-exclusion as done in lecture for the case of prime numbers. We first compute the number of positive integers less than 150 that are not square free. Let A_{2} (respectively, A_{3}, A_{5}, A_{7}, A_{11}) be the set of multiples of 2^{2} (respectively, 3^{2}, 5^{2}, 7^{2}, 11^{2}) less than 150. The cardinality of the union of these sets is given by

|A_{2} ∪ A_{3} ∪ A_{5} ∪ A_{7}| = |A_{2}| + |A_{3}| + |A_{5}| + |A_{7}| + |A_{11}| − |A_{2} ∩ A_{3}| − |A_{2} ∩ A_{5}|
= ⌊150/2^{2}⌋ + ⌊150/3^{2}⌋ + ⌊150/5^{2}⌋ + ⌊150/7^{2}⌋ + ⌊150/11^{2}⌋
−⌊150/(2^{2}3^{2})⌋ − ⌊150/(2^{2}5^{2}⌋
= 37 + 16 + 6 + 3 + 1 − 4 − 1
= 58

Therefore the number of square-free positive integers less than 150 is

150 − 58 = 92 .

Problem 9 Enumeration and permutations

(a) Kyle is manager of the MIT Chess Club. After a long and grueling match, the players have gone home, leaving Kyle to put the players’ unlabeled chess sets back in their lockers. If there are n players/lockers and n chess sets, how many ways could Kyle place chess sets in lockers such that there is exactly one chess set in each locker, disregarding the correctness of such placement? Solution. We can formulate this as a function-counting problem. Since there are n chess sets and n lockers, we can assign each chess set a unique number between 1 and n inclusive, and do the same for the lockers. Then, we are looking for an injective function from {1, …, n} → {1, …, n}. Note that the first element of the domain has n possible mappings; the second has n − 1 possible mappings (i.e., all but the first element); the third has n−2 possible mappings (i.e., all but the first two); and so on, for all n elements of the domain. This is simply n!, the number of permutations of {1, …, n}.

(b) Say Kyle recognizes Josh’s chess set, so he can place that one correctly, but recognizes none of the other chess sets. How many possible ways can Kyle place chess sets in lockers assuming he at least gets Josh’s right? Solution. We function count, as before. Without loss of generality, assign Josh’s chess set and locker the number 1, and set f(1) = 1 in our function. We can now create an injective function on the remaining elements; by part (a), this is simply (n − 1)!.

(c) Say Kyle really resents Josh’s brainpower, and decides to get even by putting Josh’s chess set in another student’s locker. How many ways can he place chess sets in lockers assuming he does not place Josh’s chess set into Josh’s locker?

Solution. Again, we function count. (Notice a pattern?) Without loss of generality, assign Josh’s chess set and locker the number 1, as before. We can first choose an element j ≠ 1 from the domain to map to 1 ((n − 1) ways). Then, we note that we have n − 1 elements of the domain and n − 1 elements of the codomain in which we want an injection, which we can choose in (n − 1)! ways from part (a). This gives us (n − 1)(n − 1)!, which makes sense since, from part (b), (n − 1)(n − 1)! + (n − 1)! = n!.

(d) Kyle has a sudden change of heart and decides to be nice to Josh. At this time, he also realizes that Shishir has conscientiously written his name on the outside of his chess set, so now Kyle knows the correct destinations of two chess sets. How many arrangements are there now? Solution. As in part (b), we can simply create an injective function on the remaining elements, which gives us (n − 2)!.

(e) Say Kyle is taking mind-altering drugs and has again changed his mind about Josh. Still being able to discern Josh’s and Shishir’s chess sets—but wishing to ill-place Josh’s—Kyle can place chess sets in lockers in how many ways? Solution. Assign 1 to Josh’s locker and chess set, and 2 to Shishir’s locker and chess set. We know that |A ∩ B| = |A| − |A ∩ B̄|, so if we take A to be the set of functions with f(2) = 2 and B to be the set of functions with f(1) ≠ 1, then we know |A| and |A ∩ B̄|, the latter of which is the solution to the previous part; so, the answer is (n − 1)! − (n − 2)! = (n − 2)(n − 2)!.

Problem 10 On a set of n elements how many of the following are there

(a) binary relations? Solution. 2^{n^{2}} since there are this many different 0 − 1 matrices of order n.

(b) symmetric binary relations? Solution. The matrix associated with a symmetric relation is symmetric. Since there are 2^{n+\binom{n}{2}} different symmetric matrices there are an equal number of symmetric relations.

(c) reflexive binary relations? Solution. The matrix associated with a reflexive relation has 1’s along the main diagonal . Hence the number of such matrices, and therefore reflexive relations, is 2^{n^{2}−n} .

(d) symmetric and reflexive binary relations? Solution. The matrix associated with a symmetric and reflexive relation is symmetric and ha s 1’s along the main diagonal. Hence the number of such relations is 2^{\binom{n}{2}}.

(e) symmetric or reflexive binary relations? Solution. The number of symmetric or reflexive relations = the number of reflexive relations + the number of symmetric relations − the number of reflexive and symmetric relations = 2^{n^{2}−n} + 2^{n+\binom{n}{2}} − 2^{\binom{n}{2}}.