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
  • 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
    Commented Jun 5, 2016 at 18:12
  • $\begingroup$ @AndréNicolas, ooh! got it. got it. thanks $\endgroup$
    – Subham Jaiswal
    Commented Jun 5, 2016 at 18:18
  • $\begingroup$ You are welcome. $\endgroup$
    – André Nicolas
    Commented Jun 5, 2016 at 18:20

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .