Picking assigned items from sets without knowing exact contents of sets

Look for help with this problem. I realise it's not the most clear the way it's written but it's difficult to phrase.

Imagine you are assigned x items. You are then given y sets of size z each, which contain between them all between 0 and x of your items, and the remainder of each set is filled with items you were not assigned. There are no two items the same between sets.

You draw a number of items from the sets at random. You can't tell what you're drawing from the set until you've made your final selections. You're trying to pick all your items with no incorrect selections. So the number you select will be between 0 and x.

For example, say you were assigned 5 items and there are 3 sets of size 9 each. When generating the sets, you first pick randomly how many items out the 5 you will spread across the 3 sets and fill the rest with decoy items until you reach 9. So for example say you chose to select 4. You first have to pick 4 out the 5 (5choose4), then assign them to sets. Assigning them could be done like 4, 0, 0 .... 4, 0, 0 .... 0, 0, 4 ... 0, 0, 4 .... 3, 1, 0 .... 3, 0, 1....etc...

The aim of the game is to correctly select all 4 items from the sets. You make selections from set 1, then set 2 and finally 3. You don't know how many items you're looking for, it could be 0 to 5. The selection is only a match if it matches exactly, i.e. you can't miss any you were assigned residing in the sets and you can't select items from the set that you weren't assigned originally. How many rounds would have you to play before you had covered every possibility?

Thank you.

• I should add that I'm looking for a generalised expression involving x, y, z. Thanks – user8918 Mar 31 '11 at 1:00

I assume when you say "You draw a number of items from the sets at random" you in fact mean that they are in a particular order in each set which you do not know, and you can choose which ones from the order to pick; otherwise this might go on forever as you randomly fail to pick the right ones.

I also assume that you are not told the detailed results of attempts; otherwise, if you were, then you could stick with what worked and cut down future searches.

So to take an example of 2 items which may be in boxes $A$ or $B$, each containing two items, the possibilities are 1 way of choosing nothing ( $\{\}$ ), 4 ways of choosing one item from one box and none from the other ( $\{A_1\}$, $\{A_2\}$, $\{B_1\}$, $\{B_2\}$ ), plus 4 ways of choosing one item from each box ( $\{A_1, B_1\}$, $\{A_1, B_2\}$, $\{A_2, B_1\}$, $\{A_2, B_2\}$ ), and 2 ways of choosing two items from one box and none from the other ( $\{A_1, A_2\}$, $\{B_1, B_2\}$ ), giving 11 possibilities in all.

If so then, perhaps surprisingly, the answer does not depend on $y$ or $z$ individually but only on the product $yz$, as the having the sets ordered mean you in effect have $yz$ individual sets of one desired or undesired element each.

So the formula for the number of possibilities is
$$\sum_{i=0}^{x} {yz \choose i}$$ since there are ${yz \choose i}$ ways of putting $i$ of the original $x$ in the boxes.

For your $x=5$, $y=3$, $z=9$ example this gives 101584 possibilities.

Thanks for your answer. Yes to the questions: you don't know the order, you're basically trying every combination and you are not told the results so you can't trim the search.

I think we're almost there but looking at your example of 2 items, surely when you're picking 2 from the original 5 you need to do $${5 \choose 2}$$ as the 2 items that will appear across the sets themselves have this many ways of being picked?

EDIT:

Here's how I calculated my version for 2 sets instead of 3:

List all the ways to split the 5 items..

So for picking 5 out of 5...

(5 0) (0 5) (1 4) (4 1) (3 2) (2 3)

Do the calculations, (5c5 * 5c0) + (5c0 * 5c5) + (5c1 * 5c4) .... and so on. And multiply this result by 5c5

Repeat this for picking 4,3,2,1,0. and sum the total to get the total 51020.

Have I done something wrong?

• In my example of "2 items which may be in boxes $A$ or $B$, each containing two items", where does 5 come from? – Henry Mar 31 '11 at 10:36
• Well I assumed you mean it was 2 chosen from the original 5. Even so, putting the numbers through.. summing 18 choose x from 0 to 5 doesn't give what I'd expect. Surely you need to multiply each term by 5 choose x? – user8938 Mar 31 '11 at 11:17