$2017$ USA TST P1

For discussing Olympiad Level Combinatorics problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
$2017$ USA TST P1

Unread post by rah4927 » Mon Jan 30, 2017 11:02 pm

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$, 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)$.

Source: USA TST $2017$, Problem $1$

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: $2017$ USA TST P1

Unread post by rah4927 » Tue Jan 31, 2017 12:04 am

Let me first rephrase the problem so that it becomes a bit easier to deal with. Imagine a bipartite graph, the left side (call it $S$) containing teams(we only need to look at $S<n$), and the right side (call it $C$) containing $n$ colours. We join the two vertices in $S$ and $C$ if the team corresponding to that vertex has been assigned that colour in $C$. Notice that by our condition, degree of any vertex in $S$ can be at most $k$.

Claim: $g(n,k) \le \lceil \frac{n}{k} \rceil$

Start by joining each vertex of $S$ to exactly $k$ colours in $C$, with each colour being used exactly once. Notice that we will have used all colours by using $\lceil \frac{n}{k} \rceil$ vertices in $S$; let all the other vertices have degree $0$. This construction yields $g(n,k)=\lceil \frac{n}{k} \rceil$, so we are done.

Claim: $g(n,k)\ge \lceil \frac{n}{k} \rceil$

Verify that this is true for some values of $(n,k)$. We will induct on $n+k$. Fix $n$ and prove that the claim holds for $k=1$. Notice that the claim is true quite obviously if $k\le n\le 2k$. So assume $n>2k$ throughout the rest of the proof.

Suppose our claim also holds when $k=i$, for some $i$.Now let $k=i+1$ (with $n>2(i+1)$). Pick a vertex in $S$ that has degree exactly $i+1$ (if this doesn't exist, then the case just reduces to $k=i$ and we are done). Remove the $k=i+1$ colours from $C$ and that vertex from $S$. Since $n-k>k$, by strong induction hypothesis, we have a proper matching of size $\lceil \frac{n-k}{k} \rceil$. Now add that vertex to the list (since it's connected to $k$ of them already), and we are done.

So, $g(n,k)=\lceil \frac{n}{k} \rceil$

Post Reply