Problem

Source: I International Festival of Young Mathematicians Sozopol 2010, Theme for 10-12 grade

Tags: set theory, combinatorics



The sets $A_1,A_2,...,A_n$ are finite. With $d$ we denote the number of elements in $\bigcup_{i=1}^n A_i$ which are in odd number of the sets $A_i$. Prove that the number: $D(k)=d-\sum_{i=1}^n|A_i|+2\sum_{i<j}|A_i\cap A_j |+...+(-1)^k2^{k-1}\sum_{i_1<i_2<...<i_k}|A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k}|$ is divisible by $2^k$.