Here's some partial progress. Replace the first occurrence of ten million with sufficiently large $n$, we claim the Turan graph on 3 parts is optimal. This is seen to be achievable by putting the fireflies on 3 parallel lines. We claim that the obvious graph is "probably $K_4$-free." If it is not, we can prove that at most $12$ other vertices are connected to 3 of the 4 vertices of the $K_4$, whence deleting the $K_4$ removes at most $6 + 2(n-4) + 12 = 2n+10$ edges, which means it suffices to show for $n = 20$ or so. EDIT: non-grid Beluhov combo? what's going on here? EDIT2: Oh... looks like these bounds actually solve the problem if you don't discard the extra edges you get at each step. If only I had realized this in test

Redacted wrong solution

I am posting the official solution from the author. In general, we show that when $n \ge 70$, the answer is $f(n) = \lfloor\tfrac{n^2}3\rfloor$. Construction: Choose three pairwise parallel lines $\ell_A$, $\ell_B$, $\ell_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: Reflect $\ell_A$ and all fireflies on $\ell_A$ in the plane containing $\ell_B$ and $\ell_C$. Reflect $\ell_B$ and all fireflies on $\ell_B$ in the plane containing $\ell_C$ and $\ell_A$. Reflect $\ell_C$ and all fireflies on $\ell_C$ in the plane containing $\ell_A$ and $\ell_B$. $\vdots$ Proof: Consider a valid configuration of fireflies. If there is no $4$-clique of friends, then by Tur\'an'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: We can't have four coplanar fireflies. Proof. If we did, none of them could move. $\blacksquare$ Claim: [Key claim] There are at most $12$ fireflies $e$ which are friends with at least three of $a$, $b$, $c$, $d$. Proof. Suppose WLOG that $e$ is friends with $a$, $b$, and $c$, and that fireflies $a$, $b$, $c$, $d$, $e$ initially occupy points $A$, $B$, $C$, $D$, $E_1$. Let $E_2$ denote the reflection of $E$ in $\triangle ABC$. Note that fireflies $a$, $b$, $c$, $d$ always form a tetrahedron congruent to $ABCD$, and that fireflies $a$, $b$, $c$, $e$ always form a tetrahedron congruent to $ABCE_1$ and $ABCE_2$. Moreover, 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 a moment when 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$. 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)$: $E_1$ is the intersection of plane $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.) $\blacksquare$ 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$, which 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)\} \quad \forall n \ge 24. \]By iterating the above inequality, we get \[ g(n) \le \max\{f(n), (2n+10) + (2(n-4)+10) + \dots + (2(n-4r)+10) + g(n-4r-4)\}, \]where $r$ satisfies $n-4r-4 < 24 \le n-4r$. Now \begin{align*} & \phantom{{} = {}} (2n+10) + (2(n-4)+10) + \dots + (2(n-4r)+10) + g(n-4r-4)\\ & = (r+1) (2n-4r+10) + g(n-4r-4)\\ & \le \left(\frac n4 - 5\right)(n+37) + \binom{24}2. \end{align*}This is less than $f(n)$ for $n \ge 70$, which concludes the solution. Remark: There are positive integers $n$ such that it is possible to do better than $f(n)$ friendships. For instance, $f(5) = 8$, whereas five fireflies $a$, $b$, $c$, $d$, and $e$ as in the proof of the Lemma ($E_1$ being the intersection point of line $CD$ with the reflection of plane $(ABD)$ in plane $(ABC)$, $E_2$ being the intersection point of plane $(ABD)$ with the reflection of line $CD$ in plane $(ABC)$, and tetrahedron $ABCD$ being sufficiently arbitrary that points $E_1$ and $E_2$ exist and points $D$, $E_1$, and $E_2$ are pairwise distinct) give a total of nine friendships. Remark: [Author comments] It is natural to approach the problem by looking at the two-dimensional version first. In two dimensions, the following arrangement suggests itself almost immediately: We distribute all fireflies as equally as possible among two parallel lines, and two fireflies are friends if and only if they are on different lines. Similarly to the three-dimensional version, this attains the greatest possible number of friendships for all sufficiently large $n$, though not for all $n$. For instance, at least one friendlier arrangements exists for $n = 4$, similarly to the above friendlier arrangement for $n = 5$ in three dimensions. This observation strongly suggests that in three dimensions we should distribute the fireflies as equally as possible among two parallel planes, and that two fireflies should be friends if and only if they are on different planes. It was a great surprise for me to discover that this arrangement does not in fact give the correct answer!

