Suppose we have $n$ lines in general position in the plane. Prove that there are at least $n-2$ ''small'' triangles. Here a "small" triangle is a triangle that is not contained in any larger triangle.
-
$\begingroup$ what does "general position" mean? i guess you are trying to exclude the possibility of parallel lines? $\endgroup$– SuvritNov 25, 2010 at 21:40
-
$\begingroup$ Yes, and also no $3$ lines concurrent. $\endgroup$– Puraṭci VinnaniNov 25, 2010 at 22:01
-
$\begingroup$ You mean at least n-2 triangles? $\endgroup$– Gjergji ZaimiNov 25, 2010 at 22:23
-
$\begingroup$ Yes, sorry - I've edited it now. $\endgroup$– Puraṭci VinnaniNov 25, 2010 at 22:27
-
$\begingroup$ The same question here: math.stackexchange.com/questions/1046048 $\endgroup$– Anton PetruninJul 11, 2016 at 22:11
2 Answers
It is well-known problem, but quite now I am unable to find a link on AoPS. For any line $a$ take all $n-1$ points, in which it meets other lines, and for any two consecutive points $B=a\cap b$, $C=a\cap c$ consider the triangle, formed by lines $a$, $b$, $c$ and draw a flower inside this triangle near the midpoint of its side $BC$. Totally, we get $(n-2)n$ flowers. On the other hand, in any part, which is not a triangle, we have at most two flowers (because any two flowers in the same part must lie on neighbouring sides of this part). Since we have $n(n+1)/2+1$ parts (simple induction), and $2n$ of them are unbounded (common sense), we get at most $3T+2(n(n+1)/2+1-2n-T)$ flowers, hence $(n-2)n\leq n^2-3n+2+T$, $T\geq n-2$, where $T$ is the number of triangular parts.
-
$\begingroup$ Sorry I don't quite understand why "in any part which is not a triangle we have at most two flowers" - surely in any part with $n$ sides we have $n$ flowers? If we have a part with $n$ sides, how could any of those sides fail to have a flower on it? $\endgroup$ Nov 25, 2010 at 23:01
-
$\begingroup$ No, say, in regular pentagon we have 0 flowers. All flowers are in other parts. (We draw exactly one flower for each segment, on one side, not on both.) $\endgroup$ Nov 25, 2010 at 23:05
-
$\begingroup$ Nice --- I did not know this solution, do you have some refs? Did you know this one: kvant.mccme.ru/1992/11/treugolniki_i_katastrofy.htm $\endgroup$ Jul 11, 2016 at 22:03
-
1$\begingroup$ I know this moving lines solution for a longer time (Kanel likes to tell this story to schoolboys, me included). But after I learnt such a short counting argument, it looks less impressive for me. Alas, I do not know the reference. I read it on mathlinks/AoPS, but now I can not find anything on their site. $\endgroup$ Jul 11, 2016 at 23:28
-
$\begingroup$ This solution is from "Triangles in Euclidean arrangements" by Felsner and Kriegel (Thanks to Alexei Kanel for the ref.) $\endgroup$ Jul 12, 2016 at 19:36
Sorry for adding that as an answer - cannot comment yet.
Just for completeness sake want to add a very short proof that in any non-triangular part we have no more than two flowers (and if we have two, they must be adjacent).
First, side $AB$ in part $P$ is marked with a flower iff inequality $\angle A + \angle B < \pi$ holds true for internal angles $A$ and $B$ in convex polygon $P$.
Second, assuming the opposite (more than two flowers or two flowers which are not adjacent) we will immediately obtain two non-overlapping pairs of angles with sums less than $\pi$. That obviously contradicts the sum of all internal angles in an $n$-gon being equal to $(n-2)\pi$.
-
2
-
1$\begingroup$ @Joseph, maybe the word is being used in the same way as in Fedor Petrov's answer. $\endgroup$ Aug 5, 2017 at 5:21
-
$\begingroup$ Yes, I have reused Fedor's terminology. In the original article by Felsner and Kriegel (edocs.fu-berlin.de/docs/servlets/MCRFileNodeServlet/…) they use labels $\oplus$ and $\ominus$ $\endgroup$– JimTAug 5, 2017 at 15:27