Author |
Topic: Polynomial Puzzle (Read 863 times) |
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Polynomial Puzzle
« on: Jan 27th, 2007, 6:46am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Polynomial Puzzle
« Reply #1 on: Mar 9th, 2007, 11:31pm » |
Quote Modify
|
There are 2C(n+m,n) polynomials in m variables with degree  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 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) =  aIXI, 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 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print