Discrete mathematics - pigeon hole principle given sets A = {1,2,...12} ; B = {1,2,...15}
Let S ⊂ A x B , |S| = 21
Prove that there exist two different pairs (x1,y1) , (x2,y2) 
in S such that
|x1 - x2 | + |y1 - y2| ≤ 4


*

*I think this solution can be proven by the pigeon hole principle, but I couldn't see it through..


Thanks,
 A: Pigeonholes don't look promising there. However, if you have an $S\subseteq\mathbb Z^2$ (of any size) such that any two points, then we can let the 12 points closest to each point of $S$ "belong" to that point:
    x
  x x x
x x s x x
  x x x
    x

and then if any point "belongs" to two different points of $S$ then those to points must satisfy $|x_1-x_2|+|y_1-y_2|\le 4$. (Convince yourself of this).
So the problem is to show that we can't place 21 such non-overlapping diamonds with their centers within $A\times B$.
Consider the rectangle $A\times B$ plus a boundary of width $1$ on each of its sides. The rectangle plus boundary contains $(12+2)(15+2)=238$ points.
Each of the 21 diamonds can have at most one point outside the width-1 boundary, except that we can place up to 4 diamonds in the corners of $A\times B$ with two points sticking out beyond the boundary. In total at most $25$ points can be outside the boundary.
The total area of the 21 diamonds is $21\times 13=273$.
But $273-25 > 238$.

In fact, by a closer accounting it turns out that no more than 10 points can stick out beyond the boundary, so even $|S|=20$ is impossible.
A: Here's an answer from the university:
divide AxB into 20 sets as such:
{3k-2, 3k-1, 3} x {3m-2, 3m-1, 3} 
where 1 ≤ k ≤ 4 and 1 ≤ m ≤ 5
this covers all numbers in the respective sets A, B and since |21| = S
by the pigeon hole principle we have at least 2 pairs in one of the sets and thus at least 2 pairs in S where |x1 - x2 | + |y1 - y2| ≤ 4
