Question

Let S = {1, 2, 3, ..., n}. Three subsets A, B, C of S are chosen at random.

Find the probability that the union of A, B, and C is S.

Answer 1

To find the probability that the union of three randomly chosen subsets \( A \), \( B \), and \( C \) from the set \( S = \{1, 2, 3, \ldots, n\} \) covers the entire set \( S \), we first need to analyze how subsets are chosen and then determine the conditions under which their union will equal \( S \).

### Step 1: Number of ways to choose subsets

Each element of the set \( S \) has three possibilities when we are choosing subsets \( A \), \( B \), and \( C \):

1. The element is included in subset \( A \).
2. The element is included in subset \( B \).
3. The element is included in subset \( C \).

Thus, for each element in \( S \), it can either be included in one or more of the subsets \( A, B, C \) or excluded entirely.

### Step 2: Total configurations

For each of the \( n \) elements in the set \( S \), there are 7 valid non-empty combinations of the subsets (since it can be in \( A \), \( B \), \( C \), any pair of these subsets, or all three). Specifically, the valid configurations are:

- In \( A \) only
- In \( B \) only
- In \( C \) only
- In \( A \) and \( B \)
- In \( A \) and \( C \)
- In \( B \) and \( C \)
- In \( A \), \( B \), and \( C \)

However, we must exclude the case where the element is in none of the subsets; thus, for any given element, we have 7 choices.

### Step 3: Total subsets and outcomes

Given that each of the \( n \) elements has 7 valid configurations, the total number of possible ways to form the subsets \( A, B, C \) is:
\[
7^n
\]
since this choice is independent for each of the \( n \) elements.

### Step 4: Favorable outcomes (subsets covering \( S \))

To ensure that the union \( A \cup B \cup C = S \), every element in \( S \) must be included in at least one of the subsets \( A \), \( B \), or \( C \). As derived previously, we have excluded the option where an element is present in none of the subsets.

### Step 5: Probability calculation

The total number of outcomes in which the subsets are chosen (allowing possibility of empty subsets) is:
\[
8^n
\]
since each element can either (1) be in \( A \), (2) be in \( B \), (3) be in \( C \), (4) be in \( A \) and \( B \), (5) be in \( A \) and \( C \), (6) be in \( B \) and \( C \), (7) be in all three subsets, or (8) belong to none.

Given the above, the probability \( P \) that \( A \cup B \cup C = S \) can be expressed as the ratio of favorable outcomes to the total outcomes:
\[
P = \frac{7^n}{8^n} = \left( \frac{7}{8} \right)^n.
\]

### Conclusion

Thus, the probability that the union of the three randomly chosen subsets \( A \), \( B \), and \( C \) covers the entire set \( S \) is:
\[
\boxed{\left( \frac{7}{8} \right)^n}.
\]