6
$\begingroup$

Problem: Given any set $S$ of $9$ points within a unit square, show that there always exist $3$ distinct points in $S$ such that the area of the triangle formed by these $3$ points is less than or equal to $\frac{1}{8}$

I am supposed to do this using the pigeonhole principle. I used the usual technique of partitioning the square to conclude that there is a triangle with area less than $\frac{1}{4}$ but I am unable to improve the bound.

Please help.

$\endgroup$
  • 3
    $\begingroup$ You need a sharper estimate of the area of the largest triangle in a $0.5\times 0.5$ square. $\endgroup$ – André Nicolas Jun 5 '16 at 18:12
  • $\begingroup$ @AndréNicolas, ooh! got it. got it. thanks $\endgroup$ – Subham Jaiswal Jun 5 '16 at 18:18
  • $\begingroup$ You are welcome. $\endgroup$ – André Nicolas Jun 5 '16 at 18:20
6
$\begingroup$

First divide the unit square into four squares with sides $s$ of length $\frac{1}{2}$.

Now given $9$ points and $4$ squares, by the pigeon hole principle at least one square $S$ which contains three of those points. Those three points form a triangle whose area $A$ is bounded by half the area of $S$ (see here for a proof). Since the sides $s$ of $S$ have length $\frac{1}{2}$, we have that $$ A\leq \frac{1}{2}s^2= \frac{1}{2}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{8}$$

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