The answer is $g(n,t)=\left\lceil\frac nt\right\rceil=k$. Interpret the problem as a bipartite graph between the set $A$ of teams and the set $B$ of colors with $a\in A$ connected to $b\in B$ iff $b$ is a signature color of $a$. The condition says that $\deg_{A-B}a\le t$, $\deg_{A-B}b>0$, and $|B|=n$. We will show the existence of a matching $a_1-b_1,a_2-b_2,\ldots,a_k-b_k$ such that $a_i$ is not adjacent to $b_j$ for any $i\ne j$, which proves that $g(n,t)\ge k$. Take an edge $x-y$ with $x\in A$ and $y\in B$ such that $\deg_{A-B}y=d$ is minimal, add $x-y$ to the matching, and delete $N_{A-B}(x,y)$ from the graph, creating a new bipartite graph between $A'\subset A$ and $B'\subset B$. No edge in $A'-B'$ will have a common neighbor edge with $x-y$, so we may add any edge in $A'-B'$ to our matching. Note that $|B'|=n-|N_{A-B}(x)|\ge n-t$ and that for any $a'\in A'$, $\deg_{A'-B'}a'\le\deg_{A-B}a'\le t$. We claim that for any $b'\in B'$, $\deg b'_{A'-B'}>0$. If $\deg_{A'-B'}b'=0$, then we must have $N_{A-B}(b')\subset N_{A-B}(b)$. Because $d$ is minimal, $N_{A-B}(b')=N_{A-B}(b)$. However, $b'\not\in N_{A-B}(a)$, so $a\not\in N_{A-B}(b')$. However, $a\in N_{A-B}(b)$, a contradiction. Hence, $\deg_{A'-B'}b'>0$, so we may repeat this process $k$ times, removing at most $t$ vertices from $B$ each time while maintaining positive degree for all vertices in $B$, and this results in the desired matching. To prove that the bound is sharp, note that it is possible for $k$ teams to have pairwise disjoint signature color sets, resulting in any number of colors at most $kt\ge n$. We clearly can't have a matching of size greater than $k$ if there are only $k$ teams, so we are done.

Oops the one below is the same except with the realization that when you remove teams to make $A'$, you don't actually remove any teams.

EDIT: misread, ignore for now

It seems like there's been some misreading of this problem in particular, so I'll attempt to clarify: Quote: 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$. So, if there are two teams $A$ and $B$ with signature color sets $\{a,b\}$ and $\{a,c\}$ respectively, $A\to a$ and $B \to c$ is not an acceptable color identification, because $A$'s color is one of $B$'s signature colors. The other important part of this problem is that the set you choose of size $\geq g(n,t)$ is any subset of the global set of teams; not all teams are part of this process.

Wait but you can't necessarily use any color you want. For example, what if the first color you pick was a signature color of every team? You're correct. I've deleted my incorrect solution which this referred to.

whatshisbucket wrote: Wait but you can't necessarily use any color you want. For example, what if the first color you pick was a signature color of every team? Yes, thanks. I've deleted the obviously wrong solution. Teaches me to not post late at night Here's the corrected solution, which I now see is the same as ABCDE's solution above, just phrased without bipartite graphs. The idea is to greedy pick by color (rather than by team), taking at each step the least used color. Select the color $C_1$ with the fewest teams using it, and a team $T_1$ using it. Then delete all colors $T_1$ uses, and all teams which use $C_1$. Note that By problem condition, this deletes at most $t$ teams total. Any remaining color $C$ still has at least one user. Indeed, if not, then $C$ had the same set of teams as $C_1$ did (by minimality of $C$), but then it should have deleted as a color of $T_1$. Now repeat this algorithm with $C_2$ and $T_2$, and so on. This operations uses at most $t$ colors each time, so we select at least $\left\lceil n/t \right\rceil$ colors. To explain the error: In my earlier solution I failed to delete the teams which used $C_1$, so I was picking the colors arbitrarily, hence the correct objection by whatshisbucket above. The solution by mathwizard888 is still shortest, though. On a side note, I originally added this problem to my notes as "most easy to mis-read", but I think it's getting an honorable mention for "most easy to fake-solve" as well now.

mathwizard888 wrote:

I've received a PM asking for motivation for this solution, so I'll share my thought process coming up with this during the test. Initially, I misread the problem, leading to the misinterpretation that zacchro mentioned. When I realized this, I tried to modify my original solution to actually work, but I couldn't. The idea I had then was to start with a set of teams and delete all shared signature colors. I would then hope that each team still had a signature color left, in which case the set would be color-identifiable. The key realization is that if a team does not have a signature color left after this procedure, it can be removed without really changing anything. This was what led to taking the set $S$ in my solution; it also supported my intuition that the answer would still be $\left\lceil\frac{n}{t}\right\rceil$.

v_Enhance wrote: whatshisbucket wrote: Wait but you can't necessarily use any color you want. For example, what if the first color you pick was a signature color of every team? Yes, thanks. I've deleted the obviously wrong solution. Teaches me to not post late at night Here's the corrected solution, which I now see is the same as ABCDE's solution above, just phrased without bipartite graphs. The idea is to greedy pick by color (rather than by team), taking at each step the least used color. Select the color $C_1$ with the fewest teams using it, and a team $T_1$ using it. Then delete all colors $T_1$ uses, and all teams which use $C_1$. Note that By problem condition, this deletes at most $t$ teams total. Any remaining color $C$ still has at least one user. Indeed, if not, then $C$ had the same set of teams as $C_1$ did (by minimality of $C$), but then it should have deleted as a color of $T_1$. Now repeat this algorithm with $C_2$ and $T_2$, and so on. This operations uses at most $t$ colors each time, so we select at least $\left\lceil n/t \right\rceil$ colors. To explain the error: In my earlier solution I failed to delete the teams which used $C_1$, so I was picking the colors arbitrarily, hence the correct objection by whatshisbucket above. The solution by mathwizard888 is still shortest, though. On a side note, I originally added this problem to my notes as "most easy to mis-read", but I think it's getting an honorable mention for "most easy to fake-solve" as well now. A little mistake to point out: in any process we deleted at most $t$ colors, rather than teams.

v_Enhance wrote: Note that By problem condition, this deletes at most $t$ teams total. On a side note, I originally added this problem to my notes as "most easy to mis-read", but I think it's getting an honorable mention for "most easy to fake-solve" as well now. I probably misread the problem; why does this delete at most $t$ teams total again? (and I apologize in advance for my stupidity )

We claim that the answer is: $\lceil n/t \rceil$ To get this as an upper bound, consider a league of $\lceil n/t \rceil$ teams, with the sets of signature colors of the teams together covering the total of $n$ colors. This is obviously a valid possibility with the desired upper bound. To get this as a lower bound, we use strong induction on $n$ with $t$ fixed. The base cases $n = 1$ to $n = t$ are trivial. Now we suppose our hypothesis is true for all $n \le k, k \ge t$, and prove it for $n = k+1$. Delete teams from the league until the first instance where you find a team $A$ and a color $Red$ such that deleting $A$ would cause $Red$ to no longer be part of any set of signature colors. Now, temporarily delete $A$, and make all the signature colors of $A$ temporarily unavailable as signature colors for the leftover teams. This reduces the number of elements of the set of colors part of atleast one signature set by at least $1$ and at most $t$. Now, by induction hypothesis, there exists a color-identifiable set of atleast $\lceil n/t \rceil - 1$ teams with certain assigned colors, among the leftover teams, under the restrictions we've specified. Note that adding $A$ to this set with $Red$ as its assigned color still leaves the set as a color-identifiable one, so the induction step is over and we're done.

We claim that $g(n,t)=\lceil n/t\rceil$. To see that $g(n,t)\le\lceil n/t\rceil$, consider a case where all the team colors are disjoint with as many teams as possible having exactly $t$ colors (it's possible to have one team with $n\pmod{t}$ colors). It's easy to see that there are exactly $\lceil n/t\rceil$ teams, and picking them all leads to a color identifiable set. We can't pick any more teams as there are none, so $g(n,t)\le\lceil n/t\rceil$. Now we show that $g(n,t)\ge\lceil n/t\rceil$. To do this, we need to show that we can always pick a color identifiable set of size at least $\lceil n/t\rceil$. Start with $S$ containing all teams. Now do the following algorithm. For each team $T\in S$, if removing $T$ from $S$ makes it such that $S$ still contains all $n$ colors over all of its team signature colors, then delete $T$ from $S$, and repeat the process. Clearly this algorithm terminates as $|S|$ is finite, so consider the final $S$ after this algorithm is done. We see that all $n$ colors are present in $S$, and further, for each team $T\in S$, $T$ has a signature color $c$ that no other team in $S$ has (otherwise the algorithm would have deleted $T$). Assign this color $c$ to $T$ for each team $T$. This is color identifiable since the assigned colors are not present in any of the signature colors of any of the other teams in $S$. There are $n$ colors over $|S|$ teams with each team having at most $t$ colors, so $|S|\ge\lceil n/t\rceil$, so we can pick $g(n,t)$ teams that are color identifiable, as desired. $\blacksquare$ Remarks Note that you are essentially forced into the algorithm I described since deleting teams in that way leads to a configuration in which the problem's premise still holds, and this situation is "strictly harder". I originally did this as an optimization to organize my thinking, but was extremely surprised when the problem just solved itself after doing this optimization.

Solved with naman12

The answer is $\boxed{g(n,t) = \left \lceil\frac{n}{t}\right\rceil. }$ The upper bound is trivial. For the lower bound, choose the smallest possible set $S$ such that each of the $n$ colors is a signature color of a team in $S$. Now suppose for the sake of contradiction that $S$ is not color-identifiable; now there must be a team in $S$ that does not have a signature color distinct from the rest of the teams in $S$. But simply delete this team; note that there still exist $n$ distinct colors in $S$ with one less element; this contradicts the minimality. Finally, remark that as each of the teams in $S$ has at most $t$ colors, we have $g(n,t) \geq \left \lceil\frac{n}{t}\right\rceil,$ as desired. Remarks: This problem was kind of silly. The main motivation for this solution is that the "obvious" greedy algorithm of choosing as many teams that satisfy the condition as possible fails; the reason being that there may exist a team $T_i \in S$ and $T_j \notin S$ such that there is only one choice of signature color for $T_i$, and that color is also present in $T_j.$ Thus we need to be more careful in choosing $S$ instead of picking teams arbitrarily; some experimentation leads to the above solution. As an aside, I don't really understand why this is a "circular optimization" problem?

The answer is $g(n,t)=\left\lceil \frac{n}{t}\right\rceil$, which we will call $k$. As a construction, take $k$ teams, with the first $k-1$ having $t$ colors, the last having $n-t(k-1)$, and all colors being disjoint. Clearly this gives us a color-identifiable set of size $k$ (which is just all of the teams), but we cannot have a color-identifiable set that's any larger because there aren't enough teams, implying the upper bound. Now, represent the signature colors of a team with sets in the obvious way, and let $T$ be the set of all teams present. Also, for any set $A$ of teams, let $c(S)$ denote the set of all colors over all teams in $A$. Let $S$ be the subset of $T$ with minimal size such that $c(S)=c(T)$. If there are multiple, just pick any one. I claim that for any team $t \in S$, we have $c(S) \neq c(S \setminus t)$. Indeed, suppose otherwise. and let $t \in S$ be a team with $c(S)=c(S \setminus t)$. But this implies that $c(S \setminus t)=c(T)$, and since $|S\setminus t|=|S|-1$, $S$ is not minimal—a contradiction. Hence $c(S) \neq c(S \setminus t)$ for all $t \in S$, which implies that for each $t \in S$ there exists some color $c_t \in t$ (i.e. $c_t$ is a signature color of $t$) that no other team in $S$ has as a signature color, which implies $S$ is color-identifiable as desired. Since the minimal size (over all sports leagues) of such a set $S$ is $k$, since for $a<k$ we have $at<n$, we are done. $\blacksquare$

zacchro wrote: 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)$. Yeah!!400 posts!! We claim that $\text{g}(n,t)=\left\lceil \frac{n}{t}\right \rceil$ Let $\mathbb{S}$ be the smallest set containing which contains all of the colours. FTSOC,assume that $\mathbb{S}$ is not colour-identifiable which implies that there must be two teams which contain a common signature colour then we delete elements to form another set which contradicts minimality to $\mathbb{S}$ We deduce that $\text{g}(n,t)=\left\lceil \frac{n}{t}\right \rceil$ from the fact there are $n$ colours and atmost $t$ colours for each team.

The answer is $\lceil {\frac{n}{t}} \rceil$ and the construction is obvious (take team $1$ to have signature colors $(1,2, \cdots, t)$, team $2$ - $(t+1, \cdots, 2t)$, etc). For the bound, take the minimal set $S$ of teams whose signature colors cover all $n$ colors. Obviously $|S| \leq \lceil {\frac{n}{t}} \rceil$ since each team has at most $t$ signature colors. To see the assignment in $S$ is possible, note that there can't be a team whose all signature colors are signature colors of other teams, done.

By probabilistic method, if we remove as many teams without compromising the number of achievable signature colors, there exists a method to lose at most $t$ signature colors while selecting a signature color and removing all other teams containing that signature color. Details basically include looking at EV of colors with one instance plus those with multiple. All cases give EV at most $\frac{t}{n}$. Thus the answer is $\lceil \frac{n}{t} \rceil$, the equality case is disjoint teams of greedily maximal size.

The answer is $\left\lceil\frac{n}{t}\right\rceil$. To show this, we perform strong induction on $n$. The base case, where $n = 1$, is obvious, so let $n$ be arbitrary, and suppose that the statement is true for all $m < n$. Pick the color that is shared by the smallest number of teams, and then choose one of the teams with this color. There are now at least $n - t$ colors left to pick from, since the chosen team can eliminate up to $t$ colors from the available ones. Moreover, each team has up to $t$ colors, so the inductive hypothesis suggests that we have at least \[\left\lceil\frac{n - t}{t}\right\rceil + 1 = \left\lceil\frac{n}{t}\right\rceil\]teams to choose. This bound is sharp in the case where we have $n$ teams, where team $k$ has colors $k$ through $k + t$ (mod $n$).

We claim that the answer is $\lceil \frac{n}{t} \rceil$. By having team 1 have colors 1 through $t$, team 2 having $t+1$ through $2t$, and so on, clearly at most $\lceil \frac{n}{t} \rceil$ is achievable. The idea for the construction for $\lceil \frac{n}{t} \rceil$ is that when assigning a color to a team, there is more damage being done if the assigned color is popular, as it would eliminate more teams. Therefore we can employ the following algorithm: -Select the least popular color $C$ (if there are ties, choose any). Then, give that color $C$ to one of the teams $X$ that want it. -After doing so, remove all teams that also want $C$ (since they are no longer relevant), and additionally remove all $t$ colors that team $X$ wants including $C$ (since all of those colors can also no longer be used). We then claim that the all colors other than the $t$ colors that team $X$ wants are still wanted by at least one remaining non-removed team. Suppose FTSOC that there exists a color $D$ that was "accidentally" deleted. Then, all teams that want $D$ were deleted, so they also would have wanted $C$. However, since $C$ is not more popular than $D$ due to the way we chose it, the set of teams that want $C$ is the same as the set of teams that want $D$. However, since $D$ was not among the $t$ colors that were supposed to be deleted, it is not one of the colors that team $X$ wanted. Thus, $X$ wanted $C$ but not $D$, contradiction. Then, each iteration of this algorithm removes at most $t$ colors. Hence, we can always obtain at least $\lceil \frac{n}{t} \rceil$, so we are done.

The answer is $g(n,t)=\left\lceil \frac{n}{t} \right\rceil=k+1$. Let the colours be $\{1,2,\ldots, n\}$; to show that no larger $g(n,t)$ is attainable, consider the sets of team colours $S_i=\{(i-1)t+1, (i-1)t+2, \ldots, it\}$ for $i=1,\ldots, k$ and $S_{k+1}=\{kt+1, kt+2,\ldots, n\}$, each with at most $t$ colours and a union of $n$ colours. Thus, there are only $k+1$ teams to choose from so $g(n,t)\leq k+1$. To show we can always choose a colour-identifiable group of at least $g(n,t)=k+1$ teams, we use the following inductive strategy. Write $n=kt+a$ where $0<a\leq t$. Choose $S_1$ arbitrarily and assign to it an arbitrary signature colour in its set. Inductively, given $S_1, \ldots, S_m$ (with unique signature colours already assigned) their union has at most $\lvert S_1\rvert +\ldots +\lvert S_m\rvert = tm$ colours. If $m<k+1$ then $n=tm+a>tm$ so there exists a colour $1\leq c\leq n$ such that $c\not\in \bigcup_{i=1}^m S_i$. But there exists some team $S_{m+1}$ containing this colour, since the union of all the teams' colours contains $c$. We choose this to be our next set and assign it signature colour $c$. This process terminates only when $m\geq k+1$ so we can choose a colour-identifiable group of at least $k+1$ teams.

This problem comes very across as a bit superficial. Answer is $g(n, t) = \lfloor n/t \rfloor$; construction is to make all teams disjoint. For the bound, take a team $T$ that has a color $c$ used a minimal number of times (this detail will become important). Place $T$ in the set $S$, and first, delete all teams that use $c$. Claim. We don't lose any colors after this deletion. Proof. Suppose a color $c_1$ was lost; then all teams with color $c_1$ also have color $c$ as a signature, contradicting minimality of $c$. $\blacksquare$ Now, note that we can delete at most $t$ colors (those in $T$), and repeat the process. We will always be able to find a new team $T$ until all colors are exhausted, which proves the bound.

The answer is $\boxed{g(n,t)=\left\lceil \frac{n}{t} \right\rceil}$. To show this bound note that we are only guaranteed that $\left\lceil \frac{n}{t} \right\rceil$ teams participate in the tournament. Then simply disjointly partition the colors amongst the teams. To show that this is always attainable consider a set of all participating teams $P$. Call a color and a team connected, if the color is a signature color of the team. Now consider the following algorithm. Consider the least popular color $C$ and choose one of the $C$'s connected teams, call them $T$. Delete all of $T$'s signature colors, and delete all of the teams with signature color $C$. Place $T$ in $S$. Now we claim any color remaining in $P$ is still connected to some team. To see this assume some color still in $P$ has no remaining connected teams. Call this color $C'$. Clearly then the only teams that used $C'$ must have been teams that also liked $C$. However as $C$ was the least connected team, $C$ and $C'$ must have the exact same set of connections. However then $C'$ must have been deleted in the original algorithm as $T$ is connected to $C'$, which means it cannot be in $P$, contradiction. Therefore after one step of this algorithm, one team is placed in $S$, and there remain $n-t$ colors, as well as at least $\left\lceil \frac{n-t}{t} \right\rceil$ teams in $P$. Repeating this algorithm $\left\lceil \frac{n}{t} \right\rceil$ times, we have $\left\lceil \frac{n}{t} \right\rceil$ teams placed in $S$.

The answer is $\left \lceil \tfrac{n}{t} \right \rceil$. There could be as few as $\left \lceil \tfrac{n}{t} \right\rceil$ teams altogether, so this lowerbound is clearly necessary. It is sufficient for all possible color combinations; consider teams for which each of their colors also belong to another team. We delete each of these teams from consideration repeatedly – after each deletion, there are still $n$ distinct colors present over all remaining teams. When we stop we must be left with each team posessing a unique color that no other (remaining) team posesses. Thus we select all of these teams as our color-identifiable group to obtain at least $\left \lceil \tfrac{n}{t} \right\rceil$.

Answer. $\lceil \frac{n}{t} \rceil$. Construction. Consider the case where all teams have $t$ signature colors. A particular team's chosen color removes $t$ of the $n$ colors as possibilities for the chosen colors of other teams. In this case, a color identifiable set exists of size at most $\lceil \frac{n}{t} \rceil$. Bound. We do induction. Base case where $n = t$ is trivial. Suppose this is true for $1$ to $n - 1$ colors. Consider any team. If the team does not have any unique colors, simply delete the team. Keep doing so until a team is picked that has unique colors. For that team, pick the unique color and add the team to the color identifying set of size $\lceil \frac{n}{t} \rceil$ from the remaining teams (since as at most $t$ colors can not be picked amongst the other teams).

Consider the smallest set $R$ of teams such that the union of the signature colors of each team comprises of all $n$ colors. This set must be color-identifiable; otherwise, we simply remove the bad teams to get a smaller set. With $n$ colors in this set, and each team having at most 1 color, we have the bound $g(n,t) \ge \boxed{\lceil \tfrac nt \rceil}$, which can be achieved by giving each team $t$ colors distinct from all other teams. $\blacksquare$

The answer is $\boxed{\lceil\tfrac{n}{t} \rceil}$. An upper bound is easily constructed by considering the case where every team has $t$ colors. Since a particular team's chosen color removes $t$ colors from the possibilities for the chosen colors of other teams, a color identifiable set exists of size at most $\lceil \tfrac{n}{t} \rceil$. To prove a lower bound, we apply a greedy algorithm based on color. At each step, select the color $C_1$ with the fewest teams using it, and consider a team $T_1$ using $C_1$. Then, delete all of the colors $T_1$ uses and all teams that use $C_1$. We claim that any other color $D$ still has at least one team using it. Suppose FTSOC otherwise; all the teams that used $D$ were deleted, which means that they used $C_1$. Evidently, this means that the set of teams that use $C_1$ and the teams that use $D$ are the same. However, $D$ itself was not removed, implying that $T_1$ used $C$ but not $D$, a contradiction. Now, we can repeat this algorithm with the next color and team, $C_2$, and $T_2$. On top of this, we know that the algorithm grabs at most $t$ colors per step. Hence, we can always obtain at least $\lceil \tfrac{n}{t} \rceil$ colors, so we are done.

We claim that the answer is $g(n, t) = \lceil \tfrac{n}{t} \rceil$. Construction: Take $\lceil \tfrac{n}{t} \rceil$ teams and for each team, either give them $t$ new colours or finish the set of $n$ colours by giving them whatever colours are left out. Now, we will prove that, this is the maximum integer $g(n, t)$. If we have a team $T$ such that, for every colour $c$ in the set of signature colours for team $T$, colour $c$ is also a signature colour of some other team, then we remove it from the sports league, which doesnt change the value of $g(n, t)$ as it involves mainly two conditions: $n$ colours are involved and each team has at-most $t$ signature colours and this condition is preserved when we remove teams like $T$. Consider the resulting sports league $L$. For every team $T \in L$, there exists a colour $c \in T$ but $c \notin R$ for every other team $R \in L$ ($R \neq T$). Thus, for this team $T$, we assign it with colour $c$. We proceed this process till we get a set of teams $S$. Note that every colour is present in at-least one team in set $S$ (else, we can always take a team which has that colour as signature colour, assign it that colour and add it to $S$). Therefore, there are at-least $\lceil \tfrac{n}{t} \rceil$ teams in the set $S$ and we are done.

I claim the answer is $g(n,t)=\left \lceil \frac nt \right \rceil$ Proof: When constructing $S,$ every team $T_i$ we take can eliminate at most $t$ colors available to everyone else. This is done by choosing $t$ colors that are signature to $T_i$ and then letting no other team have those signature colors. Now we create two cases. Case 1: t does not divide n If $t \nmid n$ we can simply assign $t \lfloor \frac nt \rfloor$ colors to $\lfloor \frac nt \rfloor$ teams, let this set of teams be $T_u$. Then the rest of the colors gets assigned to team $T_a.$ then every team not touched so far gets assigned the same color $C_x$, and this color has already been assigned to $T_a.$ then choosing any sig color for all elements of $T_u$ and assigning $C_x$ to $T_a$ fulfills this bound. Case 2: t divides n If $t \mid n$ then for $\frac nt -1$ teams we assign them $t$ colors each such that no two teams share a sig color. Call this set $T_v$ Then choose a team $T_b$ and assign it the remaining $t$ colors, one of them being $C_y.$ Then for every team without a color we give it $C_y$ as their sig color. Then choosing elements of $T_v$ with arbitrary colors and choosing $T_b$ with $C_y$ makes the bound work. We cannot do better because of the definition of $t.$