Let $a$ and $b$ be parallel lines with $50$ distinct points marked on $a$ and $50$ distinct points marked on $b$. Find the greatest possible number of acute-angled triangles all of whose vertices are marked.
Problem
Source: Sharygin Finals 2017, Problem 9.7
Tags: combinatorics, geometry
div5252
03.08.2017 16:20
Ans is $\sum x(50-x)$ Stats- 6 students solved it during the contest.
edfearay123
25.07.2021 06:58
$\dfrac{n^3-n}{3}$
Let $P_1, P_2 \dots, P_n$ the $n$ points on $a$ line, let $a_i$ the number of points on the line $b$ between $P_i$ and $P_{i+1}$ (If we overlap the lines) for all $0\leq i \leq n$, let $S_i=a_1+a_2+\dots+a_i$
Prove that the number of acute triangles are $\sum ^{n-1}_{i=0}S_i(n-S_i)+\sum ^{n-1}_{i=0}i(n-i)a_i \dots (\alpha)$
Consider $A_i$ the points between $P_i$ and $P_{i+1}$, prove that if we move one point from $A_{i+1}$ to $A_i$ (i.e the new cardinals of the sets are $a_i+1$ and $a_{i+1}-1$) then ($\alpha$) maximizes if only if $i\geq S_i$ (just replace in the formula) and note that if $i=S_i$ the number of acute triangles will be the same after the operation.
We can do the above for the other points in $b$, so it is easy to conclude that if we want that ($\alpha$) is the maximum, necessarily the points between $a$ and $b$ are interspersed with some space between two points (it is a bit rigorous to explain it, but it can be done with contradiction or induction).
Finally for the counting, we can suppose that the space between two points is in the begining. The number of acute triangles are $2\sum ^n_{i=0} i(n-i)=\dfrac{n^3-n}{3}$