Massachusetts Institute of Technology Handout 36 6.042J/18.062J: Mathematics for Computer Science October 23, 1998 Professors Nancy Lynch and Srini Devadas

Notes for Recitation 7 (10/23/98)

1 The Pigeonhole Principle

We showed in lecture that for finite sets, |A| ≤ |B| iff there is an injection from A into B. The contrapositive of this fact is

Corollary 1.1 (The Pigeonhole Principle) If there are more pigeons than pigeonholes, then there must be at least two pigeons in one hole.

Formally, let A and B be finite sets. If |A| > |B| and f : A ↦ B, then there exist distinct elements a and a′ in A such that f(a) = f(a′).

As a trivial application of the Pigeonhole Principle, suppose that there are three people in a room. The pigeonhole principle implies that two have the same gender. In this case, the “pigeons” are the three people and the “pigeonholes” are the two possible genders, male and female. Since there are more pigeons than holes, two pigeons must be in the same pigeonhole; that is, two people must have the same gender.

The pigeonhole principle seems too obvious to be really useful, but the next two examples show how it gives short proofs of results that are difficult to obtain by other means.

A problem on an old final exam was to prove the following claim:

Claim 1.2 In every set of 1000 integers, there are two integers x and y such that 573 | (x − y).

At first glance, this looks very hard! Those 1000 numbers could be anything! Since there are no less than 1000 integer-valued variables here, even our old standby, induction, seems hopeless. Surprisingly, however, there is a short proof using the Pigeonhole Principle.

To apply the Pigeonhole Principle, we must identify two things: pigeons and holes. Furthermore, to prove anything with the Pigeonhole Principle, we must have more pigeons than holes. Since there are only two numbers mentioned in this problem, a natural thing to try is 1000 pigeons and 573 holes.

Under this interpretation, a pigeon is an integer, but what is a hole? Ideally, the existence of two pigeons and in the same hole should be equivalent to the existence of two numbers x and y such that 573 | (x − y). This suggests numbering the holes 0, 1, … 572 and putting in hole n all integers congruent to n modulo 573. Now we can construct a proof:

Proof. Let S be a set of 1000 integers. Let M = {0, 1, … 572}. Let f : S ↦ M be the function defined by f(n) = n mod 573. Since |S| > |M|, Corollary 1.1 implies that there exist distinct elements x and y in S such that f(x) = f(y). This means (x mod 573) = (y mod 573) and so 573 | (x − y).

Really there was nothing special about the numbers 1000 and 573 other than the fact that 1000 > 573. We could have made a stronger claim: if n > m, then in every set of n integers, there are two integers x and y such that m | (x − y).

2 Strong pigeonholes

The Strong Pigeonhole Principle. If n(r − 1) + 1 pigeons are placed in n holes then there is at least one hole with r or more pigeons in it.

Proof. By contradiction. Assume for the purpose of a contradiction that there is a way of placing the pigeons in the holes so that all the holes have r − 1 or fewer pigeons. Then the total number of pigeons is at most n(r −1). This is a contradiction since we assumed that there are at least n(r − 1) + 1 pigeons.

An equivalent way of stating the principle is: If n pigeons are placed in r holes, then there is at least one hole with ⌈n/r⌉ pigeons in it.

Example: We will prove that there are at least 200 Americans with exactly the same number of hairs on their heads. First we estimate that the number of hairs on any person’s head is at most a million. There are over 200 million Americans. To apply the strong pigeonhole principle, think of Americans as pigeons, and that there is a hole for each unique number of possible hairs. That is all Americans with the same number of hairs go into the same hole. Now by the pigeon hole principle there must be some hole that gets at least 200, 000, 000/1000, 000 = 200 pigeons. That is there are at least 200 Americans with exactly the same number of hairs on their heads.

Example: Consider the following problem: we are to number the squares of a chessboard from 1 to 64. Is it possible to do this so that the difference between the numbers of any pair of adjacent squares (horizontally, vertically or diagonally) is no more than 8 ?

