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
Problem
Source: Macedonian Mathematical Olympiad 2023 P3
Tags: combinatorics
11.04.2023 11:09
Replace $1000$ with any even integer $n$. We will prove that the answer is $\dfrac{n^3}{4}$. Let $a_i$ be the $n$ colours, and consider the $n$ graphs $G_i$ such that the vertices of each $G_i$ are the $n$ gnomes of colour $i$, and we connect two gnomes with an edge if and only if they are friends. Claim: Each $G_i$ is a bipartite graph. Proof: We will prove that $G_i$ cannot have odd cycles, from which result our Claim follows (this is a well-known characterization of bipartite graphs). Assume otherwise. Give a red candy to each gnome belonging to the $(2j+1)-$th story for some $j$, and a blue candy to each gnome belong to the $2j-$th story for some $j$. Then, along a cycle we alternate between gnomes with red and blue candies, which makes it impossible for the cycle to have odd length, as desired. $\blacksquare$ To the problem, since each $G_i$ is a bipartite graph, it has at most $\dfrac{n^2}{4}$ edges. Indeed, if the two parts of the graph have $a$ and $b$ vertices respectively, then $a+b=n$ and so by AM-GM $ab \leq \dfrac{(a+b)^2}{4}=\dfrac{n^2}{4}$. Therefore, in total we have at most $n \cdot \dfrac{n^2}{4}=\dfrac{n^3}{4}$ pairs of friends (since those pairs appear only between vertices of the same $G_i$). 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}$
11.04.2023 18:14
Claim) for an arbitrary colour $i$, there are at most ${n^2} \over 4$ pairs of friends that have the colour $i$. Pf) Enough to prove for colour 1. Let there are $a_i$ gnomes in the $i$th floor that has the colour 1. Note that $\sum _{i=1} ^n a_i =n$. Let #(pair of friends that has the colour 1) $=S$ $S=\sum _{i=1} ^{n-1} a_i a_{i+1} \le (\sum _{i=odd} a_i) (\sum _{i=even} a_i) =-(\sum _{i=odd} a_i)^2+n(\sum _{i=odd} a_i) \le {{n^2} \over 4}$ Therefore the maximum pairs of friends are $n^3 \over 4$. An example showing this is: 111222 222111 333444 444333 555666 666555
09.05.2023 20:55
I claim that the maximum number of friendships is $500^2 * 1000$. Proof: 121212 212121 343434 434343 So, for each color you have 500*500 options, total of $1000 * 500^2$ We can represent gnomes with a graph $G$ where the gnomes are vertices, and 2 vertices are connected if the gnomes are "friends". Claim: There is no $K_3$ in $G$. Proof: Choose gnomes with same color $d_1, d_2, d_3$, then $|d_1 - d_2| = |d_2 - d_3| = |d_1 - d_3| = 1$ It follows that $|d_i - d_j| = {0, 2}$ for $0 < i < j < 4$. Contradicition. From Turan's theorem: $|E| \leq (1000^2 / 4) = 500^2$. Proof done