There is an equilateral triangle $ABC$ on the plane. Three straight lines pass through $A$, $B$ and $C$, respectively, such that the intersections of these lines form an equilateral triangle inside $ABC$. On each turn, Ming chooses a two-line intersection inside $ABC$, and draws the straight line determined by the intersection and one of $A$, $B$ and $C$ of his choice. Find the maximum possible number of three-line intersections within $ABC$ after 300 turns. Proposed by usjl
Problem
Source: 2023 Taiwan TST Round 2 Mock Exam P6
Tags: Taiwan, combinatorics, geometry
CrazyInMath
09.04.2023 06:13
Does a four-line intersection count as three three-line intersection, or one, or zero? @below you're right, I'm silly
USJL
09.04.2023 07:14
CrazyInMath wrote: Does a four-line intersection count as three three-line intersection, or one, or zero? As each line passes through one of $A$, $B$ and $C$, there cannot be a point in the interior of $ABC$ that is incident to more than three lines.
Bobson
23.03.2024 06:43
The answer is 7651.
Consider Ceva's theorem. By associating each line through $A$ ($B$, $C$ respectively) with the number $\log \dfrac{BD}{DC}$, where $D$ is the intersection of the line and $BC$, the problem is equivalent to the following problem:
Let $A=B=C=\{1\}$ be three sets. In each turn Ming sum up a pair of elements from two of the sets $A$, $B$ or $C$, and append its negation to the third set. After 300 turns, what is the maximum number of triplets $(a,b,c)\in A\times B\times C:= S$ summing up to $0$?
After the first turn, say WLOG appending $-2$ to $A$, we can replace $A$, $B$ and $C$ with $\dfrac{A+2}{3}$, $\dfrac{B-1}{3}$ and $\dfrac{C-1}{3}$ respectively, so that now $A=\{0,1\}$ and $B=C=\{0\}$. The problem remains the same and there's $299$ turns left.
To reach the maximum, Ming appends the rest of all integers in $[-50,50]$ to each of $A$, $B$ and $C$ in some order that can be easily figured out. The number of triplets summing up to $0$ would be $3\cdot 50\cdot 51+1=7651$ (There are $50\cdot 51$ choices of $(a,b,c)$ such that $a\geq 0$ and $b<0$. The $3$ for the cyclic permutations, and the $1$ for the extra solution $(0,0,0)$).
To show that this achieves the maximum, assume $|A|=l+1$, $|B|=m+1$, $|C|=n+1$. Consider the equivalent poset $P=[0,l]\times [0,m]\times [0,n]\cap \mathbb Z^3$. One of the largest antichain in $P$ is $P\cap \{(a,b,c)\in \mathbb Z^3|a+b+c=\dfrac{300}{2}\}$ (This is a generalization of Sperner's theorem), and $S$ cannot exceed the size of this antichain given $l,m,n$. Note that this number is the constant term of $(x^l+x^{l-2}+...+x^{-l})$ $(x^m+x^{m-2}+...+x^{-m})$ $(x^n+x^{n-2}+...+x^{-n})$, and it reaches maximum when $l=m=n=100$ (as when $l,m$ get closer each terms get larger), and this meets our construction.