MK-MO 2023 Problem 3

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.

Authored by Nikola Velov