USA TSTST

Construction: Choose three pairwise parallel lines $l_A,l_B,l_C$ forming an infinite equilateral triangle prism (with side larger than 1). Split the $n$ fireflies among the lines as equally as possible, and say that two fireflies are friends iff they lie on different lines. To see this works: 1. Reflect $l_A$ and all fireflies on $l_A$ in the plane containing $l_B$ and $l_C$. 2. Reflect $l_B$ and all fireflies on $l_B$ in the plane containing $l_C$ and $l_A$. 3. Reflect $l_C$ and all fireflies on $l_C$ in the plane containing $l_A$ and $l_B$. ...

Proof: Consider a valid configuration of fireflies. If there is no 4-clique of friends, then by Turán's theorem, there are at most $f(n)$ pairs of friends. Let $g(n)$ be the answer, given that there exist four pairwise friends (say $a,b,c,d$). Note that for a firefly to move, all its friends must be coplanar.

Claim (No coplanar $K_4$) — We can't have four coplanar fireflies which are pairwise friends. Proof. If we did, none of them could move (unless three are collinear, in which case they can't move). □

Claim (Key claim — tetrahedrons don't share faces often) — There are at most 12 fireflies $e$ which are friends with at least three of $a,b,c,d$. Proof. First denote by $A,B,C,D$ the locations of fireflies $a,b,c,d$. These four positions change over time as fireflies move, but the tetrahedron $ABCD$ always has a fixed shape, and we will take this tetrahedron as our reference frame for the remainder of the proof. WLOG, will assume that $e$ is friends with $a,b,c$. Then $e$ will always be located at one of two points $E_1$ and $E_2$ relative to $ABC$, such that $E_{1}ABC$ and $E_{2}ABC$ are two congruent tetrahedrons with fixed shape. We note that points $D,E_1$, and $E_2$ are all different: clearly $D\ne E_1$ and $E_1\ne E_2$. (If $D=E_2$, then some fireflies won't be able to move.) Consider the moment where firefly $a$ moves. Its friends must be coplanar at that time, so one of $E_1,E_2$ lies in plane $BCD$. Similar reasoning holds for planes $ACD$ and $ABD$. So, WLOG $E_1$ lies on both planes $BCD$ and $ACD$. Then $E_1$ lies on line $CD$, and $E_2$ lies in plane $ABD$. This uniquely determines $(E_1,E_2)$ relative to $ABCD$:

$E_1$ is the intersection of line $CD$ with the reflection of plane $ABD$ in plane $ABC$. $E_2$ is the intersection of plane $ABD$ with the reflection of line $CD$ in plane $ABC$. Accounting for WLOGs, there are at most 12 possibilities for the set $\{E_1,E_2\}$, and thus at most 12 possibilities for $E$. (It's not possible for both elements of one pair $\{E_1,E_2\}$ to be occupied, because then they couldn't move.) □ Thus, the number of friendships involving exactly one of $a,b,c,d$ is at most $(n-16)\cdot 2+12\cdot 3=2n+4$, so removing these four fireflies gives $$g(n)\le 6+(2n+4)+\max \{f(n-4),g(n-4)\}.$$ The rest of the solution is bounding. When $n\ge 24$, we have $(2n+10)+f(n-4)\le f(n)$, so $$g(n)\le \max \{f(n),(2n+10)+g(n-4)\}\forall n\ge 24.$$ By iterating the above inequality, we get $$\begin{gathered} g(n)\le \max \{f(n),(2n+10)+(2(n-4)+10) \\ +\cdots +(2(n-4r)+10)+g(n-4r-4)\}, \end{gathered}$$ where $r$ satisfies $n-4r-4<24\le n-4r$. Now $$\begin{array}{rl}& (2n+10)+(2(n-4)+10)+\cdots +(2(n-4r)+10)+g(n-4r-4)\\ & =(r+1)(2n-4r+10)+g(n-4r-4)\\ & \le \left(\frac{n}{4}-5\right)(n+37)+\left(\genfrac{}{}{0ex}{}{24}{2}\right).\end{array}$$ This is less than $f(n)$ for $n\ge 70$, which concludes the solution.