Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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|}$

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems/Problem_5&oldid=196413"