In a football league, there are $n\geq 6$ teams. Each team has a homecourt jersey and a road jersey with different color. When two teams play, the home team always wear homecourt jersey and the road team wear their homecourt jersey if the color is different from the home team's homecourt jersey, or otherwise the road team shall wear their road jersey. It is required that in any two games with 4 different teams, the 4 teams' jerseys have at least 3 different color. Find the least number of color that the $n$ teams' $2n$ jerseys may use.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
13.11.2010 01:14
Let $C$ be the number of distinct colours required. Denote the $i^{\text{th}}$ team by $T_i=(a_i,b_i)$, where $a_i$ is the homecourt jersey colour and $b_i$ is their away colour. Let (*) be the property that at least three colours are used in any two games between four teams. 1) Call two teams similar if their homecourt jerseys are the same colour. If there exists two pairs of similar teams and the pairs have different homecourt jereseys, we have a contradiction. That is, if we have pairs of the form $(a,b_1),(a,b_2),(c,b_3),(c,b_4)$ with $a\not = c$ then we can have two games with colours $(a,c)$ which contradicts (*). It follows that only one colour can appear more than once as a homecourt colour. 2) If at least three teams, $T_i,T_j,T_k$ are similar then no other team can use the colour $b_i,b_j,b_k$ for their homecourt colours. Otherwise we might have team $(a,b_i),(a,b_j),(a,b_k),(b_i,c)$ and we get two games using colours $(a,b_i)$, again contradicting (*). 3) If at least four teams $T_i,T_j,T_k,T_{\ell}$ are similar then their away jerseys are distinct. From (1) we can assume wlog that $T_1,T_2,...,T_k$ are similar and $T_{k+1},...,T_n$ have distinct homecourt jerseys, for some $k \le n$. If $k\ge 4$ then from (3) the $k$ similar teams have distinct away jerseys, and from (2) those away jerseys are distinct from the homecourt jerseys of $T_{k+1},...,T_n$. It follows that $C \ge 1 + k + (n-k) = n+1$. If $k=3$ then from (2) the first $k$ teams have away jerseys that are distinct to the home jerseys of $T_k,...,T_n$. So we need $1$ colour for the first $k$ teams home jerseys, another colour for their away jerseys and $n-3$ colours for the remaining teams home jerseys giving $C\ge 1 + 1 + n-3 = n-1$ If $k=2$ then just looking at homecourt jerseys we have $C \ge n-1$ If $k=1$ then we need $n$ distinct homecourt jerseys. From the above we conclude that $\min\{C\}=n-1$. Equality occurs in two cases $\text{Teams}=\{(c_1,c_2),(c_1,c_2)\}\cup\{(c_2,c_3)\}\cup\{(c_3,c_2),(c_4,c_2),...,(c_{n-1},c_2)\}$ $\text{Teams}=\{(c_1,c_2),(c_1,c_2),(c_1,c_2)\}\cup\{(c_3,c_1),(c_4,c_1),...,(c_{n-1},c_1)\}$