Competition problem — Combinatorics

Library / /420 of 520

Combinatorics Difficulty 5.8 AIME, harder Prove it

Let $S$ be a finite set, and let $A_{1}, A_{2}, \cdots, A_{n} \subseteq S$ . Denote $|A|$ as the number of elements in the set $A$ . Prove: There exists a real-valued mapping $F$ defined on the power set of $X=\{1,2, \cdots, n\}$ (i.e., the set of all subsets of $X$ ) such that for any $I \subseteq X$ , we have
$\sum_{J \subseteq I} F(J)=\left|\complement_{S}\left(\cap_{i \in I} A_{i}\right)\right|$

Solution

Notice that, $\complement_{s}\left(\bigcap_{j \in J} A_{j}\right)=\bigcup_{j \in J} \complement_{S} A_{j}$ . Define $F(I)=\sum_{J \subseteq I}(-1)^{|I|-|J|}\left|\bigcap_{j \in J} \bigcap_{s} A_{j}\right|$ . By the principle of inclusion-exclusion, we have
$\begin{array}{l} \sum_{J \leq I} F(J)=\sum_{J \subseteq I} \sum_{K \leq J}(-1)^{|J|-|K|}\left|\bigcap_{k \in K} \complement_{s} A_{k}\right| \\ =\left|\cup_{i \in I}{ }_{s} A_{i}\right|=\left|\complement_{S}\left(\bigcap_{j \in J} A_{j}\right)\right| . \end{array}$
(Zheng Jialin, Wuhan Iron and Steel No.3 High School, Hubei Province, 430080)

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.