|
||
Title: Polynomial Puzzle Post by THUDandBLUNDER on Jan 27th, 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(x1,x2, x3,.......xm) = 1 whenever x1 + x2 + x3 + ....... + xm = 1? |
||
Title: Re: Polynomial Puzzle Post by Eigenray on Mar 9th, 2007, 11:31pm There are 2C(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 2C(n+m-1,m) solutions, and so 2C(n+m-1,m) - 2C(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| = x1+...+xm. 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.gifaIXI, then this says that P(X) can be obtained from 1 = X0 by replacing XI with |X|XI, aI times. Doing this in order of increasing |I|=i1+...+im, it's clear that in order for P(X) to end up with nonnegative coefficients, then we can only replace XI 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 XI. 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. |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |