4. Let X = {1, 2, 3, ... , 10}. Find the number of pairs {A, B} such that A ⊆ X, B ⊆ X, A ≠ B and A∩B = {5, 7, 8}.
Solution:
First we put 5, 7, 8 in each of A and B.
We are left out with 7 elements of X.
For each of these 7 elements there are three choices:
a) it goes to A
b) it goes to B
c) it goes to neither A nor B
Hence there are total \(3^7\) = 2187 choices. From these 2187 cases we delete that one case where all of the seven elements goes to neither A nor B as A≠ B thus giving 2187 -1 = 2186 cases.
Since A and B is unordered (that is A= {5, 7, 8, 1, 2} , B = {5, 7, 8, 4} is the same as B= {5, 7, 8, 1, 2} , A = {5, 7, 8, 4} ) we take half of these 2186 cases that is 1093 cases.
Hence there are 1093 such pairs.
According to HBCSE Official RMO Solutions, your solution is wrong.
ReplyDeleteDear Soumik,
ReplyDeleteThe official solution and our solution (and hence the result) differs because they have taken A and be as ordered, whereas we took it as unordered.
Otherwise both solutions are same.