MathDB
0721

Source:

April 28, 2008
inductionalgorithminvariantvector

Problem Statement

Let k k be an integer, k≥2 k \geq 2, and let p1, p2, …, pk p_{1},\ p_{2},\ \ldots,\ p_{k} be positive reals with p_{1} \plus{} p_{2} \plus{} \ldots \plus{} p_{k} \equal{} 1. Suppose we have a collection (A1,1, A1,2, …, A1,k) \left(A_{1,1},\ A_{1,2},\ \ldots,\ A_{1,k}\right), (A2,1, A2,2, …, A2,k) \left(A_{2,1},\ A_{2,2},\ \ldots,\ A_{2,k}\right), … \ldots, (Am,1, A1,2, …, Am,k) \left(A_{m,1},\ A_{1,2},\ \ldots,\ A_{m,k}\right) of k k-tuples of finite sets satisfying the following two properties: (i) for every i i and every j≠j′ j \neq j^{\prime}, A_{i,j}\cap A_{i,j^{\prime}} \equal{} \emptyset, and (ii) for every i≠i′ i\neq i^{\prime} there exist j≠j′ j\neq j^{\prime} for which Ai,j∩Ai′,j′≠∅ A_{i,j} \cap A_{i^{\prime},j^{\prime}}\neq\emptyset. Prove that \sum_{b \equal{} 1}^{m}{\prod_{a \equal{} 1}^{k}{p_{a}^{|A_{b,a}|}}} \leq 1.
Back to ProblemsView on AoPS