v_Enhance wrote: Claim: We can't have four coplanar fireflies. Proof. If we did, none of them could move. $\blacksquare$ What if 3 of them are collinear? EDIT: Okay, they are stuck, but this needs little bit discussion.

$\boxed{\text{Answer} = \left\lfloor \dfrac{\text{Ten Million}^2}{3} \right\rfloor}$. First-ever Nikolai non-grid combi problem (just as post $\#2$ mentions). I remember them (CMC, USEMO, snakes, Hephaestus) being square-by-square analysis, and one 50-rated Fibonacci polynomial that my TST-mate solved for three days, but this? Reminds me of the days where Geoff was sending $``\textit{geometry}"$ problems for the IMO; when he finally sended frogs (2016 P6) and tango dances (here). Not fully sure if this is correct; but hope the Motivation illuminates (at least) the answer and why tetrahedrons are sufficiently and necessarily tight. Also, extraneous information is nice on a hard problem like this. $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Two thirds in Turan's vs two fourths in secluded tetrahedrons.}$ Consider the natural graph interpretation of the problem in $G$. If $G$ has a tetrahedron with vertices $a,b,c,d$; There cannot be a vertex $e$ so that $ea,eb,ec,ed$ are all edges, and there cannot be three vertices $e,f,g$ so that $(ea,eb,ec);(fa,fb,fc);(ga,gb,gc)$ are all edges. Note that if this Claim is true (and I hope it is!), it strengthens $\#4$'s claim so that there exists $\textbf{at most eight}$ vertices which are adjacent to three of $a,b,c,d$. $\color{green} \textbf{Proof.}$ In this proof, I will heavily consider the $\textit{order of movements}$ --- meaning that instead of considering a general sense of possible $``\text{locus-es}"$ of points, I will consider those who move in a free-er way separately than those who are more rigid. Note that for a firefly to move, all of its friends must lie on one plane. Furthermore, the endpoint of its movement will be its transformation/image with respect to that plane. $\color{green} \textbf{Part Zero.}$ Here I will assert that the problem formulation is equivalent to the statement \[\begin{tabular}{p{12cm}} Ten million fireflies are in the space $\mathbb{R}^3$ --- some pairs of which are (mutual) friends, and no two may coincide at any moment. Define possible movements similarly to the problem. \\ Find the greatest possible friendships possible, given that each firefly will occupy a point different from its initial position. \end{tabular} \\ \]This is due to the fact that if each firefly moves by at least $\epsilon$ meters (this number exists, as there are finitely many fireflies), we can artificially enlarge the whole space by a factor of $\dfrac{\text{Ten Million}}{\epsilon}$ to yield a construction in the general case. So, whether a particular configuration of (fireflies, friendships, moves) satisfy the original formulation is only dependant on whether each of them leaves their initial bearing. $\color{green} \textbf{Part One: A small ordered preview.}$ Let there exist one such vertex $e$. Firstly, if $e$ is not on the planes $abc,abd,acd,bcd$ (assume they are different --- the case where all of them are equal is handled shortly after), then none of the fireflies $a,b,c,d,e$ can actually move. Secondly, if there exists four of $a,b,c,d,e$ which is on one plane (assume they are $a,b,c,d$) then none of $a,b,c,d$ can actually move. This may seem immediate, but let me elaborate; consider the sequence $S$ of firefly movements --- with each of $a,b,c,d,e$ moving at least once. So, there exists a time where one of $a,b,c,d$ finally moves ($a$), where none of the other three have. However, $a$ will have to be reflected with respect to plane $bcd$, since $b,c,d$ are all $a$'s friends, a contradiction to the assumption that $a$ moves away from its initial bearing. $\blacksquare$ $\color{green} \textbf{Part Two: The meat and potatoes of the proof.}$ Now consider the same sequence of firefly movements, and label $a,b,c$ by $1,2,3$ considering the order they appear on that sequence. We will prove that firefly $3$ will stay in its place until the end of time. Suppose otherwise, and $2$ moves first. Select a moment where firefly $1$ last moved before $2$ finally moves. So, fireflies $d,e,f,g$ will be on one plane with $2$ and $3$. Now, again, $2$ is friends with all of $1,3,d,e,f,g$ --- so they all must lie on one plane before $2$ is not rigid. Fix points $D_i,E_i,F_i,G_i$, $1 \leq i \leq 3$ to indicate the points' position before firefly $i$ moves. These definitions may seem loose as $1$ may move multiple times (so how would we determine which point is $D_1$?) but this is dismissed in the next observation: Observation. The key idea of this step is that $1$ and $2$'s bearings can be fixed regardless of their movements --- that is, when they move, we $\textbf{might as well let them stagnant!}$ A good example statement is this problem I got during my IWYMIC training (that is, IMO for lower secondary students.)

Here, we may also assume that way. As firefly $1$ are friends with the rest, whenever it moves, the start configuration and the end configuration will be congruent, so we might as well $\textbf{mark it as moved}$ and proceed as if nothing had happened. Moreover, this also can be applied to firefly $2$ and $3$, so the triangle $\triangle 123$ will stay constant throughout this $\color{green} \textbf{Second Part.}$ Observation End. After saying that, we can further WLOG that $D_1=D_2=D_3=D$, as firefly $d$ will have to lie on $D$ or $D'$ (reflection towards plane $(123)$) at all times; we might as well let it to be the former. Then, $E_1,F_1,G_1$ will lie on $(D23)$. Similarly, $E_2,F_2,G_2$ will lie on $(D13)$, $E_3,F_3,G_3$ on $(D12)$. We divide into cases here, for each firefly $e,f,g$: If $E_1=E_2=E$, then $E$ lies on $\overline{13}$, and $E_3$ or $E$'s reflection lie on $(D12)$. This possibility has one possibility of $E'$ (and also $E$): $\overline{13}$ reflected towards $(123)$ $\cap (D12)$. If $E = E_1 \ne E_2$, then $E \in (D23$ reflected on $123)$, intersected with $(D13)$. This intersection then will yield a line; Final possibility: that line belongs to the plane $D12$ (which we'd hope to be impossible --- or we can put arbitrarily many fireflies on that line.) If that happens, then $(D23)$ ref $(123) \cap (D31) \in (12D)$. Then, $\overline{1D} \in (D23)$ ref $(123)$, which is impossible. So, this final possibility yields one possible point $F$. Then, $G$ has no place left. We are done for this part. (Sorry for the unnecessarily long exposition: but I really think this yields a quite strong configuration for $n=6$, thus this is worth showcasing.) $\blacksquare$ $\blacksquare$ $\color{magenta} \rule{25cm}{2pt}$ After this, we bound the possible edges. Let $T(n)$ be the value $\left\lfloor \dfrac{n^2}{3} \right\rfloor$ --- this is the maximum of $E(G)$ if we consider $G$ to be tetrahedron-free. Let $f(n)$ be the actual maximum of $E(G)$ whether or not $G$ is tetrahedron-free. Then, the main equation is \[ f(n) = \max(T(n),f(n-4)+(6+3 \cdot 8+2(n-12))) = \max(T(n),f(n-4)+(2n+6)) \]Here, it is easy to finish (for a P9, that is) and you're free to use whatever bounding method to continue. I'll post it for completion here: Consider $f(n) \ne T(n)$. If this happens, then \[ f(n-4)+(2n+6) = \max(T(n-4)+(2n+6),f(n-8)+(2n+6)+(2n-2)) > T(n) \]However, for $n \geq 17$, \[ T(n-4)+(2n+6) = \left\lfloor \dfrac{n^2-8n+16}{3}+2n+6 \right\rfloor = \left\lfloor \dfrac{n^2-2n+34}{3} \right\rfloor \leq T(n) \]Continuing this further down into $k \leq 16$, \[ f(n) \leq f(k)+(2n+6)+(2n-2)+\ldots+ (2k+14) \]where it ends due to pattern-spotting: where $k = n-4$, the last summand will be $2n+6 = 2 \cdot k +14$. Finally, \begin{align*} f(k)+(2n+6)+(2n-2)+\ldots+ (2k+14) &= f(k) + \dfrac{(n+k+10)(n-k+4)}{4} \\ &\leq \binom{16}{2}+\dfrac{(n+23)(n-9)}{4} \end{align*}since $f(k) \leq f(16) \leq \binom{16}{2}$ and the minimum for $\dfrac{(n+k+10)(n-k+4)}{4}$ occurs when $n+k+10$ is nearest to $n-k+4$ --- which happens on $k = 13$ instead of 14,15, or 16. It is easy to see that for $n \geq 57$, \[ f(n) < \dfrac{n^2+14n+273}{4} \leq \dfrac{n^2}{3} \]which validates our bound. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$ By the way, construction is easy: just select three non-parallel planes, pick their three intersection lines and proceed according to Evan's post (the lines do not need to be parallel, but each pair of them must lie in one plane.) Here, a Turan's graph with no $K_4$ is formed if we pick $3,333,333$ fireflies on one line, $3,333,333$ fireflies on another line, and $3,333,334$ fireflies on the remaining line.

