CheshireOrb wrote: Let $n \ge 3$ be an integer and $S$ be a set of $n$ elements. Determine the largest integer $k_n$ such that: for every selection of $k_n$ $3-$subsets of $S$, there exists a way to color elements of $S$ such that none of the chosen $3-$subset is monochromatic. How many colors do we have?

Two colors.

Is there a translation error? Right now, I'm interpreting that if there ever are three elements colored the same, then $k_n$ doesn't exist... So $n=3,4$ only...

The coloring should depend on the $k_n$ subsets chosen. But this is still a very strange problem......... especially as #6

HaO-R-Zhe wrote: Is there a translation error? Right now, I'm interpreting that if there ever are three elements colored the same, then $k_n$ doesn't exist... So $n=3,4$ only... It's supposed to be "for each selection" not "for every selection".

Nice troll problem. I believe the answer should be $k_n = 6$ for $n \ge 7$ $k_5 = k_6 = 9$, $k_4 = 4$, $k_3=1$. In the style of 2012 C5, we call the two colors Asparagus and Byzantium. $n=3,4,5$ is easy. For $n=3,4$ choosing all sets works. For $n=5$, all ten is impossible, choosing $9$ has missing one set, so we color all three in the missing set Asparagus, and the remaining Byzantium. For $n=6$, Color 3 elements Asparagus and 3 elements Byzantium at random. Among the 20 colorings, exactly 18 violate the chosen 9 sets. So a coloring exists. For $n \ge 7$, consider the following 7 sets: $\{1,2,3\}, \{1,4,5\}, \{1,6,7\}, \{2,5,6\}, \{3,5,7\}, \{2,4,7\}, \{3,4,6\}$, each element appeared exactly 3 times. WLOG, more elements were colored Asparagus than Byzantium, then if two or fewer elements are colored Asparagus, at most six sets contain these two Asparagus elements, with the last set Byzantium. If exactly three elements are colored Asparagus, WLOG (because the chosen sets are completely symmetrical) 1 is colored Asparagus. We would require $\{2,5,6\}, \{3,5,7\}, \{2,4,7\}, \{3,4,6\}$ to be not monocromatic. If $2$ is Asparagus, then $3$ must be Asparagus, same for $4$ and $5$, as well as $6$ and $7$. But then we have a monochromatic Asparagus set. It follows that $k_n \le 6$ for $n \ge 7$ Finally, we will show that $k_n = 6$ works (there is actually very little to stop us). We consider the most appeared element. If the most number of appearances is less than or equal to 2, then we color a random such element Asparagus, within the 3-subset, if another element also appears twice, we color it Byzantium, and repeat. This coloring wins. If the most number of appearances is more than or equal to 4, if the remaining has overlap, we can ensure the overlapping element is Asparagus, all remaining elements are Byzantium and the most appeared element is Asparagus. If there is no overlap, just choose one from each such that they are not in the same subset (or do not appear at all) as the most appeared element. Color the chosen ones Asparagus and the remaining Byzantium, and the most appeared element Asparagus. If the most number of appearances is three, we call the set of the remaining three 3-subsets as $T_1, T_2, T_3$. We are always able to choose $t_1 \in T_1$, $t_2 \in T_2$, and $t_3\in T_3$ such that $t_i, t_j$ are not in the same set as $X$. Note that $t_i$ and $t_j$ could be the same. Therefore, color $t_1, t_2, t_3$ as Asparagus. Color $X$ as Asparagus and all the remaining as Byzantium and we win.

Still, I don't think that this P6 was too hard though. I think that the only problem is to find the correct $k_n$ for $n \ge 7$ and after that, it's easy