RO-TST 1988 Problem 16

The finite sets $A_1$ , $A_2$ , $\ldots$ , $A_n$ are given and we denote by $d(n)$ the number of elements which appear exactly in an odd number of sets chosen from $A_1$ , $A_2$ , $\ldots$ , $A_n$ . Prove that for any $k$ , $1\leq k\leq n$ the number $${ d(n) - \sum\limits^n_{i=1} |A_i| + 2\sum\limits_{ i<j} |A_i \cap A_j | - \cdots + (-1)^k2^{k-1} \sum\limits_{i_1 <i_2 <\cdots < i_k} | A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}}|$$ is divisible by $2^k$ .

Ioan Tomescu, Dragos Popescu