3
$\begingroup$

Let $S$ be a set of $n$ points in the plane in general position. Each 3 points of S span a triangle. Total number of triangles spanned by S:

$$\binom{n}{3}=\frac{n(n-1)(n-2)}{6}=\frac{1}{6} n^3-O(n^2 )$$

We know that Every set of $n$ points in general position in the plane can be partitioned into $6$ parts of almost equal size by $3$ concurrent lines (at least $\frac{n}{6}-c$(where $c$ is constant) points in each part).

Let $x$ be the point of intersection of the $3$ lines.

I need to prove that x is contained in at least $\frac{n^3}{27}-O(n^2 )$ triangles.

My approach:

enter image description here

•Every triangle of the form ACE contains $x$, the number of the triangles of this form $\frac{n^3}{216}.$

•Every triangle of the form BDF contains x, the number of the triangles of this form $\frac{n^3}{216}.$

•For every edge of the form AD, either adding any point of E makes a triangle that contains x, or adding any point of C, the number of the triangles of this form $\frac{n^2}{36}(\frac{n}{6}+\frac{n}{6})=\frac{n^3}{108}.$

How to proceed after then? I have stucked at this stage.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ For ACE pattern you have $n^3/216$ triangles, not $n^3/6$. Totally you already got $2\cdot(n^3/216)+3\cdot (n^3/108)=n^3/27$ triangles, as needed. $\endgroup$
    – Fedor Petrov
    Commented Aug 9 at 2:57
  • 1
    $\begingroup$ @FedorPetrov yes, you are right, would you put as answer? I will accept it. $\endgroup$
    – Forest
    Commented Aug 9 at 2:59

1 Answer 1

Reset to default
4
$\begingroup$

Your argument already gives $$2\cdot\frac{(n-6c)^3}{216}+3\cdot \frac{(n-6c)^3}{108}=\frac{(n-6c)^3}{27}$$ triangles.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.