Nemotron-IMO-Bench 2026 C38

Let $n$ be a positive integer and let $A_1,\ldots, A_{2^n+1}$ be finite sets. We color these sets red and blue such that there is at least one red and at least one blue set. Prove that there are at least $2^n$ different sets which can be obtained as the symmetric difference of a red set and a blue set. Here the symmetric difference of two sets as the set of objects belonging to exactly one of the two sets.