- Thread starter
- #1

- Thread starter jacks
- Start date

- Thread starter
- #1

- Feb 13, 2012

- 1,704

For the reasons explained in the successive post of C.B. this post is canceled and the solution must be found... sorry!...

Kind regards

$\chi$ $\sigma$

Kind regards

$\chi$ $\sigma$

Last edited:

- Jan 26, 2012

- 890

Except there are cubics with coefficients selected from those 8 such that the quintic has duplicate coefficients (and others with one or more coefficients not from the 8).If 'polynomials with distinct coefficients' means 'different polynomials' the solution is easy: the requested number is equal to the number of polynomials of degree 3 that can be constructed with a set of 8 coefficients, i.e. $\displaystyle n= 8^{4}= 4096$...

Kind regards

$\chi$ $\sigma$

CB

- Moderator
- #4

- Feb 7, 2012

- 2,807

Start by dividing the fifth degree polynomial $ax^5+bx^4+cx^3+dx^2+ex+f$ by $x^2-x+1$: $$ax^5+bx^4+cx^3+dx^2+ex+f = (x^2-x+1)\bigl(ax^3 + (a+b)x^2 + (b+c)x + (d+c-a)\bigr) + (d+e-b-a)x + (a+f-c-d).$$ The conditions for the remainder to be zero are $$\boxed{\begin{array}{c}a+b = d+e, \\ a+f = c+d. \end{array}}$$ So you are looking for the number of sextuplets $(a,b,c,d,e,f)$ consisting of six distinct elements from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that satisfy the boxed conditions.Find the number of polynomials of degree $5$ with distinct coefficients from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that are divisible by $x^2 - x + 1$

I do not see any straightforward method to count that number. In fact, the easiest way might be to generate a computer listing of all such sextuplets.

- Feb 13, 2012

- 1,704

Let's write the 5 degree polynomial as $\displaystyle P(x)= a_{5}\ x^{5} + a_{4}\ x^{4} + a_{3}\ x^{3} + a_{2}\ x^{2} + a_{1}\ x + a_{0}$. If $\displaystyle x^{2} - x +1$ divides P(x), then $\displaystyle e^{i\ \frac{\pi}{3}}$ as well as $\displaystyle e^{- i\ \frac{\pi}{3}}$ is a root of P(x), so that we can write...Find the number of polynomials of degree $5$ with distinct coefficients from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that are divisible by $x^2 - x + 1$

