1994 USAMO Problems/Problem 5

Problem

Let $\, |U|, \, \sigma(U) \,$ and $\, \pi(U) \,$ denote the number of elements, the sum, and the product, respectively, of a finite set $\, U \,$ of positive integers. (If $\, U \,$ is the empty set, $\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1$ .) Let $\, S \,$ be a finite set of positive integers. As usual, let $\, \binom{n}{k} \,$ denote $\, n! \over k! \, (n-k)!$ . Prove that $\sum_{U \subseteq S} (-1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S)$ for all integers $\, m \geq \sigma(S)$ .

Solution

Let, for $|S|\geq k \geq 1$ , $A_k$ be a collection of sets such that $\left|\bigcap_{k \in U}A_k\right| = \binom{m- \sigma(U)}{|S|}$ . We'll try to find such a collection to prove $\left|\bigcup_{k \in U}A_k\right| = \binom{m}{|S|}-\pi(S)$ , since we can use PIE to show that $\left|\bigcup_{k \in U}A_k\right| = \sum_{\emptyset \neq U \subseteq S} (-1)^{|U|+1}\left|\bigcap_{k \in U}A_k\right|$ .

Let $Z$ be the set of binary sequences with size $m$ , which we'll divide into blocks, in particular, with $S=\{x_1, x_2, ..., x_n\}$ , the first block has size $x_1$ , the next has size $x_2$ and so on, until we reach $\sigma(S)$ , the last few we shall consider as an extra block with size $m-\sigma(S)=R$ .

Now we perceive that the $\sigma(U)$ function has the property, that, for $U \subseteq S$ , $\sigma(S)-\sigma(U)= \sigma(S\setminus U)$ , so, $m- \sigma(U)= \sigma(S\setminus U)+R$ .

Let $A_k$ be the number of binary sequences with exactly $|S|$ times $1$ , but no appearances of $1$ in the $k$ -th block. It is easy to see that $\bigcap_{k \in U}A_k$ is all of the binary sequences with exactly $|S|$ times $1$ , but no appearances of $1$ in any of the $k$ -th blocks, for $k \in U$ . So, we can simply eliminate those blocks, with is equivalent to eliminating $U$ from $S$ , so we are left with $\sigma(S\setminus U)+R$ places to put the $1$ 's $|S|$ times. This is $\binom{\sigma(S\setminus U)+R}{|S|}$ , and we saw that is is equal to $\binom{m- \sigma(U)}{|S|}$ . So, we've found a collection that fits the description.

The number of ways to pick $1$ 's $|S|$ times from $m$ places is $\binom{m}{|S|}$ . But we don't want for the $1$ 's to fill every block, since this is not in the union. We have $\pi(S)$ ways to put the $1$ 's $|S|$ times, where each $1$ is in exacty one block ( $x_1$ places $\times$ $x_2$ places and so on). So, we find that $| \bigcup_{k \in U}A_k | = \binom{m}{|S|}-\pi(S)$ . Which implies, by the Principle of Inclusion Exclusion, $\binom{m}{|S|}-\pi(S) = \sum_{\emptyset \neq U \subseteq S} (-1)^{|U|+1}\binom{m- \sigma(U)}{|S|} \iff \pi(S) = \sum_{U \subseteq S} (-1)^{|U|}\binom{m- \sigma(U)}{|S|}$

1994 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Last Problem
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1994 USAMO Problems/Problem 5

Problem

Solution

See Also