Maths Olympiad Prep

Library / /3 of 30

Combinatorics Difficulty 4.1 AIME Find the answer Italy

Problem:

How many ordered pairs (A,B)(A, B) of subsets of {1,2,3,4,5}\{1,2,3,4,5\} are there such that the intersection of AA and BB has exactly one element?

Pick one

Solution

Solution:

The answer is (E)\mathbf{(E)}. The required pairs can be constructed as follows: first we choose the common element between AA and BB (five possibilities), and for each element not belonging to the intersection we decide whether it lies in AA, in BB, or in neither of the two. This leads us to making a choice among 3 possibilities for each of the other 4 elements, so in total we have 343^{4} possibilities (once the intersection has been fixed). Since every pair with the required property is obtained in this way for exactly one choice of the intersection element and for exactly one choice of how to distribute the remaining elements, the number of pairs is 534=4055 \cdot 3^{4} = 405.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.