2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.$$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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}

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.