Question 126
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 citizen proudly wears a hat colored in one of $1000$ possible colors and any two residents of the same tower wear differently colored hats. A pair of gnomes are friends if they wear hats of the same color, one of them lives on the $k$-th story of his tower and the other one lives on the $(k+1)$-st story of his tower. Determine the maximum possible number of pairs of gnomes that are friends.