When replying to the problem, I ask that you make posts for solutions and submit comments, jokes, smilies, etc. separately. Furthermore, please do not "hide" any portion of the solution. Please use LaTeX for posting solutions. Thanks.

this problem can be re-cast and reworded as follows: consider a set of $n$ points(colors). we need a collection of $8$ blocks(boxes) each of size $6$, such that any two points co-occur in atmost one block.Find the least possible $n$ for this. now assume that some point occurs in $3$ blocks, say the point $1$ and the blocks being $\{1,2,3,4,5,6\},\{1,7,8,9,a,b\},\{1,c,d,e,f,g\}$. in any of the other $5$ blocks, there is atmost one element from each of the above three blocks, so if there are $k$ other elements in the set, we need a collection of $5$ triples such that no pair occurs in more than one block. so, counting the number of triples $(x,y,B)$ where $x,y$ are among these other $k$ points and $B$ is a block containing them both, we get $k(k-1)/2\ge 3\cdot 5\Rightarrow k\ge 6$. if $k=6$ then it is easy to see that if $\{\alpha,\beta,\gamma\}$ is one such triple, then any of the other triples contain atmost one element from this set and hence necessarily two from the remaining three(call them $\delta,\epsilon,\mu$). But then, among the $4$ other sets there will necessarily be one containing the same pair from the other three. So $k=6$ is not possible. For $k=7$ we however have the Fano Plane and such triples exist, so $n\leq 23$.(i.e. if there is some point contained in three blocks then we can do so with $n=23$). If there is some element in atleast $4$ blocks, then as above we would have to pick up $4$ distinct pairs from a $k$-set and so there $k\ge 4$. Finally if every element occurs in atmost $2$ blocks and say it were possible that $n=22$, then the same as above leads us to choosing from a $11$-set, $6$ subsets of size $4$ and with no pair occuring in more than one such subset. But then one of the elements of $\{2,3,4,5,6,7,8,9,a,b\}$( occuring along with $1$) must occur in three sets and that is a contradiction to our assumption. So $n=23$ is the least possible such $n$.

I am confused, as to how you got to the point, 1, being in only three blocks. I thought about this, and arrived at 16 by saying, to satisfy the part about "no two colors occur together in more than one box," I thought that one could say in eight boxes, there are six balls, so 15 two-color combinations, for a total of 8*15 or 120 as the total number of different combinations. This would mean that with sixteen colours, one has 16*15/2 or 120 colour combinations.

Try to actually construct an example where only $ 16$ colors are used. It's easy to prove $ 16$ is a lower bound, like you did, but in fact you need many more colors than that. $ 23$ is the correct answer.

I got 21, er... what's wrong with the following configuration. Box number 1 2 3 4 5 6 7 8 Ball number 1 1 6 6 6 6 6 6 6 2 2 7 11 11 11 11 11 11 3 3 8 12 15 15 15 15 15 4 4 9 13 16 18 18 18 18 5 5 10 14 17 19 20 20 20 6 6 11 15 18 20 21 21 21 where the bold numbers 1 through 6 represents the ball number in each of the box, and the bold numbers from 1 through 8 are the numbers of the box. The other numbers represent the number of a particular color. All my sources tell me the answer is 23, but I don't get what's wrong with this...

Don't you have colors $ 6$ and $ 11$ together in a box lots of times? You can only have that happen once.

Here is my solution, I got 21 as an answer. Denote different colors with different letters, A-Z. The first box, then, abiding by the first rule, has colors $ ABCDEF$ We know that no two colors occur together in more than one box. To minimize the number of colors used while abiding to the given rules, we have one letter in box 2 that is in common with box 1, and the rest different and new: $ AGHIJK$ We apply the same logic to generate the third box. This time, we have one letter in the third box in common with the first box, and another from the second box. $ BGLMNO$ For the fourth box, we have one color in common with the first box, one in common with the second box, and one in common with the third box. $ CHLPQR$ For the fifth box, we have one color in common with the first box, one with the second, one with the third, and one with the fourth box. $ DIMPST$ For the sixth box, we have one color in common with boxes 1-5 each, and one original color $ EJNQSU$ For the seventh and eighth boxes, we can take combinations of the previously defined colors. So, we have letters A-U, or 21 colors.

