PRMO 2014 question 20, subset counting

---

20. What is the number of ordered pairs $(A, B)$ where $A$ and $B$ are subsets of $\{1, 2, \ldots, 5\}$ such that neither $A \subseteq B$ nor $B \subseteq A$?
[PRE-RMO–2014]

---

A wrong approach:
Let's partition the numbers into 2 sets.
First set has 1 element, second has 4 elements. Total ways to do this = 5C1 * 2 = 10. 5C1 since there are 5C1 ways to choose the set with 1 element. *2 because these are ordered pairs.
Similarly, let's partition the numbers such that first set has 2 elements, second set has 3 elements.
Again, 5C2*2 = 20.
So total 30 ways.

Why is this wrong?
Because we didn't count the cases when a number is not present in either set + when a number is present in both the sets.

For e.g. A = {2}, B = {3,4} is a valid case.
A = {2,3}, B = {1,2} is also valid.

So what's the correct approach?

Via the “four‐color” method. Label each element of $\{1,2,3,4,5\}$ according to whether it is

1. in neither $A$ nor $B$,

2. in $A$ only,

3. in $B$ only, or

4. in both $A$ and $B$.

There are $4$ possible statuses for each of the $5$ elements, giving a total of $4^5 = 1024$ ways to form an ordered pair $(A,B)$.

To ensure that neither $A\subseteq B$ nor $B\subseteq A$, we need at least one element of type 2 (an element in $A$ only) and at least one of type 3 (an element in $B$ only). Use inclusion–exclusion:

• Total configurations: $4^5 = 1024$.

• Subtract those with no type 2 element (so only types 1, 3, 4 are used): $3^5 = 243$.

• Subtract those with no type 3 element (so only types 1, 2, 4 are used): another $3^5 = 243$.

• Add back those with neither type 2 nor type 3 (so only types 1, 4 are used): $2^5 = 32$.

Hence the count is

$$1024 \;-\;243\;-\;243\;+\;32 \;=\;570.$$

Therefore, the number of ordered pairs $(A,B)\subseteq\{1,2,3,4,5\}$ with neither $A\subseteq B$ nor $B\subseteq A$ is

$$\boxed{{\displaystyle 570}}\mathrm{.}$$