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

Problem Set 7

Due Date: Tuesday, April 4, 2000 in lecture.

Self-study:

Self-study reading: Rosen §2.1–2.2

Self-study problems: §2.1 3, 11, 17, 21, 25 §2.2 1, 3, 15, 19

Reading:

Rosen, Discrete Mathematics and Its Applications: §4.1–4.3

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.

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

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.

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.

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?

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 7 How many integers in the range from 1 to 1000 are not divisible by any of the numbers 6, 10, and 15?

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.

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?

(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?

(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?

(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?

(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?

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

(a) binary relations?

(b) symmetric binary relations?

(c) reflexive binary relations?

(d) symmetric and reflexive binary relations?

(e) symmetric or reflexive binary relations?