Arvind_sn wrote: we can take combinations of the previously defined colors. What combinations?

Could somebody check this solution? I wasn't sure as to how to "rigorize" it.

Is this even correct, and if so, how can I improve it?

Let $f(k)$ be the number of times color $k$ appears among the eight boxes. Then $\sum_{k=1}^{n}f(k)=8\cdot6=48$ and since each pair of boxes intersects at most once, \[\binom{8}{2}\ge\sum_{k=1}^{n}\binom{f(k)}{2}\ge n\binom{\frac{48}{n}}{2},\]where the second inequality follows by convexity. Thus \[28\ge\frac{48}{2}\frac{48-n}{n}\implies n\ge\frac{288}{13}>22,\]whence $n\ge23$. The construction is easy after noting that the optimal bound occurs when $f(1)=f(2)=3$ and $f(3)=\cdots=f(23)=2$ (WLOG).

@math154: not much of a point but after defining $f(k)$, another way to finish it off is to see \[28=\binom{8}{2}\ge\sum_{k=1}^{n}\binom{f(k)}{2}\Rightarrow \sum_{k=1}^{n}f(k)^2\le 28\cdot 2+48=104\] Now Cauchy gives $104\geq \sum_{k=1}^{n}f(k)^2\geq \frac{(\sum_{k=1}^{n}f(k))^2}{n}$, so $n>22$.

What exactly is being counted in math154's solution? (the $\binom82$ and $\sum_{k=1}^n\binom{f(k)}{2}$)

$\dbinom{8}{2}$ counts the number of ways to select two boxes. $\sum_{k=1}^n \dbinom{f(k)}{2}$ counts the number of ways to select two balls of the same color. If $\sum_{k=1}^n \dbinom{f(k)}{2} > \dbinom{8}{2}$ then there are two ways to pick a ball of the same color from each of two bins which violates the problem condition, so it follows $\sum_{k=1}^n \dbinom{f(k)}{2} \le \dbinom{8}{2}$

xpmath wrote: The following is one example of 23 colors being used, where we use the first 23 natural numbers to represent the colors $ \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 7 & 8 & 9 & 10 & 11 \\ 2 & 7 & 12 & 13 & 14 & 15 \\ 3 & 8 & 12 & 16 & 17 & 18 \\ 4 & 9 & 13 & 16 & 19 & 20 \\ 5 & 10 & 14 & 17 & 19 & 21 \\ 6 & 11 & 15 & 18 & 20 & 21 \\ 1 & 13 & 17 & 20 & 22 & 23 \end{array}$ I know this is pretty old, but just for reference, this configuration is actually incorrect, as (13, 20) appears in both rows 5 and 8. A correct configuration would be: $ \begin{array}{cccccc} 1 & 3 & 12 & 13 & 21 & 22 \\ 1 & 4 & 11 & 15 & 19 & 23 \\ 1 & 5 & 10 & 14 & 18 & 20 \\ 2 & 3 & 9 & 11 & 18 & 23 \\ 2 & 4 & 8 & 12 & 17 & 20 \\ 2 & 5 & 7 & 13 & 16 & 19 \\ 6 & 7 & 9 & 14 & 17 & 21 \\ 6 & 8 & 10 & 15 & 16 & 22 \end{array}$

How did people come up with the construction? math154 wrote: The construction is easy after noting that the optimal bound occurs when $f(1)=f(2)=3$ and $f(3)=\cdots=f(23)=2$ (WLOG). Why is this optimal?

