Because I’m silly and didn’t set up Twitch to record our livestream, here’s roughly our thought processes for the three problems. (Solved with Eugene Lee on stream.)

Q1. Find all $f:\mathbb{Z} \rightarrow\mathbb{Z}$ such that $$f(2a)+2f(b)=f(f(a+b)).$$

Walkthrough. We tried (0,0) which was useless, then swapping $(a,b)\leftrightarrow (b,a)$. This gave us $$f(2a) - 2f(a) = \text{const. } (c)$$ Now we tried (a,a) and got $$4f(a)=f(f(2a)) - c$$ and here Eugene saw that if you do $a\rightarrow \frac{a+b}2$ you basically get a “Cauchy”-like $$f(a)+f(b) = 2f\left(\frac{a+b}{2}\right)$$ This basically forces it to be an A.P., so it remains to check solutions.

Another way to motivate the last step is to fix $a+b$ (so $RHS$ is fixed) and vary $a$.

Q2. In triangle $ABC$, point $A_1$ lies on side $BC$ and point $B_1$ lies on side $AC$. Let $P$ and $Q$ be points on segments $AA_1$ and $BB_1$, respectively, such that $PQ$ is parallel to $AB$. Let $P_1$ be a point on line $PB_1$, such that $B_1$ lies strictly between $P$ and $P_1$, and $\angle PP_1C=\angle BAC$. Similarly, let $Q_1$ be the point on line $QA_1$, such that $A_1$ lies strictly between $Q$ and $Q_1$, and $\angle CQ_1Q=\angle CBA$.

Prove that points $P,Q,P_1$, and $Q_1$ are concyclic.

Walkthrough. We noticed very early on that this problem had unusually many variable components. The first thing we tried was to extend $PB_1, PA_1$ to $X,Y$ (resp.) on $BC$, then $CP_1XA$ and $CQ_1YB$ are concyclic. Eugene was trying some gorrilla angle chasing.

Then I tried the special case where $P = Q = AA_1\cap BB_1$, and managed to prove it (basic angle chase). This is where we got stuck for a while.

This is when I decided to redraw the diagram, but with the loci of $P_1$ and $Q_1$ drawn in. These are precisely $(CB_1K)$ and $(CA_1L)$, where $K,L$ are the $P_1,Q_1$ from the special case from just now. That’s when I guessed that it could be that $(PQP_1Q_1)$ always passes through $K,L$ (fixed) as $PQ$ varies, since this seemed to be true for $PQ=AB$ and $PQ = AA_1\cap BB_1$. This falls straight out of a single angle-chase.

Q3. A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time:

• Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged.

Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Walkthrough. We both LOL-ed at this, because we were doing a very similar “construct-an-algorithm” graph problem right before this.

We started looking at obstructions to “finishing”. Most obvious was the triangle, but thinking for a little while shows that “plain” cycles were also obstructions (since they just become smaller cycles if you perform the operation on them). However, two triangles glued along an edge can be saved, and also “$K_4$ missing an edge with a hat” and two $K_4$’s glued together.

This is when we nail down the situations where no operations can be performed at all - these are precisely if the graph is disjoint $K_n$’s.

We then tried looking for other things that cannot be finished:

• two loops glued at a vertex cannot be killed
• three loops glued in various configurations cannot be killed
• … but a balloon can be killed.

That’s when we realized that the difference was that the balloon had vertices with odd degree (“odd vertices”) and the others did not. Also related was having a $K_n$ balloon: the single string could wipe out the whole thing.

Also this is when we had a big “ohhhh” moment and figured out that parity was conserved (around half an hour in).

We then figured it was important to leave odd vertices connected to even vertices, since if you have connected components with just even vertices they can’t die. Eugene proposed to just keep it connected for as long as possible and carefully disconnect the rest. So we try a greedy approach and just perform operations as long as it doesn’t disconnect the graph.

Disconnecting a graph only happens at the “apex” of the triangle we operate on, and plus vertices connected to the “feet” will stay connected. So if we find edges $PA,PB$ (and non-edge $AB$), if there’s a third edge $PC$ then $C$ is not connected to $A$ or $B$ once $P$ is removed. In particular, this means $AC,BC$ are non-edges, and we can apply the same logic to $PAC$ and $PBC$. This implies that vertices are connected to exactly one of $A,B$ or $C$. Extrapolating a bit we expect this to be some kind of tree.

There are some other cases (like cycle and clique), so we analyzed it by looking at a specific vertex $P$, which either has:

(1) all its neighbors are pairwise adjacent (2) (exists) two neighbors $A,B$ which are non-adjacent. If there’s a third neighbor $C$, then the neighbors are pairwise unconnected (except through $P$).

In particular, if there’s at least one type (1) vertex then the neighbors must all be type (1) (assuming degree at least 3), which makes a clique. Otherwise, all vertices are type (2),. so we get a cycle or a tree.

By conservation of parity, we get that it’s a tree, and with a tree you can pretty much shred it anyhow since you can never make a cycle. (This is easy to check because if you do make a cycle, reversing the step produces at least 1 cycle still.)

This is where we freaked out a bit because we realized we assumed the graph to be connected without really checking, but thankfully that’s easy.