First, note that because *A*(*z*_{i}) is zero for
every *i*, *B*(*z*_{i}) =
(*B* mod *A*)(*z*_{i}). 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 *B*_{0} ≠ 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 *A*_{0}=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 *A*_{0}. This will
result in a polynomial with *A*_{0}=1 without changing this
polynomial's solution set.)

The sum of all *B*(*z*_{i}) and the product of all
*B*(*z*_{i}) are special cases of polynomials in
*n* variables (*z*_{1},..., *z*_{n})
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:

[*X*_{1}^{2}*X*_{2}*X*_{3}] =
*x*_{1}^{2}*x*_{2}*x*_{3} +
*x*_{2}^{2}*x*_{1}*x*_{3} +
*x*_{3}^{2}*x*_{2}*x*_{1}

We will use the convention that the *X*_{i} 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*
*X*_{i} 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 *A*_{i}
coefficients relate to the *z*_{i} solutions. Specifically,
note that *A* is the product of (*x*-*z*_{i})
for all *z*_{i}. This means that *A*_{k}
is the sum of the product of any subset of size *k* of the set of
all *z*_{i}. The value of *A*_{k} 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 *A*_{i} together (potentially
multiplying some of the *A*_{i} by themselves).

Consider the symmetric polynomial described by such a product. For example,
consider the polynomial in *z*_{i} described by
*A*_{5}*A*_{4}*A*_{2}^{2}

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
*X*_{i} 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 *A*_{i} is
[*X*_{1}^{1}*X*_{2}^{1} ...
*X*_{i}^{1}*X*_{i+1}^{0}
... *X*_{n}^{0}]. Multiplying several
*A*_{i} does not result in a symmetric polynomial that is
denoted by the sum of the exponents of the *X*_{i}
involved, but we will sum the exponents anyway and replace the *X*'s with
*Z*'s. So, for example, the polynomial associated with
*A*_{5}*A*_{4}*A*_{2}^{2} is
[*X*_{1}*X*_{2}*X*_{3}*X*_{4}*X*_{5}*X*_{6}^{0} ...] *
[*X*_{1}*X*_{2}*X*_{3}*X*_{4}*X*_{5}^{0} ...] *
[*X*_{1}*X*_{2}*X*_{3}^{0} ...] *
[*X*_{1}*X*_{2}*X*_{3}^{0} ...]
and this will be denoted
[*Z*_{1}^{4}*Z*_{2}^{4}*Z*_{3}^{2}*Z*_{4}^{2}*Z*_{5}^{1}*Z*_{6}^{0} ... *Z*_{n}^{0}].
This polynomial satisfies the condition that if
*P* = [*Z*_{1}^{4}*Z*_{2}^{4}*Z*_{3}^{2}*Z*_{4}^{2}*Z*_{5}^{1}*Z*_{6}^{0} ... *Z*_{n}^{0}] then *P*(*z*_{1}, ..., *z*_{n}) =
*A*_{5}*A*_{4}*A*_{2}^{2}.

As before, the *Z*'s will be listed by *Z*_{1},
*Z*_{2}, ..., *Z*_{n} ordering and all will
be listed, even if their exponents are zero. It is easy to verify that any
product of *A*_{i}-related polynomials has a unique
representation in this notation, and that the exponents of the
*Z*_{i} will always be a monotone weakly-decreasing
sequence. Clearly, the reverse is also true: any *Z*_{i}
polynomial has a unique representation as the polynomial related to the product
of particular *A*_{i}'s.

Summing up what we have so far: the complex number that is the value of any
*Z*_{i} polynomial at the point (*z*_{1}, ...,
*z*_{n}) can
be calculated by a closed form formula of *A*_{i}'s and
each *Z*_{i} polynomial is a linear combination of the
*X*_{i} polynomials, just like any other
symmetric polynomial.

The only missing bit to this puzzle is that we still need to prove that the
*X*_{i} polynomials can be described by linear
combinations of *Z*_{i} polynomials.

Let us rephrase this. Let us list all *Z*_{i} 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 *X*_{i}
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
*X*_{i} polynomials into *Z*_{i}
polynomials. We want to know whether it is possible to reverse this process,
and to calculate the
*X*_{i} from the *Z*_{i}. 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.