Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimum number of common elements in sets

  1. Oct 18, 2009 #1

    Let's say I have 500 boxes and 500 hundred non-identical items.

    I would like to have sets of 40, chosen among those 500 hundred items and my objective is to keep the number of same items in any 2 boxes at a minimum.

    1. What would be that minimum number of common items?

    2. If it's not easy to calculate, could someone suggest an algorithm. I can write little php, so I may try to get it calculated.

    Thanks in advance.

    p.s. I'm asking it here, hoping that someone smarter than me could come up with a quick way to calculate it. Of course, I'm not expecting anyone to spend much time on it to solve it for me, but it would nice to know if there are no short-cuts to calculate it.
  2. jcsd
  3. Oct 18, 2009 #2
    So some of the 500 items are identical, but not all of them? How many of each identical set are there?
  4. Oct 18, 2009 #3
    Hmm, I think I was not clear enough, my bad.

    I have unlimited quantity of each item. I would like to fill in the boxes with 40 items and I would like to keep the number of common items in any box to a minimum.

    Like, I have 500 different gifts (with unlimited quantity) to choose from and I would like to prepare gift boxes for children and I will put 40 gifts in each of them. I want to keep the boxes that any 2 children gets as different as possible.

    I hope I could make it clear.

    Edit: And there are a total of 500 boxes / children.
    Last edited: Oct 18, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook