Consider the graph with two people joined iff they are friends. For each person $X$, let $A(X)$ be the set of its friends and $B(X)$ the set of its foes. Note that any edge goes either: from $X$ to $A(X)$ (type 1), from $A(X)$ to $B(X)$ (type 2) or from a point of $B(X)$ to another (type 3), but there's no edge joining two points of $A(X)$ (since they would form a triangle with $X$). Let the number of type 1, type 2, type 3 edges of $X$ be $x_1, x_2, x_3$ respectively, so that $x_1$ is the degree of $X$ and we want to show that for some $X$, we have $x_3 \leq q(1-4q/n^2)$. Since each edge is of one of those types, we have $x_1+x_2+x_3=q$. Thus \[ x_3 \leq q(1-4q/n^2) \Longleftrightarrow \\ x_3 \leq q-4q^2/n^2 \Longleftrightarrow \\ q-x_1-x_2 \leq q-4q^2/n^2 \Longleftrightarrow \\ x_1+x_2 \geq 4q^2/n^2. \] That is, what we want is equivalent to proving that for some vertex $X$, the set of edges touching either $X$ or a vertex joined to $X$ is at least $4q^2/n^2$. Obviously now we'll sum $x_1+x_2$ over all vertices $X$. In the resulting sum, an edge joining $X, Y$ is counted once for each edge that $X, Y$ have, that is, it is counted $D(X)+D(Y)$ times, where $D(X)=x_1$ is the degree of $X$. Thus each vertex $X$ contributes to the overall sum with $D(X)$ for each edge it has, and since it has $D(X)$ edges, it contributes with $D(X)^2$. Thus the considered sum is equal to \[ \sum_{X \in G} D(X)^2 \geq \frac{(\sum_{X \in G} D(X))^2}{n}=\frac{(2q)^2}{n}=4q^2/n. \] (That's Cauchy.) Since we are summing over $n$ vertices, one of the summands is at least $4q^2/n^2$ by pigeonhole, which is what we wanted to prove.

Hmm, a less trickier way for less tricky people. Call $q = E$ and $n = V$ for convenience. The graph is $3$-free if we look at the graph $G$ made by friend relationships, and let people be the edges. Instead of looking at the subgraph induced by eliminating $A$'s friends, we do something a bit different. Instead, look at each edge, and consider say, edge ${u, v}$. We ask, how many times does a given edge have a vertex which is not connected to either? Clearly, if we sum up all of these, we will be able to finish. This is normally a very difficult task, but observe that the graph is $3$-free, so the vertices that $u$ is adjacent to are disjoint from those adjacent to $v$. Hence, there are $D(u) - 1 + D(v) - 1 = D(u) + D(v) - 2$ vertices adjacent to one of them (which are not $u$ or $v$), so there are $(V-2) - D(u) - D(v) + 2 = V - D(u) - D(v)$ vertices adjacent to neither $u$ nor $v$. We can sum all of these up over all edges, and then note that in order to finish, we will need less than $VE - 4E^2/V$ edges so that piegonhole suffices. Note that $\sum_{X\in V}D(X) = 2E$. \[ \sum_{{u, v}\in E}V - D(u) - D(v)=EV-\sum_{{u, v}\in E}D(u) + D(v)=EV - \sum_{u \in V} D(u)^2 \le EV - \frac{4E^2}{V} \], (where the last step is Cauchy and $\sum_{X\in V}D(X) = 2E$.) so we are done.

Suppose that it is not possible. Create a graph to represent the scenario and label vertices $v_1,v_2,...,v_n$. Let $d_i$ be the degree of vertex $v_i$ and let $f(v_i)$ be the number of amicable pairs among the foes of $v_i$. Let's call a group of three vertices with one edge between them a "1-triplet" and with two edges between them a "2-triplet". Consider the sum $\sum_{i=1}^{n} d_i(d_i-1)+f(v_i)$. This counts all edges among the foes of $v_i$ each of which is used to make a 1-triplet with $v_i$ once, and the $d_i(d_i-1)$ term counts the number of 2-triples with $v_i$ adjacent to both edges twice. However, if we consider some edge $v_1v_2$ and one of the vertices $v_3,v_4,...,v_n$ then each vertex along with this edge either makes a 1-triplet or a 2-triplet, and 1-triplets are counted once while 2-triplets are counted twice as in the above sum. Hence $\sum_{i=1}^{n} d_i(d_i-1)+f(v_i)=q(n-2)$. On the other hand $f(v_i)>q(1 - 4q/n^2)$. Therefore $q(n-2)=\sum_{i=1}^{n} d_i(d_i-1)+f(v_i)>nq-4q^2/n+4q^2/n-2q=q(n-2)$ contradiction, hence there must be some vertex $v_i$ such that $f(v_i)\leq (1 - 4q/n^2)$.

Let $V(x)$ be the set of vertices connected to $x$, and let $V$ be the set of all vertices. If the result were false, then $$k - \sum_{v \in V(x)} d(v) > k (1 - \frac{4k}{n^2})$$for each $x \in V$. Thus by counting in two ways the number of triples $(A, B, C)$ where $A, C$ (not necessarily distinct) are both connected to $B$, we find that $$nk (1 - \frac{4k}{n^2}) < \sum_{x \in V} (k - \sum_{v \in V(x)} d(v)) = nk - \sum_{x \in V, v \in V(x)} d(v) = nk - \sum_{v \in V} d(v)^2 \le nk - \frac{4k^2}{n}$$by Cauchy-Schwarz, contradiction. Thus the result is true.

Nice and easy!And my first USAMO too Here's my solution Rephrase the problem in graph theoric terms USAMO 1995 Rephrased wrote: Consider a $3$free-graph $G$ with $n$ vertices and $q$ edges.Connect two edges if they are amicable.Prove that there is atleast one vertice $S$ such that the number of edges $e$ between $v$ and $w$ $v,w \in G/N[S]$ is atmost $q\left(1-\dfrac{4q}{n^2}\right)$ $\mathbf{Solution:}$ Assume the contrary that there is no such vertice $S$ satisfying the problem conditions.Then for any vertice $S$ the number of edges in $G/N[S]$ will be $q-d(S)$ but we have included the edges originating from the $N(S)$ also thus we have to subtract $d(S_i)-1 $$\forall S_i \in N(S)$.Note that the graph is $3$-free sotheir is no edge between two vertices $\in N(S)$, $\therefore$ The number of edges will be $q-d(S)-(\sum_{S_i \in N(S)}d(S_i)-1)=q-(\sum_{S_i \in N(S)}d(S_i)) > \left(q-\dfrac{4q^2}{n^2}\right) \implies \dfrac{4q^2}{n^2} > \sum_{S_i \in N(S)}d(S_i)$.Doing this for all the edges we get $$\dfrac{4q^2}{n}=n\cdot\left(\dfrac{4q^2}{n^2}\right)>\sum_{S\in G}\sum_{S_i\in N(S)}d(S_i)=\sum_{S\in G}d(S)^2 \ge \dfrac{(\sum_{S\in G}d(S))^2}{n}=\dfrac{4q^2}{n}$$A contradiction !! Hence our assumption is wrong and thus $\exists$ a member whose foes include atmost $q\left(1-\dfrac{4q}{n^2}\right)$ amicable pairs so we are done.$\blacksquare$ NOTE-$N[S]$ represents the closed neighbourhood of $S$ i.e. the set of vertices sharing an edge to $S$ and also including $S$ and $N(S)=N[S]/S$

I am confused about sabbasi's solution. When he says $\sum_{i=1}^{n} d_i(d_i-1)+f(v_i)$ Quote: counts all the edges among the foes of $v_i$ each of which is used to make a 1-triplet with $v_i$ once he is counting the number of edges in the spanning subgraph of the overall graph, consisting only of the foes of $v_i$. If this is the case, then shouldn't the number of edges among the foes of $v_i$ be $\sum_{i=1}^{n} d_i(d_i-1)-f(v_i)$ since two vertices are connected by an edge if they are enemies. Please correct me if I misunderstood something. Note: I think I am misunderstanding what edges represent in sabbasi's solution.

Take the obvious graph theoretic interpretation. Label the vertices $v_1,v_2,\dots,v_n.$ For $i\in\{1,2,\dots,n\},$ let $x_i$ be the number of edges adjacent to $v_i$ or a neighbor of $v_i.$ Since $G$ is triangle-free, $$x_i=\sum_{w\in N(v_i)}\text{deg}(w).$$Therefore, $$x_1+x_2+\dots+x_n=\sum_{w}\text{deg}(w)^2\ge\frac{(\sum_{w}\text{deg}(w))^2}{n}=\frac{4m^2}{n}.$$Thus, there exists some $k$ such that $x_k\ge\left(\frac{2m}{n}\right)^2,$ as desired.

We solve the following equivalent problem: USAMO 1995/5 Reformulated wrote: Let $G$ be a triangle-free graph with $n$ vertices and $m$ edges. Show that one can select a vertex $v$ such that deleting vertex $v$ and all its neighbors kills at least $(\tfrac{2m}{n})^2$ edges. If the neighbors of a vertex $v$ are $u_1,u_2,\dots,u_t$, then the number of edges lost by the specified deletion is \[\sum_i \deg u_i\]because there are no triangles. Observe that the expected value of the sum is \[\sum_{u\in G}\deg u\cdot\frac{\deg u}{n}=\frac{1}{n}\sum_{u\in G}(\deg u)^2\ge \frac{1}{n^2}\left(\sum_{u\in G}\deg u\right)^2=\left(\frac{2m}{n}\right)^2\]by the Cauchy-Schwarz Inequality, implying the desired.

Let $T_2$ be the number of sets of three people with $2$ amicable pairs, and let $T_1$ be the number of sets of three people with $1$ amicable pair. Since there are no sets of three people with $3$ amicable pairs, we have \[ 2T_2 + T_1 = q(n-2),\]by a simple double counting argument on the number of amicable pairs. Now if $A(p)$ is the number of friends of a person $p$, observe that \[ \sum_{p} \binom{A(p)}{2} \ge n \binom{\sum\limits_p A(p)}{2} = n \binom {\frac{2q}{n}}{2} \]by Jensen's inequality, so the number of pairs containing a person $p$ and a hostile pair of people who are both friends with $p$ is at least $n \binom {\frac{2q}{n}}{2}$. But this is simply $T_2$, so \[ T_1 = q(n-2) - 2n \binom {\frac{2q}{n}}{2} = qn - 2q - n \left( \frac{2q}{n} \right) \left( \frac{2q}{n} - 1 \right) = qn - \frac{4q^2}{n}.\]To finish, notice that there is a one to one correspondence between sets of three people with exactly $1$ amicable pair and pairs containing a person $p$ and a amicable pair of people who are both foes to $p$. Thus, a person $p$ has on average \[ \frac1{n} \left(qn - \frac{4q^2}{n} \right) = q \left( 1 - \frac{4q}{n^2} \right),\]amicable pairs in its foes, which implies the conclusion. $\blacksquare$

Construct a graph $G=(V, E)$ with vertex set $V$ being the set of $n$ people and edge set $E$ being the set of $q$ amicable pairs. By the problem statement, $G$ is triangle-free. For each vertex $v$, denote by $\text{FE}(v)$ the set of edges between foes of $v$. The task is to prove that there exists $v\in V$ such that $|\text{FE}(v)|\le q\left(1-\frac{4q}{n^2}\right)$. We shall count the pairs $(v, e)$ where $v\in V$ is a vertex and $e$ is an edge in $\text{FE}(v)$. Counting from the perspective of $v$'s, number of pairs is $\sum_{v\in V} |\text{FE}(v)|$. Counting from the perspective of edges $uv$'s, since $u$ and $v$ have no common neighbour, the number of pairs is \[\sum_{uv\in E} \left(n-\deg{u}-\deg{v}\right) = nq-\sum_{v\in V} (\deg{v})^2 \le nq - \frac{4q^2}{n}\] where the inequality is due to Cauchy-Schwarz. Hence, we have \[\sum_{v\in V}|\text{FE}(v)|\le nq-\frac{4q^2}{n} = nq\left(1-\frac{4q}{n^2}\right).\] So, by pigeonhole principle, at least one $v\in V$ satisfies $|\text{FE}(v)|\le q\left(1-\frac{4q}{n^2}\right)$. $\square$

Fairly weak problem; every step is basically forced. We solve the problem in the following alternative formation: given a triangle-free graph with $n$ vertices and $m$ edges, we show that we can select a vertex $v$ such that deleting $v$ and its neighbors removes at least $\left(\frac{2m}n\right)^2$ from the graph. Consider pairs $(v, u, e)$ where $e$ is an edge and $v, u$ are vertices with $uv$ an edge such that $e$ is incident with $u$. First, fix $u$, and notice that there are $(\deg u)^2$ ways to pick $v$ and $e$. So the number of pairs is bounded below by $$k = \sum_v (\deg v)^2 \geq \frac{(2m)^2}n$$by Cauchy-Schwarz. But there are at most $n$ choices for $v$ and thus there exists a $v$ associated with $\left(\frac{2m}n\right)^2$ such pairs. Because no two neighbors $u_1, u_2$ of $v$ are connected, all such edges $e$ are then distinct for this $v$, which finishes.