Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

We'll mimic the cloning proof of Turán's theorem to show that the optimal graph WLOG consists of $r$ pairwise disconnected complete graphs for some $r\ge 1$ (i.e. its complement is a complete $r$-partite graph for some $r$). Let $f(x)$ denote the number of weak quartets containing vertex $x$ (let $F(G)$ denote the number of weak quartets in $G$). It suffices to show that we can modify $G$ so that connectivity is transitive while not decreasing $F(G)$.

First note that if $f(u)<f(v)$ for any edge $uv$, then replacing $u$ with a clone $v'$ of $v$ (with $v'$ and $v$ connected and having the same neighborhood) yields $F(G')-F(G) \ge f(v)-f(u)>0$. Indeed, if $uv$ was in a weak quartet in $G$, the corresponding one with $v'v$ instead is in $G'$ (and there are possibly still more with $v'v$), and the remaining quartets containing at most one of $u,v$ contribute to the difference $f(v)-f(u)$. In particular, for any optimal graph $G$, $f$ must be constant over any fixed connected component, and furthermore, if we replace $v$ with a clone $u'$ of $u$ for any edge $uv$, $F$ will remain constant (since it cannot decrease). Now fix a vertex $u$ and consider its neighbors $v_1,v_2,\ldots,v_m$. If we clone $u$ to $v_1,\ldots,v_m$ in that order, then $\{u,v_1,\ldots,v_m\}$ will become a connected component of the new graph $G'$ (more precisely, a $K_{m+1}$ connected to no other vertices). But cloning only preserves or reduces components, so we can repeat this procedure to get $G$ in the desired form. Suppose our $r$ maximal complete graphs have sizes $a_1,\ldots,a_r$ with $a_1+\cdots+a_r=120$; then \[F(G)=\sum_{1\le i<j<k\le r}\sum_{\text{cyc}}\binom{a_i}{2}a_ja_k=\sum_{1\le i<j<k\le r}\frac{a_ia_ja_k(a_i+a_j+a_k-3)}{2}.\]If we fix all the $a_i\ge 0$ except for $a_u$ and $a_v$, then $a_u+a_v$ is fixed, so because $F(G)$ is symmetric in $a_u$ and $a_v$ and essentially linear in $a_ua_v$, $F(G)$ increases either if $a_ua_v=0$ or $a_u,a_v$ are as close as possible to each other. Hence we can repeatedly smooth things to zero (note that this essentially reduces $r$ to the $r-1$ case) and when it's optimal to do so, smooth one of the nonzero minimum and maximum to the average of the $a_i$ until they are all equal (note that we can only smooth finitely many things to zero), so if WLOG none of the $a_i$ need to be zero in this process for some $r$, then \begin{align*} F(G)\le \binom{r}{3}\frac{(120/r)^3(360/r-3)}{2} &=120^3(1-1/r)(1-2/r)(120/r-1) \\ &\le120^3(276/25)=4769280, \end{align*}with equality at $r=5$ and $a_1=\cdots=a_5=24$. Edit. Whoops, doing math late is rarely a good idea. Thanks; I think it's fixed now.

I don't quite understand this step: math154 wrote: Otherwise, if $f(u)\ge f(v)$, then replacing $v$ with a clone $u'$ of $u$ (again, with $u'$ and $u$ connected and having the same neighborhood) yields $F(G')-F(G)=f(u)-f(v)\ge0$ (analogous reasoning to the previous case). We're not strictly increasing the number of weak quartets, just not decreasing the number. But it's not clear to me that we're actually making any progress towards being a graph of the required form (i.e. that the component containing $u, v, w$ is complete). We no longer have a problem that $uv, uw$ are edges but $vw$ not, but mightn't we have messed things up elsewhere? For example if there is some other pair of vertices $a, b$ such that $a \sim b, b \sim v, a \sim v$ and yet $b \sim u$ but not $a \sim u$? Sorry if I'm being dense, but I can't see how to prove that this can't cause us problems...