The answer is $n = 23$. Shown below is a construction using that many colors, which we call $\{1,2,\dots,15,a,\dots,f,X,Y\}$. \[ \begin{bmatrix} X & X & X & 1 & 2 & 3 & 4 & 5 \\ 1 & 6 & 11 & 6 & 7 & 8 & 9 & 10 \\ 2 & 7 & 12 & 11 & 12 & 13 & 14 & 15 \\ 3 & 8 & 13 & Y & Y & Y & a & b \\ 4 & 9 & 14 & a & c & e & c & d \\ 5 & 10 & 15 & b & d & f & e & f \end{bmatrix} \] We say a color $x$ is overrated if it is used at least three times. First we make the following smoothing argument. Claim: Suppose some box contains a ball of overrated color $x$ plus a ball of color $y$ used only once. Then we can change one ball of color $x$ to color $y$ while preserving all the conditions. Proof. Obvious. (Though the color $x$ could cease to be overrated after this operation.) $\blacksquare$ By applying this operation as many times as possible, we arrive at a situation in which whenever we have a box with an overrated color, the other colors in the box are used twice or more. Assume now $n \le 23$ and the assumption; we will show the equality case must of the form we gave. Since there are a total of $48$ balls, at least two colors are overrated. Let $X$ be an overrated color and take three boxes where it appears. Then there are $15$ more distinct colors, say $\{1, \dots, 15\}$ lying in those boxes. Each of them must appear at least once more, so we arrive at the situation \[ \begin{bmatrix} X & X & X & 1 & 2 & 3 & 4 & 5 \\ 1 & 6 & 11 & 6 & 7 & 8 & 9 & 10 \\ 2 & 7 & 12 & 11 & 12 & 13 & 14 & 15 \\ 3 & 8 & 13 \\ 4 & 9 & 14 \\ 5 & 10 & 15 \\ \end{bmatrix} \]up to harmless permutation of the color names. Now, note that none of these $15$ colors can reappear. So it remains to fill up the last five boxes. Now, there is at least one more overrated color, distinct from any we have seen; call it $Y$. In the three boxes $Y$ appears in, there must be six new colors, and this gives the lower bound $n \ge 1 + 15 + 1 + 6 = 23$ which we sought, with equality occurring as we saw above. Remark: [Partial progresses] The fact that $\binom{16}{2} = 120 = 8 \binom{6}{2}$ (suggesting the bound $n \ge 16$) is misleading and not that helpful. There is a simple argument showing that $n$ should be much larger than $16$. Imagine opening the boxes in any order. The first box must contain six new colors. The second box must contain five new colors, and so on; thus $n \ge 6 + 5 + 4 + 3 + 2 + 1 = 21$. This is sharp for seven boxes, as the example below shows. \[ \begin{bmatrix} 1 & 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 7 & 7 & 8 & 9 & 10 & 11 \\ 3 & 8 & 12 & 12 & 13 & 14 & 15 \\ 4 & 9 & 13 & 16 & 16 & 17 & 18 \\ 5 & 10 & 14 & 17 & 19 & 19 & 20 \\ 6 & 11 & 15 & 18 & 20 & 21 & 21 \end{bmatrix} \]However, one cannot add an eight box, suggesting the answer should be a little larger than $21$. One possible eight box is $\{1,12,19,a,b,c\}$ which gives $n \le 24$; but the true answer is a little trickier.

