Combinatorial problem - coloured balls I have balls with $n$ colors, $n ≥ 3$, and I want to put them into boxes.
1/ Each box must have at last 2 colors.
2/ For every pair of colors and for every color in that pair there is a box that contains that color and doesn't contain the other one, i.e. $\forall \mathrm{color1} \, \forall \mathrm{color2} ≠ \mathrm{color1} \, \exists \mathrm{box}:(\mathrm{color1} \in \mathrm{box} \land \mathrm{color2} \notin \mathrm{box}) $
Take the product of the number of balls in a box, over all the boxes. Call this $f(n)$. What is the minimum value of $f(n)$?
It is easy to see $f(2n) ≤ [f(n)]^2$
For instance, for any n, here is a possible division into boxes:
$\{1,2\},\{2,3\},...,\{n-1,n\},\{1,n\}$, so $f(n) ≤ 2^n$.
However one can do better. For $2n$ one can divide into boxes as follows:
$\{1,...,n\},\{n+1,...,2n\},\{1,n+1\},\{2,n+2\},...,\{n,2n\}$
so $f(2n) ≤ n^2 \cdot 2^n$
And I can do (somewhat) better than this. Basically I'm looking for an upper bound if it's low, or a lower bound if it's high - an exact formula isn't really needed.
 A: Let's number the colors from $0$ to $mn - 1$.
We split the boxes into two categories:
The first category contains the following boxes:
$A_0:\{ 0, n, 2n,3n,...,(m-1)n \}$
$A_1:\{1,n+1,2n+1,...,(m-1)n+1\}$
$A_2:\{2,n+2,2n+2,3n+2,...,(m-1)n+2\}$
$\ldots$
$A_{n-1}:\{ n-1, 2n-1,3n-1,...,mn-1 \}$
The second category contains the boxes:
$B_0:\{0, 1,2,3,4,...,n-1\}$
$B_1:\{ n,n+1,n+2,...,2n-1 \}$
$\ldots$
$B_{m-1}:\{(m-1)n, (m-1)n+1,(m-1)n+2,...,mn-1\}$
If $n,m \ge 2$ then the first condition is satisfied.
Let's take two colors $c_1$ and $c_2$ whose Euclidian division by $n$ is $qn + r$ and $q'n + r'$ respectively.
The two colors are distinct so $q \neq q'$ or $r \neq r'$.
If $q \neq q'$ then $c_1 \in B_q$ and $c_2 \not\in B_q$.
If $r \neq r'$ then $c_1 \in A_r$ and $c_2 \not\in A_r$.
Either way, the second condition is satisfied.
The number of balls in each box in the first category is $m$ and there are $n$ boxes so the product is $m^n$.
The number of balls in each box in the second category is $n$ and there are $m$ boxes so the product is $n^m$.
As such, $f(mn) \le n^m \cdot m^n$ for all $m,n \ge 2$.
