I proved it by induction about $ m$. Let $ S = \sum_{b = 1}^{m}\prod_{a = 1}^{k} p_{a}^{|A_{b,a}|}$. The case $ m = 1$ is trivial. Suppose that the proposition is true for all $ m$ less than $ M$. If $ m = M$, If there exist a element $ x$ which appears in only $ A_{a,n}$ for fixed $ n$, we can remove all $ x$s. ( this removing doesn't affect the satisfaction of the condition ) But then the value of $ S$ is increased. So we can assume that there doesn't exist such $ x$. $ (*)$ Choose a element in some sets. Denotes it $ x$. Let ${ B_{i} = \{j | x \in A_{j,i}}\}$ and $ f(X) = \sum_{b\in X}\prod_{a = 1}^{k} p_{a}^{|A_{b,a}|}$. Because of the condition (i), $ B_{i}$s are disjoint sets. Let $ C = \{1,\cdots,m\} - B_{1} - \cdots - B_{k}$. For each $ B_{i}$, sets "with respect to" $ B_{i}$ , that is $ A_{a,b}$s such that $ a\in B_{i}$, also satisfy the condition. Removing $ x$ from those sets also doesn't affect this. ( see the argument for $ (*)$ ) .If we did this, $ f(B_{i})$ turns to $ \frac {1}{p_{i}}f(B_{i}) = b_{i}$. Furthermore, If we add some sets "with respect to" $ C$, this collection of sets remain to satisfy the condition. Because there exist least two nonempty $ B_{i}$ (see $ (*)$), we can apply induction hypothesis to this. If $ f(C) = X$, We get $ b_{i} + X \le 1 \Rightarrow b_{i} \le 1 - X$. We're goal is to show that $ S = p_{1}b_{1} + \cdots + p_{k}b_{k} + X \le 1$. But this can be proved now. $ p_{1}b_{1} + \cdots + p_{k}b_{k} + X \le (1 - X)(p_{1} + \cdots + p_{k}) + X = 1 - X + X = 1$. Therefore induction step is ended. $ Q.E.D.$

N.B. My work on this problem was based around drawing tables, and I couldn't find a way to upload images, so I strongly advise the marker draw a table as instructed to help them visualise the ideas of this proof, though I hope the explanation is sound enough anyway. Firstly, let $ S$ be the union of all sets $ A_{i,j}$. Write it in the form $ S = \{a_1,a_2,....,a_n\}$ (a union of finitely many finite sets is finite). Now draw a table with $ a_1,a_2,....,a_n$ along the top and the numbers $ 1,2,....,m$ down the left hand side. By condition (i), for some $ i$ there exists at most one $ j$ such that any single $ a_s \in A_{i,j}$. If such a $ j$ exists, we signify this in our table by writing $ j$ in the cell in column $ a_s$ and row $ i$. If no such $ j$ exists, leave the cell blank. We call the sum of a table the quantity given in the question to estimate. We now use the following algorithm to 'fill in' all the blank cells without affecting the value we are trying to estimate. Suppose that in row $ i$ the cells in columns $ a_{s_t}$ are blank for $ t = 1,2,....,u$. Then replace row $ i$ with $ k^u$ rows with the following properties: - For $ s \not\in \{s_t\}$ let the value in column $ a_s$ be constant for all our new rows and equal to the original value from 'row $ i$'. - Let our $ k^u$ rows all be different and let the ordered $ u$-tuple formed by the values of the cells in columns $ a_{s_1}, a_{s_2},... ,a_{s_u}$ take all values in $ \{1,2,...,k\}^u$. Doing this replacement procedure to a single row $ i$, noting that this leaves every term of the sum except that where $ b = i$ invariant, replaces $ \prod_{a = 1}^k p_a^{|A_{i,a}|}$ with the value (where the sum is taken over all $ k$-tuples $ (t_v)$ of nonnegative integers such that $ t_1 + t_2 + ... + t_k = u$, corresponding to adding up how many times each of $ \{1,2,...,k\}$ appears in the previously empty cells of a given row) given by \[ \sum_{(t_v)}\binom{u}{t_1}\binom{u - t_1}{t_2}...\binom{u - t_1 - t_2 - ... - t_{k - 1}}{t_k}\prod_{a = 1}^k p_a^{|A_{i,a}| + t_a} \] This can be re-written as \[ \prod_{a = 1}^k p_a^{|A_{i,a}|}\sum_{(t_v)}\binom{u}{t_1}\binom{u - t_1}{t_2}...\binom{u - t_1 - t_2 - ... - t_{k - 1}}{t_k}\prod_{a = 1}^k p_a^{t_a} \] \[ = \prod_{a = 1}^k p_a^{|A_{i,a}|}(p_1 + p_2 + ... + p_k)^u = \prod_{a = 1}^k p_a^{|A_{i,a}|} \] So this operation does indeed leave the sum invariant, and does not create any more rows with empty cells. We can therefore perform this operation on all rows containing empty cells. Furthermore, if condition (ii) does not hold for the new table, since we have *added* elements to our sets, it quite clearly cannot have held for the original table. Better Explanation: If for $ i'$ there were originally $ j\not = j'$ for which $ A_{i,j} \cap A_{i',j'} \not = \emptyset$ then in the new situation for any $ i$ value corresponding to a newly created row, if $ i'$ corresponds to an old row, this old relationship still holds (because all the elements of $ S$ previously in 'row $ i$' are now in all our rows. If $ i'$ also corresponds to a newly-created row, the permutations among the previously empty cells being different imply that there is a column $ a_s$ in which content $ j, j'$ of cells $ i$ and $ i'$ differ, corresponding to a nonempty intersection between sets $ A_{i,j}$ and $ A_{i',j'}$ with $ j\not = j'$ (nonempty because they contain $ a_s \in S$. We therefore perform this operation to every row in the original table, to yield a new table with the same sum, but with no empty cells. Now, it is clear that the rows of the table form some subset $ U$ of the set of vectors $ V = \{1,2,...,k\}^n$. We cannot have two identical rows, else condition (ii) would be violated, because in such identical rows $ i,i'$ an element is in $ A_{i,j}$ if and only if it is in $ A_{i',j}$, so for $ j\not = j', A_{i,j}\cap A_{i',j'}$ would be empty. For a vector $ v \in V$ let $ f_d(v)$ denote the number of entries in $ v$ with value $ d$. The original definition of a table's sum is clearly equivalent to the following expression: \[ \sum_{u \in U} \prod_{a = 1}^k p_a^{f_a(u)} \] The $ p_i$ are positive reals, so each term in this sum is positive. The sum is therefore maximal when the set $ U$ is as large as it can possibly be. But $ U$ is a subset of $ V$, so $ U = V$ is this maximal case, and here it is clear that (with each vector corresponding to 'choosing a number from each bracket') \[ \sum_{v \in V} \prod_{a = 1}^k p_a^{f_a(v)} = (p_1 + p_2 + ..... + p_k)^n = 1 \] Thus \[ \sum_{u \in U} \prod_{a = 1}^k p_a^{f_a(u)} \leq 1 \] And this was the result required. Equality occurs if and only if (once all the blank spaces have been filled) every possible partition of $ S$ into $ k$ subsets corresponds to a $ k$-tuple $ (A_{i,1},A_{i,2},....,A_{i,k})$ in our collection.