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

Difference between revisions of "1994 USAMO Problems/Problem 5"

m (→‎See Also)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
Let, for <math>|S|\geq k \geq 1</math>, <math>A_k</math> be a collection of sets such that <math>| \bigcap_{k \in U}A_k | = \binom{m- \sigma(U)}{|S|}</math>. We'll try to find such a collection to prove <math>| \bigcup_{k \in U}A_k | = \binom{m}{|S|}-\pi(S)</math>, since we can use the Principle of Inclusion Exclusion to show that <math>| \bigcup_{k \in U}A_k | = \sum_{\emptyset \neq U \subseteq S} (-1)^{|U|+1}| \bigcap_{k \in U}A_k |</math>.
 +
 
 +
Let <math>Z</math> be the set of binary sequences with size <math>m</math>, which we'll divide into blocks, in particular, with <math>S=\{x_1, x_2, ..., x_n\}</math>, the first block has size <math>x_1</math>, the next has size <math>x_2</math> and so on, until we reach <math>\sigma(S)</math>, the last few we shall consider as an extra block with size <math>m-\sigma(S)=R</math>.
 +
 
 +
Now we perceive that the <math>\sigma(U)</math> function has the property, that, for <math>U \subseteq S</math>, <math>\sigma(S)-\sigma(U)= \sigma(S\setminus U)</math>, so, <math>m- \sigma(U)= \sigma(S\setminus U)+R</math>.
 +
 
 +
Let <math>A_k</math> be the number of binary sequences with exactly <math>|S|</math> times <math>1</math>, but no appearances of <math>1</math> in the <math>k</math>-th block. It is easy to see that <math>\bigcap_{k \in U}A_k</math> is all of the binary sequences with exactly <math>|S|</math> times <math>1</math>, but no appearances of <math>1</math> in any of the <math>k</math>-th blocks, for <math>k \in U</math>. So, we can simply eliminate those blocks, with is equivalent to eliminating <math>U</math> from <math>S</math> , so we are left with <math>\sigma(S\setminus U)+R</math> places to put the <math>1</math>'s <math>|S|</math> times. This is <math>\binom{\sigma(S\setminus U)+R}{|S|}</math>, and we saw that is is equal to <math>\binom{m- \sigma(U)}{|S|}</math>. So, we've found a collection that fits the description.
 +
 
 +
The number of ways to pick <math>1</math>'s <math>|S|</math> times from <math>m</math> places is <math>\binom{m}{|S|}</math>. But we don't want for the <math>1</math>'s to fill every block, since this is not in the union. We have <math>\pi(S)</math> ways to put the <math>1</math>'s <math>|S|</math> times, where each <math>1</math> is in exacty one block (<math>x_1</math> places <math>\times</math> <math>x_2</math> places and so on). So, we find that <math>| \bigcup_{k \in U}A_k | = \binom{m}{|S|}-\pi(S)</math>. Which implies, by the Principle of Inclusion Exclusion,
 +
<math>\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|}</math>
  
 
==See Also==
 
==See Also==

Revision as of 08:14, 10 June 2018

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 $| \bigcap_{k \in U}A_k | = \binom{m- \sigma(U)}{|S|}$. We'll try to find such a collection to prove $| \bigcup_{k \in U}A_k | = \binom{m}{|S|}-\pi(S)$, since we can use the Principle of Inclusion Exclusion to show that $| \bigcup_{k \in U}A_k | = \sum_{\emptyset \neq U \subseteq S} (-1)^{|U|+1}| \bigcap_{k \in U}A_k |$.

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=95037"