Maths Olympiad Prep

Library / /25 of 37

Combinatorics Difficulty 8.1 Shortlist Find the answer

In a sports league, each team uses a set of at most tt signature colors. A set SS of teams is[i] color-identifiable[/i] if one can assign each team in SS one of their signature colors, such that no team in SS is assigned any signature color of a different team in SS.

For all positive integers nn and tt, determine the maximum integer g(n,t)g(n, t) such that: In any sports league with exactly nn distinct colors present over all teams, one can always find a color-identifiable set of size at least g(n,t)g(n, t).

A number or a short expression. Spacing and $ signs are ignored.

Solution

In a sports league, each team uses a set of at most t t signature colors. A set S S of teams is color-identifiable if one can assign each team in S S one of their signature colors, such that no team in S S is assigned any signature color of a different team in S S .

For all positive integers n n and t t , we aim to determine the maximum integer g(n,t) g(n, t) such that in any sports league with exactly n n distinct colors present over all teams, one can always find a color-identifiable set of size at least g(n,t) g(n, t) .

The answer is nt \lceil \frac{n}{t} \rceil .

To show that the answer cannot be higher, consider the following construction: let team 1 have colors 1,2,3,,t 1, 2, 3, \ldots, t , team 2 have colors t+1,t+2,,2t t+1, t+2, \ldots, 2t , and so on. Team k k will have colors (k1)t+1,(k1)t+2,,min(kt,n) (k-1)t + 1, (k-1)t + 2, \ldots, \min(kt, n) . This construction results in nt \lceil \frac{n}{t} \rceil teams, so g(n,t)nt g(n, t) \leq \lceil \frac{n}{t} \rceil .

To prove that g(n,t)nt g(n, t) \geq \lceil \frac{n}{t} \rceil , construct a function f(i) f(i) that maps each color i i to a team such that team f(i) f(i) has i i as a signature color. This function must exist because each color is the signature color of some team. Let S S be the set of teams equal to f(i) f(i) for some i i . Construct a bipartite graph with teams in S S as left vertices and colors as right vertices.

There are clearly at least n n edges, one for each color. Since each left vertex (team) has degree at most t t , there are at least nt \lceil \frac{n}{t} \rceil teams in this set. Furthermore, because f f is surjective from colors to teams, Hall's Marriage Theorem applies, ensuring a perfect matching exists.

Thus, the maximum integer g(n,t) g(n, t) is:
nt \boxed{\lceil \frac{n}{t} \rceil}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.