$\displaystyle a_{5}\ e^{i\ \frac{5}{3}\ \pi} + a_{4}\ e^{i\ \frac{4}{3}\ \pi} + a_{3}\ e^{i\ \pi} + a_{2}\ e^{i\ \frac{2}{3}\ \pi} + a_{1}\ e^{i\ \frac{1}{3}\ \pi} + a_{0}= (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\ \pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

Observing (1) we note that all the triplets $\displaystyle a_{0},a_{1},a_{2}$ combined with the conditions $\displaystyle a_{3}=a_{0}, a_{4}=a_{1}, a_{5}=a_{2}$ satisfies (1) so that the requested number of polynomials is $\displaystyle 8^{3}= 512$...

Kind regards

$\chi$ $\sigma$

- Feb 13, 2012

- 1,704

Observing more carefully (1) we discover that the condition $\displaystyle a_{2}-a_{5}= a_{1}-a_{4}=a_{0}-a_{3}=0$ is not the only solving way because the basic equality $\displaystyle e^{i\ \frac{2}{3}\ \pi} - e^{i\ \frac{1}{3}\ \pi} + 1=0$ implies that $\displaystyle a_{2}-a_{5}= a_{4}-a_{1}=a_{0}-a_{3}= \pm 1$ is also a solving way and that means that the requested number of polynomials is $\displaystyle 8^{3} +2\ \cdot 7^{3}= 1198$...Let's write the 5 degree polynomial as $\displaystyle P(x)= a_{5}\ x^{5} + a_{4}\ x^{4} + a_{3}\ x^{3} + a_{2}\ x^{2} + a_{1}\ x + a_{0}$. If $\displaystyle x^{2} - x +1$ divides P(x), then $\displaystyle e^{i\ \frac{\pi}{3}}$ as well as $\displaystyle e^{- i\ \frac{\pi}{3}}$ is a root of P(x), so that we can write...

$\displaystyle a_{5}\ e^{i\ \frac{5}{3}\ \pi} + a_{4}\ e^{i\ \frac{4}{3}\ \pi} + a_{3}\ e^{i\ \pi} + a_{2}\ e^{i\ \frac{2}{3}\ \pi} + a_{1}\ e^{i\ \frac{1}{3}\ \pi} + a_{0}= (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\ \pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

Observing (1) we note that all the triplets $\displaystyle a_{0},a_{1},a_{2}$ combined with the conditions $\displaystyle a_{3}=a_{0}, a_{4}=a_{1}, a_{5}=a_{2}$ satisfies (1) so that the requested number of polynomials is $\displaystyle 8^{3}= 512$...

Kind regards

$\chi$ $\sigma$

- Moderator
- #7

- Feb 7, 2012

- 2,807

If you take the real part of (1) then you find that $\frac12((a_{2}-a_{5}) +\frac12(a_{1}-a_{4}) + (a_{0}-a_{3}) = 0$. If you take the imaginary part of (1) then you get $a_{2}-a_{5} = a_{1}-a_{4}$. Those equations are equivalent to the boxed equations in my previous comment. These are the only conclusions that you can deduce from (1), and chisigma's following claim is incorrect:$\displaystyle a_{5}\ e^{i\ \frac{5}{3}\ \pi} + a_{4}\ e^{i\ \frac{4}{3}\ \pi} + a_{3}\ e^{i\ \pi} + a_{2}\ e^{i\ \frac{2}{3}\ \pi} + a_{1}\ e^{i\ \frac{1}{3}\ \pi} + a_{0}= (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\ \pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

The original problem was:Observing more carefully (1) we discover that the condition $\displaystyle a_{2}-a_{5}= a_{1}-a_{4}=a_{0}-a_{3}=0$ is not the only solving way because the basic equality $\displaystyle e^{i\ \frac{2}{3}\ \pi} - e^{i\ \frac{1}{3}\ \pi} + 1=0$ implies that $\displaystyle a_{2}-a_{5}= a_{4}-a_{1}=a_{0}-a_{3}= \pm 1$ is also a solving way and that means that the requested number of polynomials is $\displaystyle 8^{3} +2\ \cdot 7^{3}= 1198$...

I understood the phrase in red to mean that, in each such polynomial, the six integers $a_0,a_1,a_2,a_3,a_4,a_5$ should be distinct elements of the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$. That condition makes the problem very much harder to solve.Find the number of polynomials of degree $5$ with distinct coefficients from the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$ that are divisible by $x^2 - x + 1$

- Jan 26, 2012

- 890

When I get the chance I will cut some code to directly count the number of polynomials with the required property (but being Saturday that will be after household duties which will be in about 9 hours time)If you take the real part of (1) then you find that $\frac12((a_{2}-a_{5}) +\frac12(a_{1}-a_{4}) + (a_{0}-a_{3}) = 0$. If you take the imaginary part of (1) then you get $a_{2}-a_{5} = a_{1}-a_{4}$. Those equations are equivalent to the boxed equations in my previous comment. These are the only conclusions that you can deduce from (1), and chisigma's following claim is incorrect:

The original problem was:

I understood the phrase in red to mean that, in each such polynomial, the six integers $a_0,a_1,a_2,a_3,a_4,a_5$ should be distinct elements of the set $\left\{1, 2, 3, 4, 5, 6, 7, 8\right\}$. That condition makes the problem very much harder to solve.

CB

- Feb 13, 2012

- 1,704

In order to avoid confusion we search first

$\displaystyle (a_{2}-a_{5})\ e^{i\ \frac{2}{3}\\pi} + (a_{1}-a_{4})\ e^{i\ \frac{1}{3}\ \pi} + (a_{0}-a_{3})=0$ (1)

Because $\displaystyle e^{i\ \frac{\pi}{3}}$ is a root of $\displaystyle x^{2} - x +1$, the equation (1) will be satisfied for...

$\displaystyle a_{2}-a_{5} = a_{4}-a_{1}= a_{0}-a_{3}= 0, \pm 1, \pm 2,...,\pm 7$ (2)

'Taking it easy' in little time You 'discover' [unless some more errors of me...] that the whole number of polynomial divisible by $x^{2} - x +1$ is...

$\displaystyle n= 8^{3} + 2\ \sum_{k=1}^{7} (8-k)^{3}= 2080$ (3)

Now to proceed we have to clarify what means 'with distinct coefficients' in the original post...

Kind regards

$\chi$ $\sigma$

- Moderator
- #10

- Feb 7, 2012

- 2,807

$ a_{2}-a_{5} = a_{4}-a_{1}= a_{0}-a_{3}= k$, where $k\in \{0, \pm 1, \pm 2,...,\pm 7\}.$

Clearly there are no solutions for $k=0$ (because then some of the coefficients would have to be equal). When $k=1$, the possible values for each of the pairs $(a_2,a_5),\,(a_4,a_1),\,(a_0,a_3)$ are $(2,1),\,(3,2),\,(4,3),\,(5,4),\,(6,5),\,(7,6),\,(8,7).$ I counted 10 possible ways to select three of those pairs comprising six different numbers. For each such triple there are 3!=6 ways to assign them to the three pairs $(a_2,a_5),\,(a_4,a_1),\,(a_0,a_3)$, giving a total of 60 solutions to (2) with $k=1.$ There are also 60 solutions for $k=-1$. So 120 solutions for $k=\pm1.$

Similar computations give 72 solutions for $k=\pm2$, 48 solutions for $k=\pm3$ and also for $k=\pm4$, 12 solutions for $k=\pm5$ (and none for $k=\pm6$ or $\pm7$). That gives a grand total of $\boxed{300}$ solutions for the problem. (I'll be interested to see if the Captain's computer tally agrees with that!)

- Jan 26, 2012

- 890

Code:

```
>function CountDiv()
$
$ global I;
$
$ count=0;
$ OKs=0;
$ r1=0.5*(1+sqrt(3)*I);
$ r2=0.5*(1-sqrt(3)*I);
$ arry1=1:8;
$
$ for idx1=1 to 7
$ for idx2=idx1+1 to 8
$ aa=nonzeros(arry1!=idx1);
$ arry2=arry1(aa);
$ aa=nonzeros(arry2!=idx2);
$ arry2=arry2(aa);
$
$ for jdx=1 to fak(6)-1
$ count=count+1;
$ c1=polyval(arry2,r1);
$ if c1~=0
$ c2=polyval(arry2,r2);
$ if c2~=0
$ OKs=OKs+1;
$ endif
$ endif
$ arry2=next(arry2);
$ end
$ end
$ end
$
$ return {count, OKs}
$ endfunction
>{C,O}=CountDiv;[C,O]
20132 300
```