Possibilities for Set B with n Objects in Sample Space U

[agargento]

Homework Statement

1. Given sample space U with n objects. A ⊂ U, and A has k objects. A ∩ B ≠∅

What are all the possibilities for B?

Homework Equations

2ⁿ - All possibilities for set B with n objects

The Attempt at a Solution

I don't know where even to begin... The question itself confuses me.

 

[BvU]

Hello again,

Entering a new subject area always takes some getting used to.
You write 'What are all the possibilities for B?' but I suppose (and hope) you mean 'How many B are possible? '

In the relevant equation the ∅ is included, right ? But is it a posssibility for B given that A ∩ B ≠∅ ?
Does the number k have influence on the answer ?

 

[agargento]

Hello again,

Entering a new subject area always takes some getting used to.
You write 'What are all the possibilities for B?' but I suppose (and hope) you mean 'How many B are possible? '

In the relevant equation the ∅ is included, right ? But is it a posssibility for B given that A ∩ B ≠∅ ?
Does the number k have influence on the answer ?

Yea, it should be "how many", just bad translation on my part. Didn't understand your other 2 questions. What is k in this question?

 

[PeroK]

Yea, it should be "how many", just bad translation on my part. Didn't understand your other 2 questions. What is k in this question?

If you are stuck on this sort of problem, you should always try an example. Try $n =3$ and $k =2$.

 

[agargento]

If you are stuck on this sort of problem, you should always try an example. Try $n =3$ and $k =2$.

Oh I got confused. I think the answer might be 2^n-k ... But if A and B have something in common, subtracting k might subtract some objects that exist in B?

 

[PeroK]

Oh I got confused. I think the answer might be 2^n-k ... But if A and B have something in common, subtracting k might subtract some objects that exist in B?

You can check your formula with the example numbers I suggested.

 

[agargento]

You can check your formula with the example numbers I suggested.

2¹ ? I still don't really get it.

 

[PeroK]

2¹ ? I still don't really get it.

Why not do the example? It helps to work it out for some specific numbers. You should be able to list all possible sets for B and count them.

 

[agargento]

Why not do the example? It helps to work it out for some specific numbers. You should be able to list all possible sets for B and count them.

Well ok... U has 3 objects. A has 2. Now, we know that B has something in common with A... But if we don't know the size of B, how can we know if it is equal to A, or maybe smaller?

 

[PeroK]

Well ok... U has 3 objects. A has 2. Now, we know that B has something in common with A... But if we don't know the size of B, how can we know if it is equal to A, or maybe smaller?

I don't think you understand this problem. It's asking you to count how many possibilities you have for B. You can go through all the options for B and count how many meet the requirements.

 

[agargento]

I don't think you understand this problem. It's asking you to count how many possibilities you have for B. You can go through all the options for B and count how many meet the requirements.

Clearly I'm very confused... if n=3 and k=2... Well, I think A could have 4 options... {1,2},{1},{2},{} ...
Seems to me B could be {1,2,3},{1,2},{1},{2},{3,2},{}... Which is 2ⁿ-2^n-k...

 

[PeroK]

Clearly I'm very confused... if n=3 and k=2... Well, I think A could have 4 options... {1,2},{1},{2},{} ...
Seems to me B could be {1,2,3},{1,2},{1},{2},{3},{3,2}... Which is 2ⁿ-2^n-k...

No. $U$ and $A$ are fixed. $B$ is the only "variable" set.

 

[agargento]

No. $U$ and $A$ are fixed. $B$ is the only "variable" set.

Hmm I see. So B could have 2 objects in common in A, or 1. It can also have another object... Maybe 2ⁿ? After all, B could be equal to A...

 

[PeroK]

Hmm I see. So B could have 2 objects in common in A, or 1. It can also have another object... Maybe 2ⁿ? After all, B could be equal to A...

That's all good, apart from another guess at the answer. You still haven't solved the problem for $n = 3, k = 2$.

These problems are about finding a process or method for counting. That's why trying some examples is invaluable. It also gives you a test for any general answer you work out.

 

[agargento]

That's all good, apart from another guess at the answer. You still haven't solved the problem for $n = 3, k = 2$.

These problems are about finding a process or method for counting. That's why trying some examples is invaluable. It also gives you a test for any general answer you work out.

Still can't wrap my head around this...umm.. If U has 3 objetcs, and A has two, B must have at least 1 object in common with A... So it can have either 1 or 2 objetcs that are in A, and maybe have another object from U... So... 2x2... =4 = 2^k?

 

[Delta2]

For sure $2^k$ is a lower bound for the possibilities of B, because B can be any subset of A, in which case A∩B=B≠∅. But there are also other possibilities for B.

 

[PeroK]

Still can't wrap my head around this...umm.. If U has 3 objetcs, and A has two, B must have at least 1 object in common with A... So it can have either 1 or 2 objetcs that are in A, and maybe have another object from U... So... 2x2... =4 = 2^k?

You need to write down all the possibilities for B.

1
2
3
1, 2
1, 3
2, 3
1, 2, 3

Assuming A is the set 1, 2 how many of the above possibilities for B meet the requirements?

 

[agargento]

You need to write down all the possibilities for B.

1
2
3
1, 2
1, 3
2, 3
1, 2, 3

Assuming A is the set 1, 2 how many of the above possibilities for B meet the requirements?

6... Which is 2ⁿ-2^n-k

 

[PeroK]

6... Which is 2ⁿ-2^n-k

Is that true in general, then? If so, why?