, 2023

The answer is $7651$; in general, for the $6n$-th turn, the maximum possible value is $3n^2 + 3n + 1$.

Let us coordinatize these lines: for a line $\ell$ passing through point $A$, label it as $(1, r)$, where
$$r = \frac{\sin \angle(AB, \ell)}{\sin \angle(\ell, AC)}.$$
Define $(2, r)$ and $(3, r)$ similarly. Note that this means:
- there exists $t > 0$ such that the initial three lines are $(1, t)$, $(2, t)$, and $(3, t)$;
- by the trigonometric form of Ceva's theorem, the three lines $(1, r_1)$, $(2, r_2)$, and $(3, r_3)$ are concurrent if and only if $r_1 r_2 r_3 = 1$, i.e., $\log_t r_1 + \log_t r_2 + \log_t r_3 = 0$;
- each time Ming selects the intersection point of $(i, r_i)$ and $(j, r_j)$, the new line he can add is $(k, r_k)$, where $k \in \{1, 2, 3\} - \{i, j\}$ and $r_k = (r_i r_j)^{-1}$, i.e., $\log_t r_k = -(\log_t r_i + \log_t r_j)$.

Combining the above, by considering the $\log_t$ version, we can reformulate the problem as the following equivalent combinatorial problem:
Let $S_1 = S_2 = S_3 = \{1\}$. Each time, Ming takes $n_i \in S_i$ and $n_j \in S_j$, and adds $-(n_i + n_j)$ to the third set. Let $S = \{(s_1, s_2, s_3) : s_i \in S_i, s_1 + s_2 + s_3 = 0\}$. Prove that after $6n$ operations, the maximum possible value of $|S|$ is $3n^2 + 3n + 1$.

Estimate: This is equivalent to proving that when $|S_i| = n_i$ and $n_1 + n_2 + n_3 = 6n + 3$ (since initially $|S_i| = 1$), we have $|S| \le 3n^2 + 3n + 1$. Let the elements of $S_1$ be $a_1 < a_2 < \dots < a_p$, the elements of $S_2$ be $b_1 < b_2 < \dots < b_q$, and the elements of $S_3$ be $c_1 < c_2 < \dots < c_r$, and without loss of generality assume $p \le q \le r$. Consider the sets
$$\begin{align*} T_1 &= \{a_1 + b_1, a_2 + b_1, \dots, a_p + b_1, a_p + b_2, \dots, a_p + b_q\}, \\ T_2 &= \{a_1 + b_2, a_2 + b_2, \dots, a_{p-1} + b_2, a_{p-1} + b_3, \dots, a_{p-1} + b_q\}, \\ \vdots \\ T_i &= \{a_1 + b_i, a_2 + b_i, \dots, a_{p+1-i} + b_i, a_{p+1-i} + b_{i+1}, \dots, a_{p+1-i} + b_q\}, \\ \vdots \end{align*}$$

Then it is easy to see that $\cup_{i=1}^p T_i = S_1 + S_2$, and any $a_k + b_\ell$ appears in exactly one $T_i$. Also,
$$|T_i \cap (-S_3)| \le |S_3| = r \quad \text{and} \quad |T_i \cap (-S_3)| \le |T_i| = p + q - 2i + 1,$$
therefore
$$|S| = \sum_{i=1}^{p} |T_i \cap (-S_3)| \le \sum_{i=1}^{p} \min(r, p+q-2i+1) := f(p, q, r),$$
a direct computation (see Remark 1) gives
$$\begin{aligned} f(p, q, r) &= \frac{1}{4}(-p^2 - q^2 - r^2 + pq + pr + qr) + \frac{1}{4} \\ &\le \frac{(p+q+r)^2}{12} + \frac{1}{4} = 3n^2 + 3n + 1 \end{aligned} \quad (1)$$

Remark 1: Derivation of the left-hand side of (1). Note that
- if $r < q-p+1$, then $f(p, q, r) = f(p, q-1, r+1)$;
- if $r > q+p-1$, then $f(p, q, r) = f(p, q+1, r-1)$.
Hence we may without loss of generality set $r \in [q-p+1, q+p-1]$, and in this case a direct computation gives
$$\begin{aligned} f(p, q, r) &= \sum_{p+q-2i+1 \le r} r + \sum_{p+q-2i+1 > r} (p+q-2i+1) \\ &= tr + (p-t)(q-t) = -t(p+q-r-t) + pq \end{aligned} \quad (3)$$

where $t = \lfloor (p+q+1-r)/2 \rfloor$. But note that
$$t(p+q-r-t) = \max_{x \in \mathbb{Z}} x(p+q-r-x) = \frac{(p+q-r)^2-1}{4} \quad (4)$$
Substituting (4) back into (3) gives the left-hand side of (1).

Remark 2: Derivation of the left-hand side of (2). Since changing $S_1$ to $(S_1+2)/3$, $S_2$ to $(S_2-1)/3$, and $S_3$ to $(S_3-1)/3$ leaves the number of tuples satisfying $s_1 + s_2 + s_3 = 0$ unchanged, we may instead consider $S_1 = S_2 = S_3 =$
$\{-n, -n+1, \cdots, n-1, n\}$, in which case
$$|S| = \sum_{k=-n}^{n} |\{s_2 + s_3 = -k : s_i \in S_i\}| = (2) \text{ left-hand side.} \quad (5)$$

$$\begin{aligned} |S| &= \sum_{k=-n}^{n} (2n+1-|k|) = (2n+1) + 2 \sum_{k=1}^{n} (2n+1-k) \\ &= (2n+1) + n \times (3n+1) = 3n^2 + 3n + 1. \end{aligned} \quad (2)$$

Construction: Consider the following strategy: we first present Ming's optimal strategy:
1. Ming first adds $-(1+1) = -2$ to all three sets;