Proof in 19x19 square

Question

A $19x19$ square $ABCD$, where $A=(0,0)$ $B=(0,19)$ $C=(19,19)$ $D=(19,0)$ is given. Prove, that when we choose arbitrary 99 points of integer coordinates $(x,y)$ such that $x, y \mathbb \in <0,19>$ (inside ABCD square including borders), there always exists such rectangle (of any dimensions), that is formed by the $4$ chosen points (out of $99$) and each of its sides is parallel to the axes.

Answer 1

Let $N=20$. Assume the converse, there is no such a rectangle. Let a horizontal line $y=i$ contains $n_i$ choosen points. Then there are ${n_i\choose 2}$ pairs of these points. Since there are no such a rectangle, each pair of vertical lines $x=x_1$ and $x=x_2$ contains no more than one of these pairs. Thus the total number of pairs of points is not greather than the number of the pairs of vertical lines. That is

$$\sum\frac{n_i(n_i-1)}2 \le\frac {N(N-1)}2.$$

But $\sum n_i=M=99$. The inequality between quadratic and arythmetic means imply that $$\sum n_i^2\ge \frac 1N\left(\sum n_i \right)^2=\frac {M^2}N.$$

Thus $$\frac {M^2}N-M\le N(N-1),$$

$$\frac {99^2}{20}-99\le 20\cdot 19,$$

$$391.05\le 380,$$

a contradiction.