# Balls in monochromatic bins

Suppose we have a collection of $$m$$ balls in $$k$$ different colors. Let $$b_i$$ be the number of balls with color $$i$$, so $$\sum_{i=1}^k b_i = m$$. Assume we have $$n$$ bins with capacities $$c_1, \dots, c_n$$, such that $$\sum_{j=1}^n c_j \geq m$$.

We say an assignment of balls into bins is monochromatic if it satisfies three conditions:

(I) Each ball is assigned to exactly one bin.

(II) Number of balls assigned to a bin is at most its capacity.

(III) A bin is either empty or monochromatic, i.e. it does NOT contain two balls with different colors.

Question: How do we decide for a given collection of $$m$$ balls with $$k$$ colors, and $$n$$ bins with capacities, whether there is a monochromatic assignment? Is this problem $$NP$$-hard?

For example if we have two balls $$b_1=7, b_2=3$$, then it is impossible to distribute them to two bins with capacities $$c_1=5, c_2=6$$, but we can distribute them into three bins with capacities $$c_1=5, c_2=2, c_3=3$$.

It is NP-hard, by reduction from multiway number partitioning: given an instance of multiway number partitioning, i.e., a multiset $$S$$ and a target $$T$$ and a positive integer $$k$$ so that $$S$$ sums to $$kT$$, set $$b_1=\dots=b_k=T$$ and $$c_1,\dots,c_n$$ the multiset. Then there is a monochromatic assignment iff there is a valid solution to the multiway number partitioning problem.