3

Suppose we are given $n$ points in a plane, where $n\ge 4$ and no 3 of the points are collinear. If $k$ distinct triangles are designated with vertices among the $n$ points, show that no more than $k(n-3)$ of the $n\choose 4$ groups of four points contain at least one of the designated triangles.

I tested $n=4$, and had $2$ distinct triangles designated among the 4 points and I had to prove that: No more than $2$ of the $1$ group of four points contain at least one of the designated triangles?

Also, can I clarify something? When it says

$k$ distinct triangles are designated with vertices among the $n$ points,

it basically means that $k$ can take on any value from $1$ to $n\choose 3$, right? If $n=4$, $k$ could be $1,2,3$, or $4$ right? (up to $4$ triangles can be formed from $4$ points)

5xum
  • 123,496
  • 6
  • 128
  • 204
miamiheatftw
  • 145

1 Answers1

1

Your example with $n=4$, $k=2$, shows that the inequality to be shown mya not be sharp, or at least not for all $n$ and $k$.

Hint: The expression $k(n-3)$ seems to hint towrds considereing tuples consisting of a) one of the triangles, b) any of the points except three (which three, may depend on the triangle in a) So how do you find three special points given a triangle? How do you get a group of four points, given a triangle and another point?

Hagen von Eitzen
  • 374,180
  • You can get a group of 4 points by taking the 3 points of an arbitrary triangle, and adding any one of the other n-3 points. Since there are k triangles, there are at most k(n-3) groups of 4 points which contain at least one of the k triangles. However, we may have overcounted because some of the group of points may be counted for more than one triangle. I still don't get what it means by 2 of the 1 group. – miamiheatftw Aug 06 '14 at 07:13
  • @miamiheatftw Well, ther is only one grou of four points if you have only $n=4$ points to begin with, hence the number of four-point-groups containing a triangle is trivially $\le 1$. Now if you have $k$ triangles, the claim is that the number of four-point-groups containing a triangle is $\le k(n-3)$. As $k(n-3)=k$, we have to show that the number of four-point-groups containing a triangle is $\le k$.As we already know that the number of four-point-groups containing a triangle is $\le1$, there is nothing to show for $k\ge 1$; of course there is also nothing to show for $k=0$. So all is fine. – Hagen von Eitzen Aug 06 '14 at 16:59
  • Ah, I think it's getting to me now. So, we just have to show that it's "no more" than k(n-3). – miamiheatftw Aug 06 '14 at 19:23