The answer is $n = 23$. First, we provide the following construction (where distinct colors are represented as positive integers): $$B_1 = \{1, 2, 3, 4, 5, 6\};$$$$B_2 = \{1, 7, 8, 9, 10, 11\};$$$$B_3 = \{1, 12, 13, 14, 15, 16\};$$$$B_4 = \{17, 2, 7, 12, 18, 19\};$$$$B_5 = \{17, 3, 8, 13, 20, 21\};$$$$B_6 = \{17, 4, 9, 14, 22, 23\};$$$$B_7 = \{5, 10, 15, 18, 20, 22 \};$$$$B_8 = \{6, 11, 16, 19, 21, 23\}.$$Now, we prove this is the smallest possible satisfactory value of $n$. If $n \le 23$, then Pigeonhole implies either: some color will appear at least $4$ times, or at least $2$ distinct colors will each appear $3$ times. Case 1: Suppose color $1$ appears at least $4$ times. WLOG, we can let $B_1$ through $B_4$ be filled as follows: $$B_1 = \{1, 2, 3, 4, 5, 6\};$$$$B_2 = \{1, 7, 8, 9, 10, 11\};$$$$B_3 = \{1, 12, 13, 14, 15, 16\};$$$$B_4 = \{1, 17, 18, 19, 20, 21\}.$$Now, notice the number of new colors that appear in $B_i$ is no less than $6 - (i - 1) = 7 - i$, as we can only reuse up to $i-1$ colors from $B_1, B_2, \ldots, B_{i-1}$ in $B_i$. This means at least $7 - 5 = 2$ new colors will appear in $B_5$, bringing our total number of distinct colors to no less than $23$. Thus, we cannot achieve a smaller value of $n$ for this case. Case 2: Suppose color $1$ and color $2$ both appear exactly $3$ times. (If either color appeared more than $3$ times, then case $1$ takes precedent.) Now, we have $2$ sub-cases: $\bullet$ 1 and 2 Do Appear Together In One Box: WLOG, we can fill $B_1, B_2, B_3$ as follows: $$B_1 = \{1, 2, 3, 4, 5, 6\};$$$$B_2 = \{1, 7, 8, 9, 10, 11\};$$$$B_3 = \{1, 12, 13, 14, 15, 16\}.$$Now, let color $2$ be contained in $B_4$ and $B_5$. Observe we cannot reuse an element from box $1$ in $B_4$, as color $2$ is contained within both boxes. Thus, at least $5 - (3 - 1) = 3$ new colors will appear in $B_4$. Similarly, no less than $5 - (4 - 2) = 3$ new colors will appear in $B_5$. Now, by previously proven logic from case $1$, we know at least $7 - 6 = 1$ new color will appear in $B_6$. This brings our total amount of distinct colors to no less than $16 + 3 + 3 + 1 = 23$. Thus, we cannot achieve a smaller value of $n$ for this sub-case. $\bullet$ 1 and 2 Do Not Appear Together In One Box: WLOG, we can let color $2$ be contained in $B_4, B_5, B_6$, and fill $B_1, B_2, B_3$ as follows: $$B_1 = \{1, 3, 4, 5, 6, 7\};$$$$B_2 = \{1, 8, 9, 10, 11, 12\};$$$$B_3 = \{1, 13, 14, 15, 16, 17\}.$$Notice no less than $5 - 3 = 2$ new colors will appear in $B_4$, at least $5 - (4 - 1) = 2$ new colors will appear in $B_5$, and at least $5 - (5 - 2) = 2$ new colors will appear in $B_6$. Thus, our total number of distinct colors is no less than $17 + 3 \cdot 2 = 23$, which means we cannot achieve a smaller value of $n$ for this sub-case. We've shown no value of $n$ less than $23$ can be achieved for all possible cases, implying $23$ is the minimum as desired. $\blacksquare$ Remarks: At first, I found an easy construction for $n = 24$ and guessed this was the minimum. Unfortunately, I repeatedly failed to show this (cause it's false lol) via casework on the first $6$ boxes and induction. I did manage to prove, however, that $24$ is the minimum when we use a modified version of the Greedy Algorithm for the first $7$ boxes ($6, 5, \ldots, 1, 0$ new colors for each additional box). Once I realized this question felt pigeonhole-esque (in my eyes), I noticed having at most $23 = \frac{6 \cdot 8}{2} - 1$ colors implies either: one color will appear at least $4$ times, or $2$ distinct colors will each appear at least $3$ times. (For some reason, I still thought $24$ was the minimum at this point, so I was trying to use contradiction for $n \le 23$.) This kills the problem, and the rest of my solution is just careful minimization of the number of new colors.