Solved with Jeffrey Chen and Kevin Wu. At most \(\frac13(10^{14}-1)\) friendships are allowed. Construction: Consider a plane \(\mathcal P\) and an equilateral triangle \(ABC\) in \(\mathcal P\), and consider the perpendicular lines \(\ell_1\), \(\ell_2\), \(\ell_3\) to \(\mathcal P\) through \(A\), \(B\), \(C\). Place \(\frac13(10^7-1)\), \(\frac13(10^7-1)\), \(\frac13(10^7+2)\) fireflies respectively on \(\ell_1\), \(\ell_2\), \(\ell_3\), and let two fireflies be friends if and only if they don't lie on the same line. Then we can repeatedly send entire lines to the respective reflections over the plane containing the other lines. Say, reflect \(\ell_1\) over \(\ell_2\ell_3\) to \(\ell_1'\), then \(\ell_2\) over \(\ell_3\ell_1'\) to \(\ell_2'\), and the resulting set of lines \(\{\ell_3,\ell_1',\ell_2'\}\) is just a translation of the original \(\{\ell_1,\ell_2,\ell_3\}\). Thus we can move the entire system of fireflies arbitrarily far away. Proof of upper bound: Let \(f(k)\) be the answer for \(4k\) fireflies, and consider the obvious graph \(G\) on the fireflies. Claim: \(G\) has no \(K_5\). Proof. Assume \(A\), \(B\), \(C\), \(D\), \(E\) are all connected to each other. Assume \(A\) is the first of these to move. On \(A\)'s turn to move, points \(B\), \(C\), \(D\), \(E\) are all coplanar. If no three of \(B\), \(C\), \(D\), \(E\) are collinear, then neither of \(B\), \(C\), \(D\), \(E\) is able to move. If, say, \(C\), \(D\), \(E\) are collinear, then neither of \(C\), \(D\), \(E\) is able to move.\qedhere \(\blacksquare\) Claim: For any \(K_3\), say \(\triangle BCD\), there are at most four points \(A_i\) such that \(A_iBCD\) is a \(K_4\). Proof. Use the triangle \(BCD\) as our reference frame. Note that the tetrahedron \(A_iBCD\) is always invariant under congruence, so the possible locations of the firefly at \(A_i\) are some point \(X_i\) and the reflection \(Y_i\) of \(X_i\) over the plane. Assuming the firefly at \(B\) moves, there is a plane \(\mathcal P_B\) not containing \(B\) but containing \(C\), \(D\), and either \(X_i\) or \(Y_i\) for each \(i\). Similarly define \(\mathcal P_C\) and \(\mathcal P_D\). Let \(\mathcal P_B'\), \(\mathcal P_C'\), \(\mathcal P_D'\) be the reflections of \(\mathcal P_B\), \(\mathcal P_C\), \(\mathcal P_D\) over \(\triangle BCD\). We are given for each \(i\) that \(X_i\) lies on either \(\mathcal P_B\) or \(\mathcal P_B'\), \(X_i\) lies on either \(\mathcal P_C\) or \(\mathcal P_C'\), and \(X_i\) lies on either \(\mathcal P_D\) or \(\mathcal P_D'\). Without loss of generality let \(X_i\) lie on \(\mathcal P_B\). For each choice of planes \(\mathcal P_B\times (\mathcal P_C\text{ or }\mathcal P_C')\times (\mathcal P_D\text{ or }\mathcal P_D')\) there is at most one common point, so there are at most four possible values of \(X_i\). Finally, we are given no two fireflies ever occupy the same point, so there is at most one firefly per pair \((X_i,Y_i)\), as otherwise neither would ever move. Thus at most four fireflies are connected to \(B\), \(C\), \(D\). \(\blacksquare\) Claim: We have \[f(k)\le\max\left\{\frac{16k^2}3,f(k-1)+8k+10\right\}.\] Proof. If \(G\) does not contain any \(K_4\), then by Tur\'an \[\#\text{edges}\le\frac{16k^2}3.\]Otherwise take a tetrahedron \(ABCD\). By the claim there are at most 3 points incident to \(B\), \(C\), \(D\). Symmetrically, there are at most 12 points incident to at least three of \(A\), \(B\), \(C\), \(D\), so we have \[\#\text{edges}\le f(k-1)+6+2(4k-4)+12=f(k-1)+8k+10.\]\(\blacksquare\) Finally, we have for some \(j\ge0\) that \begin{align*} f(k)&\le(8k+10)+\big(8(k-1)+10\big)+\cdots+\big(8(j+1)+10\big)+\frac{16j^2}3\\ &=(k-j)\big(4(k+j+1)+10\big)+\frac{16j^2}3\\ &\le\max\left\{\frac{16k^2}3,k(4k+14)\right\}\le\frac{16k^2}3, \end{align*}for \(k\ge11\), as desired.

For those not in the know, this is a reference to the amazing Owl City song of Fireflies. Claim: We can achieve $\left\lfloor \frac{n^2}{3} \right\rfloor$ friends. Proof. Split the fireflies into three groups $a$, $b$, $c$. Then place these three groups into parallel lines, and connect those in distinct groups. We can then reflect all fireflies in one group over the plane formed by the other planes. By repeating this, we can repeatedly decrease the $x$ coordinate of all three groups as desired. Then we have $ab + bc + ca$ total connections which smoothes out at a maximum of $\left\lfloor \frac{n^2}{3} \right\rfloor$. $\blacksquare$ Define $m(X)$ as the answer for a certain $X$. Claim: Given a $K_4$ clique of fireflies, there are at most $12$ fireflies that are friends with at least $3$ of the fireflies in the clique. Proof. WLOG let the fireflies be $f_1, f_2, f_3, f_4$. Let $g$ be friends with $f_1, f_2, \dots, f_3$ and let $P_{ijk}$ be the plane through $f_i, f_j, f_k$. Then $g$ and $g$'s reflection over $P_{123}$ must together lie in all of $P_{124}, P_{134}, P_{234}$. However, this forces either $g$ or its reflection to lie on an edge from $f_4$. There's at most $6$ ways to choose this, and since fireflies can't share the opposition at most $3$ can be in use. Since there's $4$ ways to choose the friends, the result follows. $\blacksquare$ Claim: $m(X) \le \max\left\{m(X-4) + 2n + 40, \left\lfloor \frac{n^2}{3} \right\rfloor \right\}$. Proof. Suppose that $m(X) > \left\lfloor \frac{n^2}{3} \right\rfloor$. By Turan's theorem we get a $K_4$ subclique. At most $12$ fireflies are friends with at least $3$ of the clique. As such, this subclique adds at most $4 \cdot 12 + 2 \cdot (n - 4 - 12) = 2n + 16$ to the result after deleting the subclique. $\blacksquare$ Then, for sufficiently large $n \ge 200$, it follows that $\left\lfloor \frac{n^2}{3} \right\rfloor - m(X - 4) \ge 2n + 40$, meaning that $m(X) \le \left\lfloor \frac{n^2}{3} \right\rfloor$, giving the result.

The answer is $\frac{10^{14} - 1}{3}$. Construction: Take three distinct non-coplanar pairwise parallel lines. On the first two lines, place $\frac{10^7 - 1}{3}$ fireflies and on the third line place $\frac{10^7+1}{3}$ fireflies, and let two fireflies be friends if they are on different lines, resulting in $\frac{10^{14}-1}{3}$ friendships. Each time, we can reflect all fireflies on a line over the plane determined by the other two lines, so we can move all the fireflies ten million meters away from their original positions. Bound: Take the obvious graph interpretation and denote the graph as $G$, and let $f(n)$ denote the answer for $n$ fireflies. Any vertex with degree $\geq 3$ can only move if all its neighbors are coplanar, in which case it can be reflected over the plane determined by its neighbors. Claim: $G$ does not contain a $K_5$ subgraph. Proof. Suppose otherwise and let its vertices be $A$, $B$, $C$, $D$, and $E$. WLOG, suppose $A$ moves first, so $B$, $C$, $D$, and $E$ are coplanar. Then suppose $B$ moves next, so $A$, $C$, $D$, and $E$ are coplanar. But then the vertices are all coplanar and they do not move, contradiction. $\square$ If $G$ does not contain a $K_4$ subgraph, then from Turan's theorem the maximum number of edges is $\left \lfloor \frac{n^2}{3} \right \rfloor$. Otherwise, suppose $G$ contains a $K_4$ subgraph $G'$. Claim: There are at most $12$ other vertices connected to $3$ vertices in $G'$. Proof. Let the vertices of $G$ be $A$, $B$, $C$, and $D$, and let $E$ be a vertex connected to $A$, $B$, and $C$. Let $E'$ denote the reflection of $E$ about $ABC$. $A$, $B$, $C$, and $D$ can only be moved when $E$ is coplanar with the other three vertices, so moving $A$, $B$, $C$, or $D$ does not change the location of $E$ and $E'$ with respect to $ABCD$. For all of $A$, $B$, $C$ and $D$ to be able to move, planes $ABC$, $ABD$, and $ACD$ must contain either $E$ or $E'$, so one of $E$ and $E'$ must lie on $AB$, $AC$, or $AD$. WLOG, suppose $E$ lies on $AB$. Then $E'$ must be coplanar with $ACD$, so $E'$ is the point where line $AB$ intersects plane $ACD$, and there is only one possible position for $E$. $E$ and $E'$ cannot both be vertices, so there are at most $3$ vertices connected to $A$, $B$, and $C$. Therefore, there are at most $12$ vertices connected to $3$ vertices in $G'$. $\square$ We can delete $G'$ and induct to get $$f(n) = \max \left \{ \left \lfloor \frac{n^2}{3} \right \rfloor, f(n-4) + 2n + 10 \right \}$$for $n \geq 16.$ For $n \geq 24$, $\frac{n^2 - (n-4)^2}{3} > 2n+10$. We can compute $f(4) = 6, f(8) \leq 24, \dots , f(32) \leq 344$, then $f(32) + 74 \leq 418 \leq \frac{36^2}{3} = 432$, so $f(n) \leq \left \lfloor \frac{n^2}{3} \right \rfloor$ for all multiples of $4$ greater than or equal to $36$. Therefore, $f(10^7) \leq \left \lfloor \frac{10^{14}}{3} \right \rfloor = \frac{10^{14}-1}{3}$.

This seems tighter than the other bounds on this thread, so I'm not sure if it's right. Posting anyway. (If someone finds an error, please let me know!) Let $K'$ be the graph formed by removing one of the edges from a $K_5$. We claim that the graph has no copies of $K'$. Note that $K'$ is just a $K_4$ (call the vertices A,B,C,D) with another vertex E connected to three of A,B,C,D (WLOG A,B,C). FTSOC assume that $K'$ exists. As mentioned earlier in the thread, no three of A,B,C,D can be collinear because then none of those three can move (by the Triangle Inequality, the only possible new position would be the original position for any one of these three points, rendering them all unable to move). If A,B,C,D are coplanar, then whichever one of these moves first would force the remaining 3 to be collinear, contradicting the above. Analogously, A,B,C,E are not coplanar. Note that, at any point, if one of A,B,C moves, then it must be a reflection over the plane through the remaining 4 points. This means that such a move would make the new 3D figure formed by the 5 points immediately after the move congruent (with respective points matching) to the one immediately before the move. Consequently, the only moves that change the shape are reflecting D and E over the plane ABC. Let the two positions for D be $D_1$ and $D_2$ (reflections over ABC), and let $E_1$ and $E_2$ be the two positions for E. We know that $ABCD_1E_2$ and $ABCD_2E_1$ are congruent, furthermore, $ABCD_1E_1$ and $ABCD_2E_2$ are also congruent (the elements of a pair are mirror images of each other). Thus, we only need to consider $ABCD_1E_1$ and $ABCD_1E_2$ in what follows. We claim at least one of A,B,C cannot move. Consider either one of these two figures (WLOG $ABCD_1E_1$). Now, note that at most one of the following can be coplanar: $ABD_1E_1$, $BCD_1E_1$, $CAD_1E_1$. If $\geq 2$ of these were coplanar, then $ABCD_1E_1$ would lie on a plane, contradicting what we established earlier. Thus, when $ABCDE$ is in the $ABCD_1E_1$ "state", at most one of $A,B,C$ can move (such a move does not change the "state", as the new figure is congruent to the old one). Analogously, at most one of $A,B,C$ can move in the $ABCD_1E_2$ state. Since there are only two distinct noncongruent states for this figure, this means that by Pigeonhole, at least one of $A,B,C$ cannot move, contradiction. Thus, the graph contains no copies of $K'$. We can now proceed as above. Namely, if the graph contains a $K_4$, then all other elements are each adjacent to at most 2 vertices of this $K_4$. If the graph currently has $N$ vertices, then deleting this $K_4$ alongside all edges connecting it to other elements removes 4 vertices and at most $6+2(N-4)=2N-2$ edges, allowing us to proceed with the same bounding + Turan approach.