4031 lines are drawn on a plane, no two parallel or perpendicular, and no three lines meet at a point. Determine the maximum number of acute-angled triangles that may be formed.
Problem
Source:
Tags: combinatorics
05.01.2016 00:14
Solution with Lord.of.AMC, mathtastic, ProbaBillity, ABCDE: Let $A$ be the total number of acute triangles and $O$ be the total number of obtuse triangles. Assume $2n+1$ lines are given and set $n=2015$ at the end. Number the lines $l_1, l_2, ... l_{2n+1}$. Consider any line $l_i$. Rotate the entire plane so that $l_i$ is horizontal and call $l_i$ the base line. . Once it is horizontal, define a line to be positive if it has positive slope, where we consider $l_i$ as the $x$-axis, and call it negative otherwise. Note that for a triangle determined by $l_i$ and two other lines $l_j,l_k$ to be acute, it is necessary for one of $l_j,l_k$ to be positive and the other to be negative, and this must also occur when we make $l_j, l_k$ the base lines. Thus we say an acute triangle has $3$ positive-negative pairs- one for each line we make the base line. Meanwhile, triangle $l_i,l_j,l_k$ is obtuse if it has exactly one positive-negative pair- WLOG assume $l_j,l_k$ bound the obtuse angle, and then letting $l_i$ be the base gives the pair. Finally, note that when any line $l_i$ is made the base, there are at most $n^2$ positive-negative pairs we can make with base $l_i$. This is because there are $2n$ other lines, so the number of pairs is maximized at $n$ positive and $n$ negative lines for a total of $n^2$. From all our conclusions, we may deduce that $3A+O = \text{total number of positive-negative pairs} \le n^2 (2n+1)$. But then $A+O = \binom{2n+1}{3}$, the total number of triangles, so $2A \le n^2(2n+1)-\binom{2n+1}{3}$ or $6A \le 3n^2(2n+1) - (2n+1)n(2n-1)$ so $6A \le n(2n+1)(n+1)$, or $A \le \dfrac{n(n+1)(2n+1)}{6}$. Equality occurs when every line yields exactly $n^2$ positive-negative pairs; that is, it has $n$ positive and $n$ negative lines. We may choose the $2n+1$ lines to be the sidelines of a regular $2n+1$-gon. This clearly satisfies the desired because it is symmetric, so every positive line yields a corresponding negative one. Then the maximum is $A=\dfrac{n(n+1)(2n+1)}{6}$, and we can plug in $n=2015$ to get the desired $\blacksquare$.
16.04.2016 04:26
@Yanyau I remembered that Kobe has given me a try of this question and solved it orally.
16.04.2016 06:06
$Comment$ first:we can ignore the condition to the lines because when we want to minimize the number of acute triangles,they are supposed to be non parallel.... We solve the general problem,assume there to be $2n+1$ lines. Every $3$ lines would form a triangle.Let the number of acute be $A$,the obtuse be $B$.We define "region acute" as following:If a two angles of a triangle lying on a line $l$ are acute.Call the triangle is "region acute" wrt $l$.Give each line an orientation,we know the negative orientation line and positive form a "region acute".For any directed line,the "region acute" is $n^2$.Totally are $(2n+1)n^2$.So we have $3A+B\le (2n+1)n^2$,and $A+B=\binom {2n+1}{3}$,implies $A\le \frac {n(n+1)(2n+1)}{6}$.Done!
30.05.2018 17:15
Answer is $2729148240=\frac{1}{6}\cdot 2015\cdot 2016\cdot 4031$ acute angles. I think this task requires to give construction of such case. We only showed that number of acute triangles is at most this. But we are asked about the best maximum I guess, otherwise task is too easy, as we could take ${2n+1\choose 3}$