I think it's an nCr problem

[Stratego]

I think the problem below is an nCr problem [n!/(r!*(n-r)!)], but I'm not quite sure how to approach it. Any help would be appreciated.

 

There are 20 numbers, 1-20.

Someone would randomly pick 5 numbers.

I need to create sets of 10 numbers so that at least one set contains the 5 numbers that the other person pick. What's the minimum number of sets I'd need to create?

[mathematic]

I think the problem below is an nCr problem [n!/(r!*(n-r)!)], but I'm not quite sure how to approach it. Any help would be appreciated.

 

There are 20 numbers, 1-20.

Someone would randomly pick 5 numbers.

 

I need to create sets of 10 numbers so that at least one set contains the 5 numbers that the other person pick. What's the minimum number of sets I'd need to create?

What is the relation between the sets you create. One extreme - each set of 10 is independent of any other. Other extreme, two sets of ten each, i.e. no number in both sets.

 

Answers - case 1 - there is no minimum, since you could be unlucky enough to create sets without choosing any of the 5. case 2 - 2 sets will use all the numbers, so the 5 chosen will all show up in one or the other.

[John]

If I'm understanding the question correctly, then the first person chooses five numbers of the twenty. The second person then builds unique sets of ten numbers from the same twenty. The question is how many ten-element sets the second person would need to choose to ensure that at least one contains all five numbers from the first person's set.

 

It seems to me the solution is to figure out how many sets can be created without using all five of the first person's numbers, then add one.

Edited April 2, 2012 by John

[imatfaal]

What is the relation between the sets you create. One extreme - each set of 10 is independent of any other. Other extreme, two sets of ten each, i.e. no number in both sets.

 

Answers - case 1 - there is no minimum, since you could be unlucky enough to create sets without choosing any of the 5. case 2 - 2 sets will use all the numbers, so the 5 chosen will all show up in one or the other.

 

I think the idea from the OP is that the 5 random numbers must be contained in ONE set of ten numbers. Your second case doesn't work as your two sets could be 1-10 and 11-20; if the numbers chosen were 2,4,6, 12,14 you would not have covered it.

 

If I'm understanding the question correctly, then the first person chooses five numbers of the twenty. The second person then builds unique sets of ten numbers from the same twenty. The question is how many ten-element sets the second person would need to choose to ensure that at least one contains all five numbers from the first person's set.

 

It seems to me the solution is to figure out how many sets can be created without using all five of the first person's numbers, then add one.

 

There would be [math]\frac{20!}{15!5!} [/math] sets of five that could be chosen.

 

It is easily shown that groups of ten could be made that would cover all these combinations in at most half the number of groups - you can show this by just making the each group of ten by adding the objects from two groups of five. In fact you can go much lower than that - but not sure how yet.

 

As an example: you want to cover the possibilities that start 1,2,3,4, and then have one more number at the end you could do this in 3 groups of ten

 

{1,2,3,4,5,6,7,8,9,10}

{1,2,3,4,11,12,13,14,15,16,}

{1,2,3,4,17,18,19,20,x, y}

 

That is trivially 16 groups of 5 covered in 3 groups of ten - it is actually many more groups of 5. The first set of 10 covers 252 different sets of 5...

what the minimum actually is, I don't know.

 

The most groups of five that can be covered by a set of 10 is [math] \frac{10!}{5!5!} =252 [/math]. As the total number of groups of 5 numbers is [math] \frac{20!}{15!5!} =15504 [/math] you need at least 62 groups of 10 if your coverage is perfect - whether that is possible I do not know yet.

[John]

The most groups of five that can be covered by a set of 10 is [math] \frac{10!}{5!5!} =252 [/math]. As the total number of groups of 5 numbers is [math] \frac{20!}{15!5!} =15504 [/math] you need at least 62 groups of 10 if your coverage is perfect - whether that is possible I do not know yet.

 

That sounds more like the right track. I guess for whatever reason I had it in my head that the ten-element sets would also be random but unique (though I'm still not sure my proposed strategy is correct in that case--haven't done a whole lot with combinatorics).

[phillip1882]

using an ugly "brute force" attack, i get the number of nessicary groups of 10 to be at most 2540.

 

 

 

[imatfaal]

using an ugly "brute force" attack, i get the number of nessicary groups of 10 to be at most 2540.

 

 

 

That feels about right. I did a fair bit of modelling with lower numbers and the patterns of coverage were not that close to the theoretical minumum. The numbers of small groups needed when the choice number was 2,3, and a bit of 4 were fairly well defined and patterns emerged quickly - but my head was spinning with trying to visualize higher minimum numbers of small groups. I am pretty sure it is generalizable to the number of choices (ie in this case randomly pick 5 numbers) and the difference between the complete set (ie 20) and the small groups (ie 10). with a choice of 2 or 3 numbers you can represent it visually quite easily and it becomes simple to find/show the minimum number of groups needed; i am sure that if my mind worked in 4 and 5 dimensional shapes I could do the same, but it doesn't!

[esbo]

Mmmmmm nasty problem, I remember seeing something similar to this but with smaller sets, can't remember exactly immediately.

Not sure if there is an easy way to solve it.

 

As imafall says "you need at least 62 groups of 10 if your coverage is perfect - whether that is possible I do not know yet."

 

I would guess it is not possible.

 

 

Starting from a simpler example, say a person picks a set of 1 from 3, now how many sets of 2 do you need to cover all the sets of 1?

 

001

010

100

 

110

011

 

answer 2!!

 

