wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Polynomial Puzzle
        
(Message started by: THUDandBLUNDER on Jan 27^th, 2007, 6:46am)

Title: Polynomial Puzzle
Post by THUDandBLUNDER on Jan 27^th, 2007, 6:46am

How many nth-order polynomials are there with m variables such that
i) all of their coefficients are either 0 or 1
ii) P(x₁,x₂, x₃,.......x_m) = 1 whenever x₁ + x₂ + x₃ + ....... + x_m = 1?

Title: Re: Polynomial Puzzle
Post by Eigenray on Mar 9^th, 2007, 11:31pm

There are 2^C(n+m,n) polynomials in m variables with degree http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n satisfying (i) (equivalently, a homogenous polynomial of degree n in m+1 variables).

Now, condition (ii) amounts to a system of C(n+m-1,m-1) linearly independent equations in C(n+m,m) variables. For example, if m=2, and n=4, then the matrix for the system of equations looks like
1 0 0 0 1 0 0 1 0 1 0 1 0 0 -1 1 0 -2 1 -3 0 0 1 0 0 -1 1 1 -2 3 0 0 0 1 0 0 -1 0 1 -1,

or like
1 0 1 0 0 1 0 0 0 1 0 1 -1 0 1 -2 0 0 1 -3 0 0 0 1 -1 1 0 1 -2 3 0 0 0 0 0 0 1 -1 1 -1,

whichever you prefer. If these were polynomials over an infinite field of characteristic 2 (with coefficients in the prime subfield), then there would be simply 2^C(n+m-1,m) solutions, and so 2^C(n+m-1,m) - 2^C(n+m-2,m) solutions with degree exactly n.

But it's not that simple. For m=2, the number of solutions in degree http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n seems to be

1, 2, 4, 9, 23, 66, 206, ...?

One way to generate solutions is to take a polynomial which is already a solution, pick a random term in it, and multiply it by |X| = x₁+...+x_m. If this creates coefficients larger than 1, then replace the extra terms similarly. In fact, this generates all solutions:

Suppose P(X) is as required. Then P(X)-1 must be divisible by |X|-1. But if P(X)-1 = (|X|-1)g(X), where g(X) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifa_IX^I, then this says that P(X) can be obtained from 1 = X⁰ by replacing X^I with |X|X^I, a_I times. Doing this in order of increasing |I|=i₁+...+i_m, it's clear that in order for P(X) to end up with nonnegative coefficients, then we can only replace X^I if it already appears with positive coefficient, and in order for P(X) to end up with coefficients http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1, we must replace all but at most one copy of each X^I.

Another way to look at it, for example when m=2, is to start with one checker at (0,0) in a semi-infinite checkerboard. Then repeatedly: pick a checker, and replace it with two checkers, one above and one to the right, if necessary repeating until there's no more than one checker in each square. Then we want to count positions that stay below the n-th diagonal. Really the same thing, but using checkers for some reason.