RMO 2012 solution to Question No. 4

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.

2 Replies to “RMO 2012 solution to Question No. 4”

  1. Dear Soumik,The 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.

Leave a Reply

Your email address will not be published. Required fields are marked *