orl wrote: Among a group of 120 people, some pairs are friends. A weak quartet is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets ? Let $a_{G}$ denote the number of weak quartets in a graph $G$ and let $\mathcal{G}$ be the graph with maximal number of quartets. Now we shall define an interchange of vertices $(u,v)$ w.r.t $(G,u)$ as the graph $\mathcal{G}’$ in which $ut \in \mathcal{G}’$ if and only if $t$ is a neighbour of $v$ in $G$ leaving the others undisturbed. Claim 1: Let $K, L$ be the interchange of $(u,v)$ w.r.t $(G,u)$ and $(G,v)$. Then we have $2.a_G \leq a_K + a_L$ Proof. We shall only focus on the number of weak quartets containing $u$ and $v$. Note that $K, L$ both individually have more weak quartets with both $(v,u)$ than $G$. Also note that number of weak quartets with exactly one of $u,v$ in $K$ is twice that containing only $u$ in $G$. Similar result holds true for $L$. Combining these gives us the desired result. $\square$ Claim 2: $\mathcal{G}$ is the disjoint union of complete graphs. Proof. We shall show that for adjacent vertices $u, v$ in $\mathcal{G}$, they have the same number of neighbours. Let $K, L$ be the interchange of $(u,v)$ w.r.t $(\mathcal{G},u)$ and $(\mathcal{G},v)$. Note that $2.a_{\mathcal{G}} \leq a_{K} + a_{L}$ from Claim 1. Due to the extremely condition, we have $2.a_{\mathcal{G}} = a_K = a_L$. Repeat the same operation to different sets of vertices to obtain the desired result. $\square$ Let our $t$ complete graphs have sizes $x_1, x_2, x_3, ..., x_t$. Note that $\sum{x_i} = 120$. Note that $a_{\mathcal{G}} = \sum{ \tbinom{x_i}{2} \cdot \sum{x_j.x_k}}$ which is linear in $x_1, x_2$ fixing the others. So we need the $x_i$‘s to be as close as possible. So, we can get the maximal value only if $x _1 = x_2 = x_3 = ... = x_t = \tfrac{120}{t}$ in which case $a_{\mathcal{G}} = \tfrac{120^2}{t} \cdot \tbinom{120/t}{2} \cdot \tbinom{t-1}{2} \leq 4769280$ $\blacksquare$

