Maths Olympiad Prep

Track / Stage 6 / 252 of 400 #1252 of 1964

Problem 1252

National olympiad, first round
Combinatorics Difficulty 6.5 Find the answer

Let XX be a set containing nn elements. Find the number of ordered triples (A,B,C)(A,B, C) of subsets of XX such that AA is a subset of BB and BB is a proper subset of CC.

A number or a short expression. Spacing and $ signs are ignored.

Official solution

1. **Count the number of ordered triples (A,B,C)(A, B, C) such that ABCA \subseteq B \subseteq C:**

For each element xXx \in X, there are 4 possibilities:
- xx belongs to all three sets AA, BB, and CC.
- xx belongs to BB and CC but not to AA.
- xx belongs to CC only.
- xx belongs to none of the sets.

Since there are nn elements in XX, the total number of such triples is:
4n 4^n

2. **Count the number of ordered triples (A,B,C)(A, B, C) such that AB=CA \subseteq B = C:**

For each element xXx \in X, there are 3 possibilities:
- xx belongs to both AA and B=CB = C.
- xx belongs to B=CB = C but not to AA.
- xx belongs to none of the sets.

Since there are nn elements in XX, the total number of such triples is:
3n 3^n

3. **Subtract the number of triples where B=CB = C from the total number of triples:**

The number of ordered triples (A,B,C)(A, B, C) such that ABCA \subseteq B \subseteq C and BCB \neq C is:
4n3n 4^n - 3^n

The final answer is 4n3n\boxed{4^n - 3^n}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.