# a combinatorics problem

• Jul 23rd 2010, 02:26 AM
cos
a combinatorics problem
I have B different labels and C different objects. Each label can be assigned to more than one object at the same time, and each object can have more than one label.

I want to assign every label to exactly X of my C objects, while ensuring that no object has more than Y different labels.

For some values of C, this will not be possible. My question is: What is the smallest value of C for which I can do this assignment?
• Jul 23rd 2010, 03:30 AM
cos
my solution
...is in the next post....
• Jul 23rd 2010, 03:39 AM
cos
my solution
I think the lowest number of objects is given by

$\displaystyle X$ if $\displaystyle B \leq Y$
and $\displaystyle X+(B-Y)\left\lceil X/Y \right\rceil$ otherwise

where with $\displaystyle B \leq Y$ we have every object getting all labels, and so X objects are required, while otherwise $\displaystyle \left\lceil X/Y \right\rceil$ extra objects are required to be assigned the labels not used up by the first X objects.