3. In the city of hedgehogs, there are 1000 identical buildings, each with 1000 floors, and exactly one hedgehog lives on each floor. Each resident in the city wears a hat colored in one of 1000 possible colors, and any two residents in the same building have hats of different colors. We say that two hedgehogs are $\bar{u} p u j a \bar{u} e l i$ if they wear hats of the same color and live on consecutive floors (in different buildings). Determine the maximum possible number of (unordered) pairs of hedgehogs that are friends.
Solution. Let $k=500$. First, we will show that for a fixed color $c$, there cannot be more than $k^{2}$ pairs of friends wearing caps of color $c$.

Indeed, let us form (a simple) graph whose vertices are the gnomes wearing caps of color $c$, and there is an edge between two vertices if the corresponding gnomes are friends.

We will show that this graph does not contain triangles. Suppose the opposite, that the gnomes living on floors numbered $s_{1}, s_{2}$, and $s_{3}$ are friends (in pairs). Without loss of generality, let $s_{1}>s_{2}>s_{3}$. Then $s_{1}=s_{2}+1$ and $s_{2}=s_{3}+1$. But this means that the gnomes living on floors numbered $s_{1}$ and $s_{3}$ are not friends because $s_{1}-s_{3}=2$, a contradiction.

We will use the following auxiliary result (known as Mantel's Theorem).

Lemma. Every simple graph of order (number of vertices) $n \geq 3$ and size (number of edges) $m>\left\lfloor\frac{n^{2}}{4}\right\rfloor$ contains a triangle.

Proof 1. Note that the statement is true for $n \in\{4,5\}$. Assuming the statement is not true in general, consider a counterexample $G$ of the smallest possible order $n$. Thus $n \geq 5$. Let $u v$ be any edge of $G$. Since $u v$ does not lie on a triangle, there is no vertex $w$ adjacent to both $u$ and $v$. Therefore, $(\operatorname{deg}(u)-1)+(\operatorname{deg}(v)-1) \leq n-2$, or $\operatorname{deg}(u)+\operatorname{deg}(v) \leq n$. Let $G^{\prime}=G-u-v$ be the graph obtained from $G$ by deleting vertices $u$ and $v$ (along with all edges incident to at least one of these two vertices). Thus $G^{\prime}$ has order (number of vertices) $n^{\prime}=n-2$ and size (number of edges)

$$
m^{\prime}=m-(\operatorname{deg}(u)+\operatorname{deg}(v))+1 \geq m-n+1>\left\lfloor\frac{n^{2}}{2}\right\rfloor-n+1
$$

Thus,

$$
m^{\prime}>\frac{n^{2}}{4}-n+1=\frac{n^{2}-4 n+4}{4}=\frac{(n-2)^{2}}{4}
$$

Since $n-2 \geq 3$, from the minimal choice of $G$ it follows that $G^{\prime}$ contains a triangle. But, $G^{\prime} \subseteq G$, which contradicts the assumption that $G$ does not contain a triangle.

Proof 2. Let $G$ be a simple graph of order $n$ that does not contain triangles. Let $\alpha$ denote the number of elements in a maximum independent set $A \subseteq V(G)$. (For a subset of $V(G)$, we say it is independent if there are no edges between its elements.) Let $\beta=n-\alpha$. Since $G$ does not contain triangles, the neighbors of any vertex $v \in V(G)$ form an independent set. Therefore, $\operatorname{deg}(v) \leq \alpha$.

Every edge of $G$ has at least one endpoint (vertex) in the set $B=V(G) \backslash A$ (since $A$ is independent). Thus, counting the edges of $G$ from their endpoints in $B$, we have $m=|E(G)| \leq \sum_{v \in B} \operatorname{deg}(v)$. Consequently, the inequality between the arithmetic and geometric means gives

$$
m \leq \sum_{v \in B} \operatorname{deg}(v) \leq \alpha \beta \leq\left(\frac{\alpha+\beta}{2}\right)^{2}=\frac{n^{2}}{4}
$$

In fact, this proof shows something more: Among simple graphs of order $n$ that do not contain triangles, the one with the most edges, namely $\left\lfloor\frac{n^{2}}{4}\right\rfloor$, is the unique complete bipartite graph $K_{\left\lfloor\frac{n}{2}\right\rfloor,\left\lceil\frac{n}{2}\right\rfloor}$.

From the lemma, we immediately have that every simple graph without triangles with $2 k$ vertices can have at most $k^{2}$ edges. (In this case, equality is achieved only for the complete bipartite graph $K_{k, k}$.) Therefore, for each color, there can be at most $k^{2}$ pairs of gnomes who are friends and wear caps of that color. Consequently, the total number of friendships in the city cannot exceed $2 k \cdot k^{2}=2 k^{3}=2 \cdot 500^{3}$.

To obtain a construction where the upper bound is achieved, let $\left\{c_{1}, \ldots, c_{2 k}\right\}$ be the set of colors. In the first 500 buildings, take the sequence of cap colors that the gnomes wear, from bottom to top, to be $c_{1}, c_{2}, c_{3}, c_{4}, \ldots, c_{2 k-1}, c_{2 k}$, and in the remaining 500 buildings, let this sequence be $c_{2}, c_{1}, c_{4}, c_{3}, \ldots, c_{2 k}, c_{2 k-1}$. Thus, each gnome has exactly $k$ friends. Since the total number of gnomes is $2 k \cdot 2 k=4 k^{2}$, the total number of friendships is

$$
\frac{1}{2} \cdot k n^{2} \cdot k=2 k^{3}=2 \cdot 500^{3}
$$

Therefore, we conclude that the maximum possible number of friendships is $2 \cdot 500^{3}$.