Macedonian Mathematical Olympiad

Let us analyze the problem. There are $1000$ towers, each with $1000$ stories, so there are $1000\times 1000=10^6$ gnomes. Each gnome wears a hat of one of $1000$ colors, and in each tower, all $1000$ colors are present (since 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 lives on the $k$-th story of his tower, and the other on the $(k+1)$-st story of his tower (possibly in a different tower).

We are to maximize the number of such pairs.

Let us fix a color $c$. In each tower, there is exactly one gnome with hat color $c$ on each story. So, for color $c$, there are $1000$ towers $\times$ $1000$ stories = $1000$ gnomes with color $c$.

For each color $c$, consider the gnomes on the $k$-th story in all towers. There are $1000$ such gnomes (one per tower). Similarly, for the $(k+1)$-st story. For each $k=1$ to $999$, we can pair each gnome on the $k$-th story with each gnome on the $(k+1)$-st story, but only if they are in different towers (since in the same tower, the two gnomes have different colors).

But the definition says: "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". It does not require them to be in the same tower, and in fact, in the same tower, the two gnomes have different colors, so cannot be friends.

So, for each color $c$, for each $k=1$ to $999$, we can pair the gnome with color $c$ on the $k$-th story of tower $i$ with the gnome with color $c$ on the $(k+1)$-st story of tower $j$, for all $i,j$ from $1$ to $1000$.

But to count the number of pairs, for each color $c$, for each $k=1$ to $999$, there are $1000$ gnomes on the $k$-th story and $1000$ gnomes on the $(k+1)$-st story, so $1000\times 1000=10^6$ possible pairs for each $k$ and each color $c$.

But we must be careful: is it allowed to pair a gnome on the $k$-th story of tower $i$ with the gnome on the $(k+1)$-st story of tower $j$ for any $i,j$? Yes, as long as they have the same color, which is possible since every tower has all colors, and the gnome on the $k$-th story of tower $i$ with color $c$ exists for every $i$ and $k$.

But the problem asks for the maximum possible number of pairs. That is, we can assign the colors to the gnomes in the towers in any way, as long as in each tower, all $1000$ colors are present (no two gnomes in the same tower have the same color).

Let us try to maximize the number of pairs. For each color $c$, for each $k=1$ to $999$, the gnome with color $c$ on the $k$-th story of tower $i$ and the gnome with color $c$ on the $(k+1)$-st story of tower $j$ can be paired as friends for all $i,j$.

But the problem says "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". It does not specify that the towers must be different, but in the same tower, the two gnomes have different colors, so cannot be friends.

Therefore, for each color $c$, for each $k=1$ to $999$, the gnome with color $c$ on the $k$-th story of tower $i$ and the gnome with color $c$ on the $(k+1)$-st story of tower $j$ are friends for all $i,j$ from $1$ to $1000$.

But we must count the number of pairs. For each color $c$, for each $k=1$ to $999$, there are $1000$ gnomes on the $k$-th story and $1000$ gnomes on the $(k+1)$-st story, so $1000\times 1000=10^6$ pairs for each $k$ and each color $c$.

But if we count all such pairs, we are counting each unordered pair twice (once as $(a,b)$ and once as $(b,a)$), unless the problem wants ordered pairs. But the problem says "a pair of gnomes are friends if...", so we count unordered pairs.

But in this construction, for each color $c$, for each $k=1$ to $999$, for each $i,j$ from $1$ to $1000$, the pair (gnome with color $c$ on $k$-th story of tower $i$, gnome with color $c$ on $(k+1)$-st story of tower $j$) is a friend pair. But the pair (gnome on $k$-th story of tower $i$, gnome on $(k+1)$-st story of tower $j$) and (gnome on $(k+1)$-st story of tower $j$, gnome on $k$-th story of tower $i$) are different unless $i=j$ and $k$ and $k+1$ are swapped, but since in the same tower, the two gnomes have different colors, so cannot be friends.

Therefore, for each color $c$, for each $k=1$ to $999$, for each $i\ne j$, the pair (gnome with color $c$ on $k$-th story of tower $i$, gnome with color $c$ on $(k+1)$-st story of tower $j$) is a friend pair.

But the problem does not specify that the two gnomes must be in different towers, but in the same tower, the two gnomes have different colors, so cannot be friends.

Therefore, for each color $c$, for each $k=1$ to $999$, for each $i,j$ from $1$ to $1000$, $i\ne j$, the pair (gnome with color $c$ on $k$-th story of tower $i$, gnome with color $c$ on $(k+1)$-st story of tower $j$) is a friend pair.

But since the gnome with color $c$ on $k$-th story of tower $i$ and the gnome with color $c$ on $(k+1)$-st story of tower $j$ are distinct for $i\ne j$, and the pair is unordered, we must count each pair only once.

Alternatively, for each color $c$, for each $k=1$ to $999$, there are $1000$ gnomes on the $k$-th story and $1000$ gnomes on the $(k+1)$-st story, so $1000\times 1000=10^6$ pairs for each $k$ and each color $c$.

But since the gnomes are in different towers, and the colors are assigned so that in each tower, all colors are present, the maximum possible number of pairs is achieved when for each color $c$, for each $k=1$ to $999$, all $1000$ gnomes on the $k$-th story and all $1000$ gnomes on the $(k+1)$-st story are paired.

Therefore, the total number of pairs is:

Number of colors: $1000$ Number of $k$: $999$ (from $1$ to $999$) For each $k$ and color, $1000\times 1000=10^6$ pairs

Total number of pairs: $$1000\times 999\times 10^6=999\times 10^9$$

Therefore, the maximum possible number of pairs of gnomes that are friends is $999\times 10^9$.