MathDB
finite set

Source: USAMO 1994

October 23, 2005
inductionfunctionalgebra unsolvedalgebra

Problem Statement

Let  ∣U∣, σ(U) \, |U|, \, \sigma(U) \, and  π(U) \, \pi(U) \, denote the number of elements, the sum, and the product, respectively, of a finite set  U \, U \, of positive integers. (If  U \, U \, is the empty set,  ∣U∣=0, σ(U)=0, π(U)=1\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1.) Let  S \, S \, be a finite set of positive integers. As usual, let  (nk) \, \binom{n}{k} \, denote  n!k! (n−k)!\, n! \over k! \, (n-k)!. Prove that ∑U⊆S(−1)∣U∣(m−σ(U)∣S∣)=π(S) \sum_{U \subseteq S} (-1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S) for all integers  m≥σ(S)\, m \geq \sigma(S).
Back to ProblemsView on AoPS