We are given 5040 balls in k different colors, where the number of balls of each color is the same. The balls are put into 2520 bags so that each bag contains two balls of different colors. Find the smallest k such that, however the balls are distributed into the bags, we can arrange the bags around a circle so that no two balls of the same color are in two neighboring bags.
Problem
Source: Turkish TST 2005, P6
Tags: combinatorics proposed, combinatorics
26.03.2019 09:17
\bump anyone?
29.01.2022 23:01
Bumping. Any solution?
02.02.2022 12:50
Bumping again.
02.02.2022 15:34
I’m guessing the answer is 6, because the cases 1, 2, 3, 4, 5 can be checked not to work very easily by forming triples (1, 2) (2, 3) (3, 1), where 6 just barely passes, however I cannot yet prove that 6 works.
03.02.2022 05:09
While not sure, the answer may be 11 per this.
03.02.2022 05:34
grupyorum wrote: While not sure, the answer may be 11 per this. ??? Let $c$ $-$ number of balls of each color (by the condition of the problem all numbers are equal), then $kc=5040$, hence $k$ must divide $5040$, so the answer obviously cannot be $11$.
12.02.2022 06:30
Fun problem! I hope someone else can find a shorter solution to this, but I think it's worth the read. We claim that the answer is $\boxed {6}$ colors. First, to prove that five colors can fail, label the colors $A$ through $E$. Note that there are $1008$ balls of each color. Now pair up the balls so that every ball of color $A$ gets paired up with color $B$ (and vice versa), and we have the same number of bags with the combinations $CD$, $DE$, and $EC$. Then there are $1008$ bags with $AB$, and $504$ bags left with each of the combinations without ball $A$ or $B$ (because $1008 + 504 \cdot 3 = 2520$). Now let's try to arrange these bags in a circle subject to the problem's conditions, in clockwise order. Suppose we start with a bag with $AB$. Then the next bag could be any of the combinations $CD$, $DE$, or $EC$. However, after that bag (the one without the colors $A$ or $B$), we would have to select a bag with the combination $AB$ again, because selecting any two out of the three remaining combinations that are not $AB$ would require them to have a color in common, which is not allowed. We can repeat the same logic again to this bag with $AB$ to get that every second bag in the circle must have the color combination $AB$, but since there are $2520$ bags in the circle, then that would imply that there are $2520 : 2 = 1260$ bags with the combination $AB$ for this task to succeed, which is more than the $1008$ we only have, contradiction. Therefore, we have shown that five colors is not sufficient $\square$ To show that six colors can work, we will construct a valid arrangement with $k$ balls for each of the six different colors, for any positive integer $k$, using induction. Label the colors $A$ through $F$.
Now for $k \geq 3$, suppose the statement is true for both $k-1$ and $k-2$ from the base case. We will show it must be true for $k$ as well. First, we will prove an important lemma Lemma: For every random grouping of the balls, at least one of the following is true: i) There are three bags with a ball of every color (such as $AB$, $CD$, $EF$ for example) ii) There are three bags with all the possible combinations of balls from three colors, such as $AB$, $BC$, and $CA$, and three more bags with all the possible of combinations of balls from the three remaining colors (which would be $DE$, $EF$, and $FD$ in this case) Proof: Suppose otherwise. Call a combination relevant if there exists a bag with that combination for a given random grouping. Assume WLOG that both $AB$ and then $CD$ are relevant (because there obviously must exist a bag without either $A$ or $B$). Then if $EF$ can't be relevant as that would make statement i) true. Now notice that at least two combinations involving colors $E$ and $F$ each, need to be relevant because, for example, we cannot exclusively pair up every ball of color $E$ with a ball of color $A$ as some have already been paired up with $B$. Now suppose WLOG $EA$ was relevant. Notice that $FB$ can't be relevant as that would make statement i) true with the bags $EA$, $FB$, and $CD$. Also, if we made $EB$ relevant, then by the same logic $FA$ can't be relevant either, so then both $FC$ and $FD$ would have to be relevant. But then that would make statement ii) true with the combinations $EA$, $EB$, $AB$ and $FC$, $FD$, $CD$, which means $EB$ cannot be relevant either. Therefore, as $EB$ can't be relevant, then one of $EC$ or $ED$ is. Suppose WLOG it's $EC$. Applying the same logic as before tells us that neither $FD$ nor $ED$ can be relevant, which also means that both $FA$ and $FC$ must be relevant those are the only two remaining colors we can pair $F$ up with. Finally, note that $BD$ can't be relevant as that would make i) true with the combinations $BD$, $FC$, and $EA$. Now if we take a look at the set of the colors $\{B, D, E, F\}$, note that we have essentially proven that any pair of two colors in this set cannot be relevant. In other words, all the relevant pairs, or bags in our random grouping, have at least one of the colors not in this set, which only leaves $A$ or $C$ remaining. But clearly this cannot be possible because only one-third of the balls are either color $A$ or $C$, and as there are only two balls in a bag, then at most two-third of the bags will contain either color $A$ or $C$, not all of them, contradiction! Therefore, the lemma is true $\square$ Now we are ready to finish with some casework on the statement that is assumed to be true. If we assume that statement i) is true, then assume WLOG that we have three bags with $AB$, $CD$, and $EF$. By the inductive hypothesis, suppose that we have already arranged all but those three bags in a circle subject to the problem conditions. Now in the pre-existing circle, there must be a bag with a ball of either color $A$ or $B$, followed by a bag with neither of those colors (because not all bags will have either color $A$ or $B$). Now the bag with a ball of either color $A$ or $B$, note that we can successfully put either bag $CD$ or $EF$ next to it, because one of the colors is already either $A$ or $B$, neither color found in bag $CD$ or $EF$, and the second color can only eliminate at most one of these bags, since the colors in bags $CD$ and $EF$ do not overlap. Therefore, in a gap between a bag with a ball of either colors $A$ or $B$ and a bag either neither of those colors, we first place the bag $AB$ next to the bag with neither of those colors, then we can place either one of the bags $CD$ or $EF$ next to the bag with a ball of either color $A$ or $B$, and lastly we can place the third and final bag in between the two bags we have just placed, so the inductive step is complete in this case. If we assume that statement ii) is true, then assume WLOG that we have three bags with $AB$, $BC$, and $CA$ (call this group one), and three more bags with $DE$, $EF$, and $FD$ (call this group two). By the inductive hypothesis, suppose that we have already arranged all but those six bags in a circle subject to the problem conditions. Like we've said before, in the pre-existing circle, there must be a bag with a ball of either color $A$ or $B$, followed by a bag with neither of those colors. Now the bag with a ball of either color $A$ or $B$, note that we can successfully put one of the bags $DE$, $EF$, or $FD$ next to it, because one of the colors is already either $A$ or $B$, neither color found in any of those bags, and also no color is found in all three of those bags, so the second color cannot eliminate all three bags from being valid. Therefore, in a gap between a bag with a ball of either colors $A$ or $B$ and a bag either neither of those colors, we first place the bag $AB$ (which is in group one) next to the bag with neither of those colors, then we can place one of the bags $DE$, $EF$, or $FD$ (which is in group two) next to the bag with a ball of either color $A$ or $B$. As for the last four bags, note that we can simply put the bags in between the two bags we have already placed so long as the bags alternate from group one to group two, as no bag from group one shares a color with a bag from group two. This also means that the first and last bags should be from different groups as there are an even number of bags in between, which we've already successfully constructed from before, so the inductive step for this case is complete as well. In either case, we have found a way to place $k$ balls each from six different colors in a circle subject to the problem's conditions, as desired $\blacksquare$