In a city of gnomes there are $1000$ identical towers, each of which has $1000$ stories, with exactly one gnome living on each story. Every gnome in the city wears a hat colored in one of $1000$ possible colors and any two gnomes in the same tower have different hats. A pair of gnomes are friends if they wear hats of the same color, one of them lives in the $k$-th story of his tower and the other one in the $(k+1)$-st story of his tower. Determine the maximal possible number of pairs of gnomes which are friends.

[i]Proposed by Nikola Velov[/i]
1. **Restate the problem with generalization:**
   We are given \( n = 1000 \) towers, each with \( n = 1000 \) stories, and each story has one gnome. Each gnome wears a hat of one of \( n = 1000 \) colors, and no two gnomes in the same tower have the same hat color. A pair of gnomes are friends if they wear hats of the same color and live on consecutive stories in their respective towers. We need to determine the maximum number of such pairs of friends.

2. **Define the problem in terms of graphs:**
   Let \( n \) be any even integer. We will prove that the maximum number of pairs of friends is \( \frac{n^3}{4} \). Let \( a_i \) be the \( n \) colors, and consider the \( n \) graphs \( G_i \) such that the vertices of each \( G_i \) are the \( n \) gnomes of color \( i \), and we connect two gnomes with an edge if and only if they are friends.

3. **Claim: Each \( G_i \) is a bipartite graph.**
   - **Proof:**
     We will prove that \( G_i \) cannot have odd cycles, which implies that \( G_i \) is bipartite (a well-known characterization of bipartite graphs). Assume otherwise. Assign a red candy to each gnome on the \( (2j+1) \)-th story for some \( j \), and a blue candy to each gnome on the \( 2j \)-th story for some \( j \). Along a cycle, we alternate between gnomes with red and blue candies, making it impossible for the cycle to have odd length, as desired. \(\blacksquare\)

4. **Calculate the maximum number of edges in each \( G_i \):**
   Since each \( G_i \) is bipartite, it has at most \( \frac{n^2}{4} \) edges. If the two parts of the graph have \( a \) and \( b \) vertices respectively, then \( a + b = n \) and by the Arithmetic Mean-Geometric Mean (AM-GM) inequality, \( ab \leq \frac{(a+b)^2}{4} = \frac{n^2}{4} \).

5. **Total number of pairs of friends:**
   Therefore, in total, we have at most \( n \cdot \frac{n^2}{4} = \frac{n^3}{4} \) pairs of friends, since those pairs appear only between vertices of the same \( G_i \).

6. **Example to show attainability:**
   An example showing that this is attainable is the following (for \( n = 6 \), with columns denoting towers and rows denoting stories, where the last row is the first story), which easily generalizes:
   \[
   \begin{array}{|c|c|c|c|c|c|}
   \hline
   1 & 2 & 1 & 2 & 1 & 2 \\ \hline
   2 & 1 & 2 & 1 & 2 & 1 \\ \hline
   3 & 4 & 3 & 4 & 3 & 4 \\ \hline
   4 & 3 & 4 & 3 & 4 & 3 \\ \hline
   5 & 6 & 5 & 6 & 5 & 6 \\ \hline
   6 & 5 & 6 & 5 & 6 & 5 \\ \hline
   \end{array}
   \]

The final answer is \(\boxed{\frac{n^3}{4}}\).