In a sports league, each team uses a set of at most t signature colors. A set S of teams is color-identifiable if one can assign each team in S one of their signature colors, such that no team in S is assigned any signature color of a different team in S.
For all positive integers n and t, we aim to determine the maximum integer g(n,t) such that in any sports league with exactly n distinct colors present over all teams, one can always find a color-identifiable set of size at least g(n,t).
The answer is ⌈tn⌉.
To show that the answer cannot be higher, consider the following construction: let team 1 have colors 1,2,3,…,t, team 2 have colors t+1,t+2,…,2t, and so on. Team k will have colors (k−1)t+1,(k−1)t+2,…,min(kt,n). This construction results in ⌈tn⌉ teams, so g(n,t)≤⌈tn⌉.
To prove that g(n,t)≥⌈tn⌉, construct a function f(i) that maps each color i to a team such that team f(i) has i as a signature color. This function must exist because each color is the signature color of some team. Let S be the set of teams equal to f(i) for some i. Construct a bipartite graph with teams in S as left vertices and colors as right vertices.
There are clearly at least n edges, one for each color. Since each left vertex (team) has degree at most t, there are at least ⌈tn⌉ teams in this set. Furthermore, because f is surjective from colors to teams, Hall's Marriage Theorem applies, ensuring a perfect matching exists.
Thus, the maximum integer g(n,t) is:
⌈tn⌉