N is the number of ordered pairs of non-empty sets P and Q that have the following properties:
- P ⋃ Q ={1,2,3,4,5,6,7,8,9,10,11,12}, and:
- P ⋂ Q = Φ, and:
- The number of elements of P is not an element of P, and:
- The number of elements of Q is not an element of Q
Find N.
assume that one of P,Q is empty,
then the other set has 12 elements and also has the number 12, thus violating either requirements 3 or 4.
So assume P has k elements 1<=k<=11 and thus Q has 12-k elements
now if k=6 then |P|=|Q|=6 and thus 6 can not be a member of P or Q but it has to belong to one of them, thus k is not 6
now for any given k, we have that the element k must belong to Q and 12-k must belong to P. That gives us k-1 remaining elements to assign to set P. We have 10 remaining elements to choose these k-1 from, thus this can be done in 10C(k-1) ways and the remaining elements go to Q.
So the total number of combinations is
Sum(10C(k-1), k=1 to 11)-10C5
changing index we get
Sum(10Ck,k=0 to 10)-10C5
2^10-10C5
1024-252=772
Thus there are 772 such ordered pairs
|
|
Posted by Daniel
on 2015-04-13 13:46:10 |
solution