Now try 2 from for covered by 3 from 4.

 

0011

0101

1001

1010

1100

 

0111

1110 so 2 sets nearly does it but it misses:-

 

1001 so you need a 3rd set 1101 or 1011.

 

For the original problem suppose you go

 

11111111110000000000

00000000001111111111

 

Well that covers two halves but big problem for those straddling the two halves!!

 

It is at this point the head spinning starts.

[questionposter]

Mmmmmm nasty problem, I remember seeing something similar to this but with smaller sets, can't remember exactly immediately.

Not sure if there is an easy way to solve it.

 

As imafall says "you need at least 62 groups of 10 if your coverage is perfect - whether that is possible I do not know yet."

 

I would guess it is not possible.

 

 

Starting from a simpler example, say a person picks a set of 1 from 3, now how many sets of 2 do you need to cover all the sets of 1?

 

001

010

100

 

110

011

 

answer 2!!

 

Now try 2 from for covered by 3 from 4.

 

0011

0101

1001

1010

1100

 

0111

1110 so 2 sets nearly does it but it misses:-

 

1001 so you need a 3rd set 1101 or 1011.

 

For the original problem suppose you go

 

11111111110000000000

00000000001111111111

 

Well that covers two halves but big problem for those straddling the two halves!!

 

It is at this point the head spinning starts.

 

Are you completely sure you know what factorials are? I guess I could be looking at it the wrong way though.

Edited April 18, 2012 by questionposter

[esbo]

Are you completely sure you know what factorials are? I guess I could be looking at it the wrong way though.

 

Yes I know what they are ie 4! = 4x3x2

 

This is about perms though and it's more complicated than just perms I believe.

 

for example consider these two

 

11111111110000000000

01111111111000000000

 

 

Looks nice consider the first two line - but you miss the this line of 5

11111111110000000000

01111111111000000000

10111000001000000000

 

using an ugly "brute force" attack, i get the number of nessicary groups of 10 to be at most 2540.

 

 

 

 

I expect the answer is ugly, what was your attack?

A computer program?

Even that would require a lot of though on the strategy???

Or maybe I am missing something?

 

I suppose you could do all the number of perms of 10 from 20 and get an answer X

then find all the perms of 5 from 10 and multiply by X

 

But you may get loads of duplicates?

[phillip1882]

right, a cpu program. basically what i did was randomly select groups of 10 untill i got every group of 5 covered, and then tried to minimize it as much as possible. personally i don't think it should actually require more than 74 groups of 10.

20!/(10!*10!) = 18476

10!/(5!*5!) = 252

18476/252 aprox = 74

[imatfaal]

Hello Phillip

 

Its been decades since I studied perms combs etc. I came to this figure

[math] \frac{20!}{15!5!} =15504 [/math] On these lines

 

20 objects for first choice, 19 for second.... ->[math] 20*19*18*17*16= \frac{20!}{15!} [/math]

and there are 5! ways in which those choices can be arranged - so divide through by 5! to give [math] \frac{20!}{15!5!} =15504 [/math]

 

I am not sure how you get to [math] \frac{20!}{10!10!} =18476 [/math]

[phillip1882]

i'm not aguing with you; for picking 5 items from a group of 20, you are correct, 15504 is the number. however, i am considering the number of ways you can get a group of 10 items from 20. i think this is a better representation of the problem, as though person A has 15504 choices for selection, person B must choose from the 18476 choices to eleminate as many of person A's choices as possible, and each choice of 10 will eliminate roughly 252 choices. i could obviously be wrong with my "logic" here, it's a gut call. <BR>(to put it a bit more succently, i'm trying to factor in the overlap problem.)

Edited April 18, 2012 by phillip1882

[imatfaal]

Phillip - I see. thanks for explaining

[esbo]

i'm not aguing with you; for picking 5 items from a group of 20, you are correct, 15504 is the number. however, i am considering the number of ways you can get a group of 10 items from 20. i think this is a better representation of the problem, as though person A has 15504 choices for selection, person B must choose from the 18476 choices to eleminate as many of person A's choices as possible, and each choice of 10 will eliminate roughly 252 choices. i could obviously be wrong with my "logic" here, it's a gut call. <BR>(to put it a bit more succently, i'm trying to factor in the overlap problem.)

 

Yes it is the overlap where the fun really begins.

I remember trying a similar problem, I will see if I can find it, the solution to the problem was also given I think.

 

Ah!!!! I have found it!

 

In a mathematical competition, in which problems were posed to the participants, every two of these problems were solved by more than of the contestants. Moreover, no contestant solved all the problems. Show that there are at least contestants who solved exactly problems each.

[imatfaal]

"every two of these problems" - does this mean any combination of two problems?

 

and is the number of contestants totally unconstrained, limited, or fixed?

 

update - the number of contestants must be limited. with 15 it is easy and clearly possible to show the opposite is true

[esbo]

"every two of these problems" - does this mean any combination of two problems?

 

and is the number of contestants totally unconstrained, limited, or fixed?

 

update - the number of contestants must be limited. with 15 it is easy and clearly possible to show the opposite is true

 

Yes I remember finding it difficult to understand, it's every pair.

 

There is no limit on the number of contestants specified so there isn't an.

 

I recall the answer is achieved by showing a contradiction between some equation you derive

and the number of contestants does not come into it.

 

Helps to see here http://www.artofproblemsolving.com/Forum/viewtopic.php?f=267&t=44575&start=0

 

 

But it's tough to understand.

Edited April 20, 2012 by esbo