Maths Olympiad Prep

Library / /202 of 520

Combinatorics Difficulty 6.0 AIME, harder Prove it

5. (A simple generalization of the principle of inclusion-exclusion)

Let AA be a finite set, and s={P1,P2,,Pm}\boldsymbol{s}=\left\{P_{1}, P_{2}, \cdots, P_{m}\right\} be a finite set of mm properties. Let Ai(1im)A_{i}(1 \leqslant i \leqslant m) be the subset of AA consisting of all elements that have property PiP_{i}. Then the total number of elements in AA that have exactly rr properties, denoted by A(r)A(r), has the following formula (r0)(r \geqslant 0):
A(r)=(r1)1i1<i2<<irmAi1Ai2Air(rr+1)1j1<j2<<jr+1mAj1Aj2Ajr+1++(1)mr(mr)A1A2Am.\begin{array}{l} A(r)=\left(r_{1}\right) \sum_{1 \leqslant i_{1}<i_{2}<\cdots<i_{r} \leqslant m}\left|A_{i_{1}} \cap A_{i_{2}} \cap \cdots \cap A_{i_{r}}\right| \\ -\left({ }_{r}^{r+1}\right) \sum_{1 \leqslant j_{1}<j_{2}<\cdots<j_{r+1} \leqslant m}\left|A_{j_{1}} \cap A_{j_{2}} \cap \cdots \cap A_{j_{r+1}}\right| \\ +-\cdots+(-1)^{m-r}\binom{m}{r}\left|A_{1} \cap A_{2} \cap \cdots \cap A_{m}\right| . \end{array}

Solution

5. Proof: Let aa be an element in AA and aa has exactly rr properties among rr properties. Then it is clear that it is counted exactly once on both the left and right sides of the given formula. If aa is an element in AA and aa has fewer than rr properties, then it is clear that it is not counted on either side of the formula. Finally, let aa be an element in AA that has t(t>r)t (t>r) properties among rr properties, then it is counted in the sum
\sum_{1 \leqslant i_{1}r+1)$. For any $u, 0r\right) . \end{aligned}

Note: In particular, when r=0r=0, we obtain Theorem 1 of this chapter.

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.