HMMT November, 2017

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

Marisa has a collection of $2^{8}-1=255$ distinct nonempty subsets of $\{1,2,3,4,5,6,7,8\}$ . For each step she takes two subsets chosen uniformly at random from the collection, and replaces them with either their union or their intersection, chosen randomly with equal probability. (The collection is allowed to contain repeated sets.) She repeats this process $2^{8}-2=254$ times until there is only one set left in the collection. What is the expected size of this set?

Solution

Solution:

It suffices to compute the probability of each number appearing in the final subset. For any given integer $n \in [1,8]$ , there are $2^{7}=128$ subsets with $n$ and $2^{7}-1=127$ without. When we focus on only this element, each operation is equivalent to taking two random sets and discarding one of them randomly. Therefore there is a $\frac{128}{255}$ probability that $n$ is in the final subset, and the expected value of its size is $8 \cdot \frac{128}{255}=\frac{1024}{255}$ .

Alternatively, since $|A|+|B|=|A \cup B|+|A \cap B|$ , the expected value of the average size of all remaining subsets at a given step is constant, so the answer is simply the average size of all 255 subsets, which is $\frac{8 \cdot 128}{255}=\frac{1024}{255}$ .

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.