Maths Olympiad Prep

Library / /701 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Define P={S,T}P=\{\mathrm{S}, \mathrm{T}\} and let P\mathcal{P} be the set of all proper subsets of PP. (A proper subset is a subset that is not the set itself.) How many ordered pairs (S,T)(\mathcal{S}, \mathcal{T}) of proper subsets of P\mathcal{P} are there such that (a) S\mathcal{S} is not a proper subset of T\mathcal{T} and T\mathcal{T} is not a proper subset of S\mathcal{S}; and (b) for any sets SSS \in \mathcal{S} and TT,ST \in \mathcal{T}, S is not a proper subset of TT and TT is not a proper subset of SS ?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

For ease of notation, we let 0=,1={S},2={T}0=\varnothing, 1=\{\mathrm{S}\}, 2=\{\mathrm{T}\}. Then both S\mathcal{S} and T\mathcal{T} are proper subsets of {0,1,2}\{0,1,2\}. We consider the following cases: Case 1. If S=\mathcal{S}=\varnothing, then S\mathcal{S} is a proper subset of any set except the empty set, so we must have T=\mathcal{T}=\varnothing. Case 2. If S={0}\mathcal{S}=\{0\}, then T\mathcal{T} cannot be empty, nor can it contain either 1 or 2, so we must have T={0}\mathcal{T}=\{0\}. This also implies that if S\mathcal{S} contains another element, then there would be no choice of T\mathcal{T} because {0}\{0\} would be a proper subset. Case 3. If S={1}\mathcal{S}=\{1\}, then T\mathcal{T} cannot contain 0, and cannot contain both 1 and 2 (or it becomes a proper superset of S\mathcal{S}), so it can only be {1}\{1\} or {2}\{2\}, and both work. The similar apply when S={2}\mathcal{S}=\{2\}. Case 4. If S={1,2}\mathcal{S}=\{1,2\}, then since T\mathcal{T} cannot contain 0, it must contain both 1 and 2 (or it becomes a proper subset of S)\mathcal{S}), so T={1,2}\mathcal{T}=\{1,2\}. Hence, all the possibilities are (S,T)=(,),({0},{0}),({1},{1}),({1},{2}),({2},{1}),({2},{2}),({1,2},{1,2})(\mathcal{S}, \mathcal{T})=(\varnothing, \varnothing),(\{0\},\{0\}),(\{1\},\{1\}),(\{1\},\{2\}),(\{2\},\{1\}),(\{2\},\{2\}),(\{1,2\},\{1,2\}) for 7 possible pairs in total.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.