First, note that because A(zi) is zero for every i, B(zi) = (B mod A)(zi). This is not a necessary step in the solution, but it does mean that we can assume that m<n because we can substitute B for B mod A everywhere.
To make things even simpler, we'll assume that m=n by omitting the assumption that B0 ≠ 0. Throughout the remainder of this solution, we will use n to signify the degree of both polynomials. We will also assume w.l.o.g. that A0=1. (It cannot be zero, because we know that there are n distinct solutions, so if it isn't already one simply divide all coefficients of A by A0. This will result in a polynomial with A0=1 without changing this polynomial's solution set.)
The sum of all B(zi) and the product of all B(zi) are special cases of polynomials in n variables (z1,..., zn) of maximum degree n for any variable, that are symmetric, in the sense that they cannot be changed by an order permutation in the variables. (A polynomial, P, in two variables, for example, will be said to be symmetric if for any x and y, P(x,y) = P(y,x).) We will prove the general case, showing that a closed form formula can be found for any symmetric polynomial.
A symmetric polynomial is a linear combination of what we shall call "symmetric monomials". We define a "symmetric monomial" as the sum of a monomial over all order permutations of its arguments, omitting any multiplications by scalar constants in the result.
Choosing a good notation to use for specialized polynomials is an important first step in solving this riddle. We begin this here by denoting symmetric monomials by uppercase X arguments, as in the following example:
[X12X2X3] = x12x2x3 + x22x1x3 + x32x2x1
We will use the convention that the Xi are numbered sequentially 1, 2, 3,..., n and that their exponents are listed in a monotone decreasing (in the weak sense) order. Note that all n Xi parameters are listed, including any whose exponents are zero. This convention ensures that each symmetric monomial has a unique representation.
The key to this riddle is in understanding how the Ai coefficients relate to the zi solutions. Specifically, note that A is the product of (x-zi) for all zi. This means that Ak is the sum of the product of any subset of size k of the set of all zi. The value of Ak can therefore be represented as a symmetric polynomial of maximum degree 1 for any parameter (except when k=0).
Because we are interested in creating polynomials of maximum degree at most n for any parameter, we will multiply several (at most n) of the polynomials described by the Ai together (potentially multiplying some of the Ai by themselves).
Consider the symmetric polynomial described by such a product. For example, consider the polynomial in zi described by A5A4A22
This is a symmetric polynomial, and should therefore be expressable as a linear combination of symmetric monomials, but the actual linear combination may be rather lengthy. Instead of trying to write this polynomial in Xi notation, let us adopt a different notation, using uppercase Z characters for this type of polynomial. The notation will be as follows: the symmetric polynomial for Ai is [X11X21 ... Xi1Xi+10 ... Xn0]. Multiplying several Ai does not result in a symmetric polynomial that is denoted by the sum of the exponents of the Xi involved, but we will sum the exponents anyway and replace the X's with Z's. So, for example, the polynomial associated with A5A4A22 is [X1X2X3X4X5X60 ...] * [X1X2X3X4X50 ...] * [X1X2X30 ...] * [X1X2X30 ...] and this will be denoted [Z14Z24Z32Z42Z51Z60 ... Zn0]. This polynomial satisfies the condition that if P = [Z14Z24Z32Z42Z51Z60 ... Zn0] then P(z1, ..., zn) = A5A4A22.
As before, the Z's will be listed by Z1, Z2, ..., Zn ordering and all will be listed, even if their exponents are zero. It is easy to verify that any product of Ai-related polynomials has a unique representation in this notation, and that the exponents of the Zi will always be a monotone weakly-decreasing sequence. Clearly, the reverse is also true: any Zi polynomial has a unique representation as the polynomial related to the product of particular Ai's.
Summing up what we have so far: the complex number that is the value of any Zi polynomial at the point (z1, ..., zn) can be calculated by a closed form formula of Ai's and each Zi polynomial is a linear combination of the Xi polynomials, just like any other symmetric polynomial.
The only missing bit to this puzzle is that we still need to prove that the Xi polynomials can be described by linear combinations of Zi polynomials.
Let us rephrase this. Let us list all Zi polynomials with maximum degree up to n according to lexicographic ordering. (The ordering relates to the exponents, in the order in which they appear.) The i'th polynomial in this ordering will be denoted Z[i]. Let us also do the same for the Xi polynomials and define X[i] accordingly. Now, consider a matrix M where the i'th element in the j'th row is the coefficient of X[i] in the linear combination that results in Z[j]. Multiplying by M is a way to make the Xi polynomials into Zi polynomials. We want to know whether it is possible to reverse this process, and to calculate the Xi from the Zi. Equivalently, we ask whether M is an invertible matrix.
The answer is that it is. To prove this, all one needs to do is to observe that M is a lower triangular matrix and that its diagonal is composed entirely of non-zero elements. In other words, the linear combination of Z[j] includes X[j], but never any X[i] with i>j. (A Z polynomial is composed in part from the X polynomial with the same exponents, but it is never composed of any X polynomial with an exponent list that is lexicographically larger.) This is easy to verify, based on the definition of Z[j].
Q.E.D.
This riddle was brought to my attention by Ito Kang. It is a generalization over a question that appeared in the 2003 AIME, and is now used as one of several AIME practice questions.
Readers who wish to have more explicit formulae for converting [Z] polynomials to [X] polynomials are welcomed to look up "Newton-Girard formulas" on the Internet.