Problem

Source: Macedonian Mathematical Olympiad 2023 P3

Tags: combinatorics



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. Proposed by Nikola Velov