MathDB
Elements which appear in an odd number of sets chosen

Source: Romanian IMO Team Selection Test TST 1988, problem 16

October 1, 2005
combinatorics unsolvedcombinatorics

Problem Statement

The finite sets A1A_1, A2A_2, …\ldots, AnA_n are given and we denote by d(n)d(n) the number of elements which appear exactly in an odd number of sets chosen from A1A_1, A2A_2, …\ldots, AnA_n. Prove that for any kk, 1≤k≤n1\leq k\leq n the number d(n)−∑i=1n∣Ai∣+2∑i<j∣Ai∩Aj∣−⋯+(−1)k2k−1∑i1<i2<⋯<ik∣Ai1∩Ai2∩⋯∩Aik∣{ 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 2k2^k. Ioan Tomescu, Dragos Popescu
Back to ProblemsView on AoPS