existence of a lattice rectangle in a $13 \times 13$ grid

Question

Problem: Prove that if 53 points are chosen from a $13\times 13$ grid then there will necessarily exist a rectangle whose vertices are among the 53 points chosen.

My try: I am guessing we have to use Pigeonhole principle. I have observed that at least one of the 13 rows will contain at least 5 lattice points. But I can't proceed further.

Also, I observed that it's enough to prove that the number of non rectangle quadrilaterals is less than $\dbinom {53}{4}$. But it turns out that this is not true.

So please help.

Answer 1

Let's count, chosen one column, how many different pairs of points we can have in that column: this is $ {13 \choose 2}=78.$ Call $a_i$ the number of points that appear in one column, we have that $$a_1+a_2+...+a_{13}=53.$$ In the column $i$ there are $a_i \choose 2$ different column-pairs of points, if we prove that $${a_1 \choose 2}+{a_2 \choose 2}+...+{a_{13} \choose 2}>78$$ we are done. Now $${a_1 \choose 2}+{a_2 \choose 2}+...+{a_{13} \choose 2}=\frac{a_1^2+...+a_{13}^2-53}{2}.$$ But we have also that $$ \frac{a_1^2+...+a_{13}^2}{13}\ge\frac{(a_1+...+a_{13})^2}{13^2}=\frac{53^2}{13^2}$$ hence $a_1^2+...+a_{13}^2\ge216$ and so $${a_1 \choose 2}+{a_2 \choose 2}+...+{a_{13} \choose 2}\ge81>78.$$

Answer 2

Show that the minimum number of pairs $(a,i),(a,j)$ in the same row happens when one row has five points and the others have four.
Then there are 78 pairs of i,j.

Answer 3

For the $i$-th $1$ in the matrix, define $x_i$ to be the number of $1$'s to the left of that $1$. So $\sum_{i=1}^{53} x_i$ is the number of $1 \times 2$ all-$1$ submatrices. If this number is more than $\binom{13}{2}=78$, we have a pair of columns containing two $1 \times 2$ all-$1$ submatrices, i.e., a rectangle.

Since we have $13$ rows, for any $k \in \{0,1,2,\ldots,13\}$, we can have $x_i=k$ at most $13$ times.

If we sort the $x_i$'s in non-decreasing order, we get the termwise lower bound $$(x_i)_{i=1}^{53} \geq (\overbrace{0,\ldots,0}^{13 \text{ times}},\overbrace{1,\ldots,1}^{13 \text{ times}},\overbrace{2,\ldots,2}^{13 \text{ times}},\overbrace{3,\ldots,3}^{13 \text{ times}},4).$$ So $\sum_{i=1}^{53} x_i \geq 82>78.$ So there's a rectangle.

---

Here's an example to show that $52$ ones is okay (derived from a (13,4,1)-BIBD):

\begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ \end{bmatrix}