We choose 100 points in the coordinate plane. Let $N$ be the number of triples $(A,B,C)$ of distinct chosen points such that $A$ and $B$ have the same $y$-coordinate, and $B$ and $C$ have the same $x$-coordinate. Find the greatest value that $N$ can attain considering all possible ways to choose the points.
Problem
Source: Hong Kong 2019 TST 2 P4
Tags: combinatorics
01.05.2019 22:03
Let $X$ and $Y$ denote the (finite) set of all lines parallel to $x$-,$y$-axis that contains at least one point among those 100 points. For any line $\ell \in X\cup Y$, let $a_{\ell}$ denotes the number of points that lie on $\ell$. Note that $|X||Y|\geqslant 100$ and that $1\leqslant |X|,|Y|\leqslant 100$. Easy to see that the number of such triples is at most $$\left( \sum_{\ell \in X}{(a_{\ell}-1)}\right)\left( \sum_{\ell \in Y}{(a_{\ell}-1)}\right)=(100-|X|)(100-|Y|)\leqslant (100-|X|)\left( 100-\frac{100}{|X|}\right) \leqslant 8100.$$The last inequality is equivalent to $(|X|-10)^2/|X|\geqslant 0$ which is true. The equality case is easy, and so the answer is $8100$.
26.05.2019 02:24
We claim that the maximum value of $N$ is $\boxed{8100}$. To see this, consider a $10\times 10$ grid. Each rectangle of four points contributes exactly $4$ such triples (the triples correspond to right triangles with legs parallel to the axes). There are $\binom{10}{2}^2$ rectangles, so there are $4\binom{10}{2}^2=8100$ right triangles. Let $y_1,\ldots,y_r$ be the distinct $y$ coordinates in all the $100$ points, and let $m_i$ be the number of points with $y$ coordinate equal to $y_i$. Focusing in on some particular $i$, we have $m$ points all on a horizontal line. Let $n_j$ for $1\le j\le m$ be the number of points on the perpendicular line passing through the $j$th point not equal to the point on the horizontal line. We see that the number of triples with $y$ coordintae equal to $y_i$ is \[n_1(m_i-1)+\cdots+n_m(m_i-1)=(m_i-1)(n_1+\cdots+n_m).\]We have that $n_1+\cdots+n_m$ is at most $100-m_i$, so the total number of points is at most \[N\le\sum_{i=1}^r(m_i-1)(100-m_i).\]Note that $f(m)=(m-1)(100-m)$ is a concave function as $f''(m)=-1$, so by Jensen's inequality, we have \[N\le r(100/r-1)(100-100/r)=100(100/r-1)(r-1)\]since $\sum m_i=100$. Note that \[(100/r-1)(r-1)=101-(100/r+r)\le 101-2\sqrt{100}=81\]by AM-GM, so \[N\le 100\cdot 81=\boxed{8100}.\]This completes the proof.