Outline of solution, from Twitch Solves ISL: The answer is $4769280$ achieved when the graph $G$ is five disjoint copies of $K_{24}$. The following claim reduces the problem to an annoying (but routine) calculation: Claim: The optimum is achieved when $G$ consists of the disjoint union of several cliques. Proof. The proof goes by Zykov symmetrization. Assume that $G$ is chosen so the number of weak quartets is maximized. Throughout the process, we annotate every vertex $v$ of $G$ with the number of weak quartets that $G$ is in, say $n(v)$. Now the main observation is that: if $n(v) \ge n(v')$, then deleting $v'$ and replacing it with a clone of $v$ changes the number of weak quartets in the graph by $n(v) - n(v')$. Indeed, Any weak quartet that involved $v'$ but not $v$ is destroyed; Any weak quartet that involved $v$ but not $v'$ is cloned; Any weak quartet that involved both $v$ and $v'$ is unaffected (as is any weak quartet which involved neither). Since $G$ was picked maximally, that means in fact $n(v) = n(v')$ for any $v$ and $v'$ in the same connected component of $G$. Hence we can do the cloning operation between any pair of adjacent vertices $v$ and $v'$, with no change to the number of weak quartets. Moreover, doing so won't change $n(w)$ for any other vertices $w$ which remain in the same connected component as the cloned $v$. After all, if it did, then we could perform the operation in a way that strictly increases the number of weak quartets, contradicting again the maximality of $G$. So, for each component $C$ of $G$, we pick any vertex $v$ and clone it everywhere. This could break off $C$ into multiple components, which is okay; we then handle those components by the same procedure later on. Repeating this procedure several times we eventually arrive at $G$ a disjoint union of cliques. $\blacksquare$ The rest of the calculation is only outlined below. If $G$ has cliques of size $a_1$, \dots, $a_n$ then the number of weak quartets is exactly \[ \sum_1^n \binom{a_i}{2} \sum_{\substack{1 \le j < k \le n \\ j,k \ne i}} a_j a_k \]and a calculation shows we want these to be as close as equal as possible. Up to integer rounding issues, this means we have \[ n \cdot \binom{120/n}{2} \binom{n-1}{2} \cdot \left( \frac{120}{n} \right)^2 \]which turns out to be maximal at $n=5$ giving the answer earlier.

ZYKOV SYMMETRIZATION The answer is $4769280=120\cdot23\cdot96\cdot72/4$, achieved by five disjoint $K_{24}$'s. Let $q(\bullet)$ denote the number of weak quartets $\bullet$ belongs to. The key idea is that if two vertices $v$ and $w$ are connected by an edge and $q(v)\geq q(w)$, then we can delete $w$ and replace it with a copy of $v$ without decreasing the number of weak quartets, and equality can only hold when $q(v)=q(w)$. We only have to consider the weak quartets which contained either $v$ or $w$ (possibly both) post-replacement: If a weak quartet contains both $v$ and $w$, then the other $2$ vertices must not be connected to each other, nor to $v$ or $w$. But since any vertex not adjacent to $v$ and $w$ pre-replacement is not adjacent to $v$ and $w$ post-replacement, so the number of such weak quartets doesn't ever decrease, If a weak quartet contains $v$ and not $w$, then it still exists, and a copy of it is created post-transformation, If a weak quartet contains $w$ and not $v$, then it is deleted. Therefore, the number of weak quartets increases by at least $q(v)-q(w) \geq 0$, with equality holding only when $q(v)=q(w)$ (this is a necessary but not sufficient condition). Therefore, if we consider some graph with an optimal number of weak quartets, any two vertices connected by an edge must belong to the same number of weak quartets. Find a connected component which is not a complete graph, and within it find a vertex $v$ adjacent to the largest complete graph contained inside the connected component but not part of it; also let $w$ be a vertex in this maximal complete graph that $v$ is adjacent to. Then $q(w) \geq q(v)$, so delete $v$ and replace it with $w$, which won't decrease the number of weak quartets. Repeat this until every connected component is a complete graph. Now suppose that we have $n$ complete graphs with sizes $a_1,\ldots,a_n$, so $a_1+\cdots+a_n=120$. The total number of weak quartets is clearly $$\frac{1}{2}\sum_{\substack{1 \leq i,j,k \leq n\\i,j,k\text{ distinct}}} \binom{a_i}{2}a_ja_k=\sum_{1 \leq i<j<k \leq n} \sum_{\mathrm{cyc}} \binom{a_i}{2}a_ja_k=\sum_{1 \leq i<j<k \leq n}\sum_{\mathrm{cyc}} \frac{1}{2}a_ia_ja_k(a_i+a_j+a_k-3).$$We will actually maximize this when $a_i$ is a nonnegative real. If we pick some $i \neq j$ and fix all the variables other than $a_i$ and $a_j$, so $a_i+a_j$ is fixed, then the above expression is actually linear in $a_ia_j$, since both $a_ia_j(a_i+a_j)$ and $a_i^2+a_j^2=(a_i+a_j)^2-2a_ia_j$ are linear in $a_ia_j$ when $a_i+a_j$ is fixed. Therefore, its maximum occurs when $a_ia_j$ is either minimized or maximized, i.e. either one of $a_i$ and $a_j$ is $0$, or $a_i=a_j$. Therefore, when the above expression is maximized, some of the $a_i$ terms are zero, and the rest are all equal. On the other hand, if one of the $a_i$ equals zero, we can delete it and reduce to the $n-1$ case, so assume that all the variables are equal to $\tfrac{120}{n}$, and therefore this quantity is at most $$\frac{1}{2}\binom{n}{3}\left(\frac{120}{n}\right)^3\left(\frac{360}{n}-3\right)=120^3\left(\frac{120}{n}-1\right)\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right).$$This is maximal when $n=5$, in which case it equals $4769280$ (to prove this, for most $n$ we can replace $120/n-1$ with $120/n$ and get a fairly simple quadratic in $n$, and finite case check the rest). $\blacksquare$

Let the people be $P_1, P_2,\dots, P_{120}$, and let $P_i$ be involved with $c_i$ weak quartets. Then, the total number weak quartets is equal to $S=\tfrac{c_1+c_2+\dots+c_{120}}{4}$. Suppose $c_i\ge c_j$ for friends $P_i$ and $P_j$. Then, we can take $P_j$, unfriend them with everyone except $P_i$, and make them friends with everyone who is friends with $P_i$. Thus, $c_j$ becomes exactly equal to $c_i$, since every weak quartet involving $P_i$ is in corresponds with one $P_j$ is in. Thus, we can make every pair of friends have the same friends, without making $S$ less. For the sake definition, we say that everyone is their own friend, but this doesn't count towards the weak quartet definition. $~$ Consider any connected component. Since it has a spanning tree, every person in this connected components has the same set of friends. Since the union of all friends of everyone in this spanning tree is the entire connected component, every person must be friends with everyone in the connected component. Thus, there is a case when $S$ is maximal such that all the friends form cliques. Let the cliques be sized $a_1,a_2,a_3,\dots,a_k$. Then, to make a weak quartet we must find two people from the same clique, and two from different ones, so \[S=\sum_{i=1}^{k}{\binom{a_i}{2}\sum_{j_1\neq j_2\in \{1,2,\dots,k\}\setminus \{1\}}a_{j_1}a_{j_2}}\]Since the sum of the $a_i$ is fixed, $S$ is maximized when the $a_i$ are as close to each other as possible. Thus, \[S\le \binom{\frac{120}{k}}{2} \binom{k-1}{2} \frac{14400}{k} \]and it can be seen that $k=5$ makes this biggest, with $\binom{24}{2}\cdot 6 \cdot \frac{14400}{5}=4769280$ weak quartets

Zykov Symmetrization OP! The idea is to take the maximal configuration $\mathcal{G}$ and prove that $f(v) = f(v')$ where $f$ is the number of weak quartets via Zykov symmetrization, indeed if $f(v)>f(v')$ then the number of weak quartets increase (take cases). So, $\mathcal{G}$ is disjoint union of cliques. Now rest is calculation, let $\mathcal{G}$ have cliques of sizes $a_1,a_2 \cdots a_n$ then the number of weak quartets are: $$\sum_{1}^{n} \binom{a_i}{2} \sum_{1\leq j,k \leq n, j,k \neq i} a_ja_k$$since this is a linear function of $x_1,x_2$ so we must take $x_i$ as close as possible so $$\sum_{1}^{n} \binom{a_i}{2} \sum_{1\leq j,k \leq n, j,k \neq i} a_ja_k = \frac{120^2}{n}\binom{\frac{120}{n}}{2}\binom{n-1}{2}$$which is maximised at $n=5$. Hence we're done