The answer is NO. Consider the square numbered 1 and the square numbered 64. We know that no matter where they are placed, there is a path of length at most 7 between them (i.e., in at most 7 hops to adjacent squares, we can go from the 1-square to the 64-square). To go from 1 to 64, there is a difference of 63 to be covered in 7 hops. Let us think of this difference as 63 pigeons and they have to each be placed in one of 7 holes. The holes represent which hop the step is taken in. Now by the strong PP there must be a hole with at least 63/7 = 9 pigeons. This means that there must be a hop which covers a difference of 9 or greater. That is there are a pair of adjacent squares that differ by at least 9.

2.1 Pigeonhole Principle Example: Weighing Balls

In the first tutorial you may have seen the following problem (illustrating reasoning by cases). There are 3 balls of which 2 have the same weight and one has a different weight. With two weighings on a balance scale, you must identify the odd ball and determine whether it is heavier or lighter than the rest. (A balance scale has a left pan and a right pan. In a weighing you put some balls in each pan. The scale then reveals whether the left pan is heavier, the right pan is heavier, or the two are equal.)

The problem is solvable using a strategy algorithm represented by a ternary tree. Each internal node in the tree represents a weighing such as, “put balls 1, 3 on one side and 2, 4 on the other side”. Each leaf node represents a result such as, “the 3rd ball is heavier than the rest”. A run of the algorithm corresponds to a path from the root to a leaf. At each internal node, we perform the weighing associated with the node. Based on the result – “leaning left”, “leaning right” or “balanced” we descend to one of the three children. When we reach a leaf, we output the indicated result.

(labels of balls in left pan, labels of balls in right pan)

                                 (1,2)
                                  /|\
                                 L = R
                                /  |  \
                               /   |   \
                         (1,3)   (2,3)   (2,3)
                         /|\       /|\       /|\
                        L = R     L = R     L = R
                       /  |  \   /  |  \   /  |  \
                      1H  2L 1L

“1H” means ball 1 is heavy, “2L” means ball 2 is light, etc.

Class exercise: Fill in remaining leaves.

Suppose that we wanted to solve the same problem with more balls, but still with only 2 weighings. If there are 5 balls, then we can apply pigeonholing to prove that no solution exists. (Of course we could do a simple case analysis here too, but case analysis gets elaborate if not prohibitive when there are a lot of balls, while pigeonholing can give simple bounds.)

Claim 2.1 The weighing problem with 5 balls cannot be solved with 2 weighings. The weighing problem with 14 balls cannot be solved with 3 weighings.

Proof. The pigeons are the possible situations. Since any one of balls could be the different weight one, and it could be either heavier or lighter than the rest. With 5 balls there are 10 pigeons, with 14 balls there are 28 pigeons. The holes are the 9 leaves of the depth-2 ternary tree used to represent the weighing strategy for the 5 ball case, or the 27 leaves of the depth-3 tree in the 14 ball case. Since there are more pigeons than holes, the Pigeonhole Principle implies that some hole must have two pigeons; that is, some leaf is not associated with a unique situation. Therefore, for every weighing strategy, there is some pair of situations that the strategy cannot distinguish. In at least one of these situations, the strategy must give the wrong answer.

In general, if there are n balls, we can compute a lower bound on the number of weighings necessary. In this case, there are 2n possible situations. If there are w weighings, then every strategy can be represented by a ternary tree with 3^{w} leaves. For a correct weighing strategy to exist, there must be as many leaves as situations. That is, we must have 3^{w} ≥ 2n or, equivalently, W ≥ log_{3} 2n.

3 Dilworth

We proved in an earlier recitation:

Theorem 3.1 If t is the length of the longest chain in a poset (A, ⪯) then A can be partitioned into t antichains.

Review: chain: all elements comparable (total order); antichain: all elements incomparable. We can use this along with Pigeonholing to prove a famous result about posets:

Theorem 3.2 (Dilworth) If t is the length of the longest chain in a poset with n elements, then the poset has an antichain of size ≥ n/t.

Proof. By previous result, the n elements can be partitioned into t antichains. The pigeons are the n elements. The holes are the t antichains. By Strong Pigeonholing, there must be ≥ n/t pigeons in some hole.

Posets arise in all sorts of contexts, and when they do Dilworth’s theorem can have interesting implications. As you will show in your second Team Problem.

4 Checkers

1. How many sets of size one or two are contained in the set of integers 0, …, n−1? Hint: There are n^{2} ordered pairs of integers 0, …, n−1, of which all but n have distinct elements.

2. Suppose n > 1 and we place checkers on exactly n + 1 squares of the n × n checkerboard. Show that some length occurs more than once as the distance between two different checkered squares. (More precisely, there are checkered squares S1 ≠ S2 and S3 ≠ S4 such that the distance between S1 and S2 is the same as the distance between S3 and S4, but {S1, S2} ≠ {S3, S4}.)

Solution:

1. There are n(n − 1) possible distinct ordered pairs of numbers 0, …, n − 1, and so n(n−1)/2 sets of exactly two such numbers, and n(n−1)/2+n = n(n+1)/2 sets of one or two numbers.

2. The distance between checkers at distinct positions (x_{1}, y_{1}) and (x_{2}, y_{2}) is uniquely determined by the set of two numbers {|x_{1} − x_{2}| , |y_{1} − y_{2}|}. The values of these differences can be 0, …, n−1 except that both can’t be zero since the positions are different. These are the holes. So there are n(n + 1)/2 − 1 holes.

Each set of two checkers is a pigeon. There are (n + 1)n/2 pigeons by reasoning as in (a). A pigeon gets assigned to a hole which is the difference of the x and y coordinates of the checker positions. Since there is one more pigeon than hole, there must be two pigeons in the same hole. That means the x and y coordinate differences, and hence the distance, between the two pigeons is the same.

5 Team Problems

Problem 1. Let S be the set of numbers 7, 77, 777, . . .. Prove that there is an element of S that is divisible by 1997.

We use the pigeonhole principle. Let the pigeons be the elements s ∈ S, and the holes be the numbers 0 … 1996. Let s be placed in s mod 1997.

Since there are more than 1997 elements of S, some hole must have two numbers, say s_{i} and s_{j}, with i and j 7’s respectively. Without loss of generality, assume that i < j.

Then, s_{j} −s_{i} = 77 … 700 … 0 where there are j −i 7’s and i 0’s. So, s_{j} −s_{i} = s_{j−i}·10^{i}. Since s_{j} mod 1997 = r = s_{i} mod 1997, s_{j} − s_{i} mod 1997 = 0, so 1997 | (s_{j} − s_{i}). But gcd(1997, 10^{i}) = 1, so 1997 must divide s_{j−i}.

Problem 2. Show that in any sequence of n integers, there is either an increasing subsequence of length \sqrt{n} or a decreasing subsequence of length \sqrt{n}.

1. Show that every DAG has a chain of length > \sqrt{n} or an antichain of size ≥ \sqrt{n}.

2. Define a DAG based on a given sequence of numbers so that chains correspond to increasing subsequences and antichains correspond to decreasing subsequences.

3. Put the above together to solve the problem.

1. From Dilworth’s theorem for every t > 0, there is either a chain of length > t or an antichain of size ≥ ⌈n/t⌉. For t = \sqrt{n}, this is exactly the statement we want to prove.

2. We define a DAG whose vertices are the numbers in the sequence. For the ordering, define (a, b) to be an edge if either a = b, or else (a < b and a comes before b in the sequence). A chain corresponds to an increasing subsequence moving to the right, but what does an antichain correspond to?

Lemma 5.1 If a, b are incomparable and a > b then a precedes b in the sequence.

Proof. By contradiction. Assume b precedes a. Then b < a and b precedes a, so (b, a) is an edge. This contradicts our assumption that a and b are incomparable.

Extend this to more than 2 elements:

Lemma 5.2 If a_{1}, a_{2}, …, a_{t} are incomparable and a_{1} > a_{2} > ⋯ a_{t}, then a_{1} a_{2}, ⋯, a_{t} form a decreasing subsequence.

Proof. (∀i), the fact that a_{i} > a_{i+1} implies that a_{i} precedes a_{i+1} in the sequence, by the previous lemma.

So given an antichain (a set of incomparable elements), arrange the elements so that they are in decreasing order and the “left of” relation follows, giving a decreasing subsequence.

3. Since we have a DAG on n elements, this implies that there is either a chain of size > \sqrt{n} or an antichain of size ≥ \sqrt{n}. By the analysis just above, this yields either an increasing sequence of length > \sqrt{n}, or a decreasing subsequence of length ≥ \sqrt{n}.