The answer is 23. I'm too lazy to show an example of how it can be achieved. If no color appears more than twice, then we need at least 24 colors, but we can do better. If a color appear more than 3 times we can show that we would need more than 23 colors. Now, WLOG color one appears in three boxes. We need 15 other colors for the remaining balls in these boxes. Out of everyone of the remaining 5 boxes at most three of the balls in them can be covered with the first 16 colors, so we need to color 3 more balls in 5 different boxes. Doing similar manipulations, we would need 7 more colors for these balls, for a total of 23.

We claim the answer is 23. The following construction works https://www.dropbox.com/s/lidr5lq4dzowf1e/23construct.jpeg?dl=0 To prove this is optimal, let $c_1,c_2,\ldots, c_n$ be the number of times that each color appears. Note that we have $\sum_{i=1}^n c_i=48$. Now, we count $X$, the number of ordered pairs $(B_i,B_j)$ where $B_i,B_j$ share a color. Upper bound: select $B_i$ first, and it can share colors with any other box, so $X\leq 8\cdot 7 = 56$. Secondly, we have that $X = \sum_{i=1}^n 2\binom{c_i}{2}$. Thus, \[56\geq \sum_{i=1}^n (c_i)(c_i-1) \Longrightarrow 104\geq \sum_{i=1}^n c_i^2\geq \frac{\left(\sum c_i\right)^2}{n} = \frac{48^2}{n}\]Thus, $n\geq \frac{12\cdot 24}{13}> 22$, so $n\geq 23$ and we're done.

