1
$\begingroup$

There are $n$ points in a plane of which no $3$ are collinear. Prove that the number of triangles whose vertices are chosen from $n$ points and whose area is $1$ is not greater than $2(n^2-n)/3$. The bound can be simplified by ${1\over3} \cdot(2+2)$ multiplied by $n\choose 2$. I have tried by the Pigeonhole Principle but that didn't help. Can anyone suggest me an alternate method? Or how can I prove it by the Pigeonhole principle? Any help would be appreciated.

$\endgroup$
12
  • $\begingroup$ Welcome to Mathematics SE. Take a tour. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. $\endgroup$ Commented Jan 21, 2023 at 14:10
  • $\begingroup$ So do you mean that we choose n random points in a plane (of which no 3 of them are collinear) and that then the maximum number of triangles is given as you said? If yes I think you can just start your proof by first taking three points which form a triangle of area 1. Then the next step could be to prove that one always can choose a next point (which satisfies the collinearity-restriction) such that the triangle formed by two of the first three points and the new point forms a triangle of area 1. The last step is to show that this is the maximum number of such triangles and is smaller than $\endgroup$ Commented Jan 21, 2023 at 14:37
  • $\begingroup$ the formula you have given. (finish of my first comment.) $\endgroup$ Commented Jan 21, 2023 at 14:37
  • $\begingroup$ @unknownuser It helps a lot but how can I prove the last step? $\endgroup$
    – user1135640
    Commented Jan 21, 2023 at 14:39
  • 2
    $\begingroup$ Hint: Write the bound as$\frac13\cdot{n\choose2}\cdot(2+2)$ $\endgroup$ Commented Jan 21, 2023 at 17:21

1 Answer 1

3
$\begingroup$

I found this question listed in AoPS as 2010 Iran MO Round 2 P2. I could not find any solutions there. So, here is this answer which becomes obvious once you see the meaning behind the given bound. Since the solution is not difficult, I'll instead walk you through my reasoning as I went.

  1. There must be something about $\frac{2(n^2-n)}{3}$. Since it is not obvious, let's factorize this.
  2. Okay, we have $\frac23 n(n-1)$. Not that helpful unless you have seen the expression for the number of line segments made by $n$ points of which no $3$ are collinear. That is $n(n-1)/2$. (Since I applied it after a long time, I had forgotten the 'divide by $2$' part while I was trying to solve it, but thanks to @MikeEarnest I corrected my error.) I'll try to explain why this is so in short. A line segment has $2$ endpoints. You can choose the first endpoint in $n$ ways, and the second one in $n-1$ ways. So you multiply them to get the total line segments. But the trouble is, you've counted every line segment twice ($AB$ is the same as $BA$), so you divide by $2$.
  3. Now we have reasoned out that this expression is a multiple of the number of possible line segments, precisely, $\frac{4}{3}$ times $\frac{n(n-1)}{2}$. We need to figure out why we have $4/3$. Our inequality is completely based on counting the maximum number of triangles with area of $1$, so maybe we divide by $3$ to account for counting every triangle thrice.
  4. The $4$ cannot be understood unless you get to the solving problem itself by using the reasoning of why the expression is as it is.

Let $k_n$ be the maximal number of triangles formed by $n$ points which are arranged in the most optimal way. Throughout this answer, we will only try to find the maximum value of $k_n$.
Suppose you choose any line segment (can be done in $n(n-1)/2$ ways). This line segment will have some arbitrary length, say $l$. If this segment is the base (that is, one of the sides) of a required triangle, we can find the height $h$: $$0.5lh = 1 \implies h = \frac2l$$ This height may vary for segment to segment. Suppose there are $4$ points at a distance of $2/l$ from the segment (by the Pigeonhole principle, you have $2$ holes on either side of the line, and each hole can accommodate $2$ points, or pigeons at max because a third point at the same distance on the same side of the line would make $3$ points collinear). This is the maximal case: you can form $4$ required triangles from each line segment. So, you have $4n(n-1)/2 = 2n(n-1)$ required triangles. But, you have counted every triangle thrice (you must have taken all three sides of the triangle as bases while choosing the base), so divide by $3$ to get the final expression: $$\frac{2n(n-1)}{3}$$Thus, $$\color{green}{k_n \le \frac{2(n^2-n)}{3}}$$ QED.

$\endgroup$

You must log in to answer this question.