Fall 2012-2013
18.310 Assignment 1
Lecturer: Michel Goemans
This assigment is due tomorrow September 6th in your (mandatory) recitation.
1. Your name and email address?
2. Which other CI-Ms, if any, have you taken?
3. In just a few sentences, please tell us what you would like to learn this term as a mathemati-
cian.
4. Below you will find an exercise and two possible write-ups of solutions. Try to solve the
problem yourself first. Then read the solutions critically before recitation. There is nothing
for you to submit in writing but consider the following questions before recitation:
• What are the advantages and disadvantages of each solution?
• What do you think might be the audience, purpose and context of each solution?
Exercise. Imagine a rectangular grid of points, consisting of 4 rows and 100
columns. Each point is colored one of red, green or blue. Prove that, no matter
how the coloring is done, there will be 4 points of the same color that form the
corners of a rectangle (with sides parallel to the grid).
Solution 1. This is an application of the pigeonhole principle. For this, we need to define what
are our pigeons and what are our pigeonholes.
Let us start with our pigeonholes. We define a column pattern to be a choice of colors for the
four points of a column; in the example above, the column pattern for the left-most column is
blue-red-red-green. For each of the 4 points of a column, we can pick any of red, green, blue for
that point, and we obtain a column pattern. Notice that there are exactly 34 = 81 different column
patterns, for there are 3 choices for each of the 4 points.
To apply the pigeonhole principle, we label each column (which are our pigeons) by its column
pattern (which are our pigeonholes). Since there are more than 81 columns, there must be two
columns with the same column pattern. Now concentrate just on these two columns which are
colored identically; see the figure below for an illustration.
HW1-1
Since there are 4 rows and only 3 colors, we can again apply the pigeonhole principle to deduce
that 2 of the rows have the same color. But this gives us a rectangle whose 4 corners have the same
color, and we are finished.
Solution 2. We will prove a stronger statement, namely that 19 columns are sufficient to obtain
an axis-aligned rectangle with all corners having the same color.
We first need a few definitions. For an integer n, let [n] denote {1, 2, · · · , n}, and let a k × n
grid be the set [k] × [n]. A 3-coloring of the k × n grid is any function
f : [k] × [n] → {1, 2, 3}.
For mathematical convenience, we have replaced the 3 colors blue, red and green by 1, 2 and 3.
We are ready to state and prove our result.
Theorem 1. Let f be any 3-coloring of the 4 × n grid where n ≥ 19. Then there exist x1 , x2 ∈ [4]
with x1 6= x2 and there exist y1 , y2 ∈ [n] with y1 6= y2 such that f ((x1 , y1 )) = f ((x1 , y2 )) =
f ((x2 , y1 )) = f ((x2 , y2 )), i.e. (x1 , y1 ), (x1 , y2 ), (x2 , y1 ), (x2 , y2 ) form the corners of a monochromatic
rectangle.
Proof. By the pigeonhole principle, each column (·, y) (for 1 ≤ y ≤ n) contains some color i at
least twice (possibly it could even contain two colors twice). Label each column with a color used
twice (arbitrarily with one of the colors if two colors are used twice). As n ≥ 19 and we have
3 colors, by the generalized pigeonhole principle, there are at least 7 columns colored i for some
i ∈ {1, 2, 3}. Inside each such column (·, y), there are 42 = 6 possibilities for the pair (x1 , x2 ) of
positions with f ((x1 , y)) = i = f ((x2 , y)). Therefore by the pigeonhole principle, there must be
two values y1 6= y2 with f ((x1 , y1 )) = f ((x1 , y2 )) = f ((x2 , y1 )) = f ((x2 , y2 )) = i. This concludes
the proof of the theorem.
HW1-2