bash. Let $S$ denote the set of colors, so $|S| = n$. Because no two balls in the same box are the same color, the boxes correspond to subsets $S_1,S_2,\cdots,S_8$ of $S$, each with cardinality $6$ satisfying that for any $i\ne j$, $|S_i\cap S_j| \le 1$. We seek to minimize $n$. Observe that \[|S_1\cup S_2\cup S_3\cup S_4\cup S_5\cup S_6\cup S_7| \ge \sum_{i=1}^7 |S_i| - \sum_{1\le i<j\le 7}|S_i\cap S_j| = 7\cdot 6 - \binom 72 = 21.\]Letting $1$ denote when color $i$ is in $S_j$ in the following table for $1\le i\le 23$, we present a construction for $n=23$. \begin{tabular}{c|c|c|c|c|c|c|c|c} Color&$S_1$&$S_2$&$S_3$&$S_4$&$S_5$&$S_6$&$S_7$&$S_8$\\ \hline 1&1&1&1&1&&&& \\ \hline 2&1&&&&1&&&\\ \hline 3&1&&&&&1&&\\ \hline 4&1&&&&&&1&\\ \hline 5&1&&&&&&&1\\ \hline 6&1&1&&&&&&\\ \hline 7&&1&&&1&&&\\ \hline 8&&1&&&&1&&\\ \hline 9&&1&&&&&1&\\ \hline 10&&1&&&&&&1\\ \hline 11&&&1&&1&&&\\ \hline 12&&&1&&&1&&\\ \hline 13&&&1&&&&1&\\ \hline 14&&&1&&&&&1\\ \hline 15&&&1&1&&&&\\ \hline 16&&&&1&1&&&\\ \hline 17&&&&1&&1&&\\ \hline 18&&&&1&&&1&\\ \hline 19&&&&1&&&&1\\ \hline 20&&&&&1&1&&\\ \hline 21&&&&&1&&1&\\ \hline 22&&&&&&1&&1\\ \hline 23&&&&&&&1&1\\ \hline \end{tabular} We claim that $n<23$ fails. Let $T=\{1,2,\cdots,8\}$. Remark that $n\le 20$ automatically fails, so assume $21\le n\le 23$. Let the $n$ colors have appear $a_1,a_2,\cdots,a_n$ times respectively. Observe that by the initial bound rearranged \[\sum_{i,j\in T\setminus \{k\}, i\ne j}|S_i\cap S_j| \ge 7\cdot 6 - n = 42-n\]for all $k\in T$. Remark that \[28\ge \sum_{i=1}^n \binom{a_i}2 = \sum_{i,j\in T,i\ne j} |S_i\cap S_j| = \frac 16\cdot \sum_{k\in T} \sum_{i,j\in T\setminus \{k\}, i\ne j}|S_i\cap S_j| \ge \frac 43\cdot (42-n) \ge \frac 43\cdot (42-23) > 25.\]Thus the sum is at least $26$. We also have $\sum_{i=1}^n a_i = \sum_{i=1}^8 |S_i| = 48$. Suppose $n=21$ for now, so we get $28=\sum_{i=1}^n \binom{a_i}2$, hence \[\sum_{i=1}^n (a_i-1)^2 = \sum_{i=1}^n \left[2\binom{a_i}2 - a_i + 1\right] = 56-48+n=29.\]Let there be $b_t$ instances of $a_i=t$ for $1\le t\le 6$, noting that $b_t$ would be $0$ for $t>6$. Then we have \[b_1+2b_2+3b_3+4b_4+5b_5+6b_6 = 48\]and \[b_2+4b_3+9b_4+16b_5+25b_6 = 29.\]As $\sum_i b_i = 21$, the first equation rewrites as \[b_2+2b_3+3b_4+4b_5+5b_6 = 27.\]It is then clear that $b_6=1$ yields contradiction, as we either get $b_3=1$ and $b_i=0$ for $i\ne 1,3,6$ or $b_2=4$ and $b_i=0$ for $i\ne 1,2,6$, neither of which work. Then we write the equations \[b_2+2b_3+3b_4+4b_5 = 27\]and \[b_2+4b_3+9b_4+16b_5 = 29.\]Subtract the first equation from the second so we instead work with the equations \[2b_3+6b_4+12b_5 = 2\]and \[b_2+4b_3+9b_4+16b_5=29.\]We must have $b_3=1$ and $b_4=b_5=0$, so then $b_2=29-4 = 25$, but this is absurd because then $b_2>21$. So suppose $n=22$. As $\frac 43\cdot (42-22) > 26$, we have \[27\le \sum_{i=1}^n \binom{a_i}2 \le 28.\]Write \[28=54-48+n\le \sum_{i=1}^n (a_i-1)^2 = \sum_{i=1}^n \left[2\binom{a_i}2 - a_i+1\right] \le 56-48+n = 30.\]So define the $b_i$ as before so we have the inequality \[28\le b_2+4b_3+9b_4+16b_5+25b_6 \le 30\]and the equation \[b_2+2b_3+3b_4+4b_5+5b_6 = 48 - 22 = 26.\]Then we have \[2\le 2b_3+6b_4+12b_5+20b_6\le 4,\]hence $b_3 \in \{1,2\}$ and $b_4=b_5=b_6=0$. Then $b_2+b_3 = 26-b_3\ge 24$, absurd again, so we are done.

The answer is $23$ colors, for which we will provide a construction at the end of the proof that $n\ge 23$. Let the colors be $C_1,C_2,\dots, C_n$ and let $c_i$ be the number of times $C_i$ appears. Note that the number of pairs of boxes is $28.$ Now, any pair of boxes may not share two colors, and then number of pairs of balls which are the same color is \[\binom{c_1}{2}+\dots + \binom{c_n}{2}.\]This number may not exceed $28$. Since $\tbinom{c_1}{2}$ is a convex function, we can apply Jensen's to get \[28\ge \binom{c_1}{2}+\dots + \binom{c_n}{2}\ge n \cdot \binom{\tfrac{c_1+\dots + c_n}{n}}{2}.\]Thus, $56\le n\left(\tfrac{48}{n}\right) \left(\tfrac{48}{n}-1\right)=48\left(\tfrac{48}{n}-1\right)\implies \tfrac{13}{6}\le \frac{48}{n}\implies n\ge \tfrac{48\cdot 6}{13}>22.$ Thus, $n\ge 23$. We provide the following construction: \begin{align*} ABCDEF\\ AGHIJK\\ ALMNOP\\ QBGLRS\\ QCHMTU\\ QDINVW\\ EJORTV\\ FKPSUW \end{align*}