There are $n$ points in the page such that no three of them are collinear.Prove that number of triangles that vertices of them are chosen from these $n$ points and area of them is 1,is not greater than $\frac23(n^2-n)$.
Problem
Source:
Tags: geometry, combinatorics, counting question
30.04.2010 21:08
Doesn't it suffice to prove that nC3 <= \frac{2}{3}(n^2-n) Well, my latex doesn't seem to be working!!!
30.04.2010 21:17
consider a graph wich its vertices are the n points and its edges are the segments between these points . every edge can give us at max 4 triangles which the area is 1 ( because no three are collinear ) and every triangle with area 1 gives us exactly 3 edges ,if m be the number af triangles with area 1 , then with double counting we have that m is smaller or equal to 2n(n-1)/3 .
30.04.2010 23:26
The poster didn't post the correct statement of problem. Please edit it so that other readers don't get confused.
01.05.2010 08:18
Actually AMPARVARDI didn'y post the real problem. The real problem is this : There are $ n $ points in the page such that no three of them are collinear. Prove that number of triangles that vertices of them are chosen from these points and their area is $ 1 $ , is not greater than $ \frac{2}3(n^{2}-n) $ .
03.05.2010 16:31
the way i see it, four triangles with area 1 can share at most an edge, so if we multiply the number of edges by 4 we will identify a 1-triangle as a unique triplet of edges, not sharing any of its edges with others. So we switch the initial graph with a multigraph having 4 edges where there was one before. The number of edges cannot exceed 2N(N-1) now. At this point we count triangles. For each triangle we count we discard three edges. Thus the number of triangles cannot exceed 2N(N-1)/3.
11.05.2010 09:52
Consider any pair of points A and B. The loci of points C such that the area of ABC is 1 are two lines of a certain distance from AB. There are at most two points on each line, hence there are at most 4 such triangle for each pair of points. In total, there are at most 4C(n,2) triangles, but each triangle is counted three times, hence there are at most 4C(n,2)/3 triangles.
13.05.2010 18:03
Johan Gunardi wrote: Consider any pair of points A and B. The loci of points C such that the area of ABC is 1 are two lines of a certain distance from AB. There are at most two points on each line, hence there are at most 4 such triangle for each pair of points. In total, there are at most 4C(n,2) triangles, but each triangle is counted three times, hence there are at most 4C(n,2)/3 triangles. Agreed! =D Finally I can see your post =)
31.05.2015 16:16
Just wondering, does equality hold here and how? Thanks!
01.06.2015 16:32
Goutham wrote: Doesn't it suffice to prove that nC3 <= \frac{2}{3}(n^2-n) Well, my latex doesn't seem to be working!!! You need to put american dollar sign before and after. ${ n \choose 3} \leq \frac{2}{3}(n^2-n) $
08.01.2017 11:02
When does equality hold? Doesn't this look like a weak inequality?
29.03.2022 16:58
Let $A,B$ be $2$ point's with distance $d$. Assume $2$ lines with distance $\frac{2}{d}$ from $AB$. Note that all triangles which one of their points lies on this $2$ lines and other points are $A,B$ have area $1$. Because of condition "no three of them are collinear" we have at most 4 points possible so we can at most have 4 triangles for $A,B$ but Note that for each triangle we count it 3 times, so the answer is : $\frac{4}{3}{ n \choose 2} = \frac{2}{3}n^2 - n$.