\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{TSTST 2020/9}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 50}
\maketitle
\section*{Problem}
Ten million fireflies are glowing in $\mathbb{R}^3$ at midnight.
Some of the fireflies are friends, and friendship is always mutual.
Every second, one firefly moves to a new position
so that its distance from each one of its friends is the same
as it was before moving.
This is the only way that the fireflies ever change their positions.
No two fireflies may ever occupy the same point.
Initially, no two fireflies, friends or not, are more than a meter away.
Following some finite number of seconds,
all fireflies find themselves at least ten million meters
away from their original positions.
Given this information,
find the greatest possible number of friendships between the fireflies.
\section*{Video}
\href{https://www.youtube.com/watch?v=NOjZ_DKUgxc}{\texttt{https://youtu.be/NOjZ\_DKUgxc}}
\section*{External Link}
\url{https://aops.com/community/p20020206}
\newpage
\section*{Solution}
In general, we show that when $n \ge 70$,
the answer is $f(n) = \lfloor\tfrac{n^2}3\rfloor$.
\bigskip
\textbf{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:
\begin{enumerate}
\ii Reflect $\ell_A$ and all fireflies on $\ell_A$
in the plane containing $\ell_B$ and $\ell_C$.
\ii Reflect $\ell_B$ and all fireflies on $\ell_B$
in the plane containing $\ell_C$ and $\ell_A$.
\ii Reflect $\ell_C$ and all fireflies on $\ell_C$
in the plane containing $\ell_A$ and $\ell_B$.
\ii[$\vdots$]
\end{enumerate}
\bigskip
\textbf{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.
\begin{claim*}
[No coplanar $K_4$]
We can't have four coplanar fireflies
which are pairwise friends.
\end{claim*}
\begin{proof}
If we did, none of them could move
(unless three are collinear, in which case they can't move).
\end{proof}
\begin{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$.
\end{claim*}
\begin{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_1ABC$ and $E_2ABC$
are two congruent tetrahedrons with fixed shape.
We note that points $D$, $E_1$, and $E_2$ are all different:
clearly $D \neq E_1$ and $E_1 \neq 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$:
\begin{itemize}
\ii $E_1$ is the intersection of line $CD$
with the reflection of plane $ABD$ in plane $ABC$.
\ii $E_2$ is the intersection of plane $ABD$
with the reflection of line $CD$ in plane $ABC$.
\end{itemize}
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.)
\end{proof}
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)\}
\quad \forall n \ge 24. \]
By iterating the above inequality, we get
\begin{align*}
g(n) \le \max\Big\{f(n), \; (2n+10) &+ (2(n-4)+10) \\
&+ \dots + (2(n-4r)+10) + g(n-4r-4)\Big\},
\end{align*}
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.
\begin{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.
\end{remark*}
\begin{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!
\end{remark*}
\begin{remark*}
On the other hand, Ankan Bhattacharya gives the following
reasoning as to why the answer should not be that surprising:
\begin{quote}
I think the answer $(10^{14} - 1)/3$ is quite natural
if you realize that $(n/2)^2$ is probably optimal in 2D and
$\binom n2$ is optimal in super high dimensions (i.e.\ around $n$).
So going from dimension $2$ to $3$ should increase the answer
(and indeed it does).
\end{quote}
\end{remark*}
\end{document}