Problem 31

ThePerfectHacker · #1 $Old$ 07-17-2007, 08:43 PM

1)Let $f(x),g(x),h(x),r(x)$ be polynomials such that:
$f(x^5)+xg(x^5)+x^2h(x^5)=(x^4+x^3+x^2+x+1)r(x)$ .
Show that $x-1$ divides $f(x)$ .

2)Below is a unit circle with 7 equally spaced points. Find the product of all the line segments shown.

mathisfun1 · #2 $Old$ 07-18-2007, 12:40 PM

1) We'll show that f(1)=0; the result follows. Write $f(x^5) = (x^4+x^3+x^2+x+1)r(x)-xg(x^5)-x^2h(x^5) \ \ (*)$ . Note that the RHS can only have powers of x that are multiples of 5. $xg(x^5)$ and $x^2h(x^5)$ have only powers of x congruent to 2 and 3 mod 5, respectively. Choose coefficients for the RHS of (*) such that the terms with powers of x congruent to 3 and 4 (mod 5) vanish. Write $r(x)=a_0+a_1x+a_2x^2+...+a_nx^n$ . The first term of the RHS of (1) is $a_0$ . Write the highest power of x that is a mulitple of 5 as $5k$ . Consider when k=1. Now, the $x^4$ term has coefficient $\Sigma_{i=0}^m a_i=0$ . If m<4 then the coefficient for $x^5$ is $\Sigma_{i=1}^m a_i = -a_0$ , in which case x=1 is a root for f(x). If m=4 then there are there are two possibilities. If $x^5$ has coefficient $\Sigma_{i=1}^4 a_i = -a_0$ then we're done. If instead the coefficient is $\Sigma_{i=1}^{5} a_i = a_5-a_0$ , then $f(1)$ (the sum of the coefficients of $x^0$ and $x^5$ ) equals $a_5$ , in which case we're done since $a_5=0$ (being the coefficient of $x^9$ . Induct on k.

malaygoel · #3 $Old$ 07-19-2007, 12:33 AM

2) I got the answer $12(sinx + sin2x + sin3x)$
where $x=\frac{\pi}{7}$

ThePerfectHacker · #4 $Old$ 07-19-2007, 07:23 AM

Quote:

Originally Posted by malaygoel $View Post$

2) I got the answer $12(sinx + sin2x + sin3x)$
where $x=\frac{\pi}{7}$

Sorry,

, you made a mistake.

mathisfun1 · #5 $Old$ 07-19-2007, 08:36 AM

From law of cosines, each segment connecting two adjacent points on the perimeter have length $2\sin{\frac{\pi}{7}}$ . Each of the next-longest segments has length $2\sin{\frac{2\pi}{7}}$ , and a longest segment has length $2\sin{\frac{3\pi}{7}}$ . There are seven segments of each length, so the product is $(8\sin{\frac{\pi}{7}}\sin{\frac{2\pi}{7}}\sin{\frac{3\pi}{7}})^7$ . Using the well-known fact that $\sin{\frac{\pi}{7}}\sin{\frac{2\pi}{7}}\sin{\frac{3\pi}{7}}=\frac{\sqrt 7}{8}$ Trigonometry Angles--Pi/7 -- from Wolfram MathWorld, our answer is $243\sqrt{7}$ .

ThePerfectHacker · #6 $Old$ 07-19-2007, 09:41 AM

Quote:

Originally Posted by mathisfun1 $View Post$

our answer is $243\sqrt{7}$ .

Good job! See if you can generalize this. Given a $n\geq 2$ points on a unit circle find the product of all $n(n-1)/2$ segments.

malaygoel · #7 $Old$ 07-19-2007, 09:15 PM

if n is odd
it is $x^n$
where x is
$2^{\frac{n-1}{2}}sin\frac{2\pi}{n}sin\frac{4\pi}{n}...sin\frac{(n-1)\pi}{n}$

ThePerfectHacker · #8 $Old$ 07-19-2007, 09:23 PM

Quote:

Originally Posted by malaygoel $View Post$

if n is odd
it is $x^n$
where x is
$2^{\frac{n-1}{2}}sin\frac{2\pi}{n}sin\frac{4\pi}{n}...sin\frac{(n-1)\pi}{n}$

I am not saying that the answer is wrong because I have not checked it but it can be greatley simplified.

ThePerfectHacker · #9 $Old$ 07-22-2007, 07:22 PM

Both of the problems I posted require the nice application of Complex Numbers.

The first problem was from the United States national competition. My solution differs slightly from the offical solution which is a little bit more elementary.

We will use something called the roots of unity. Given the equation $z^n=1$ there are exactly $n$ complex solution given by:
$\left\{ \cos \frac{2\pi 0}{n}+i\sin \frac{2\pi 0}{n} , \cos \frac{2\pi}{n} + i \sin \frac{2\pi}{n}, ... , \cos \frac{2\pi (n-1)}{n}+i\sin \frac{2\pi (n-1)}{n} \right\}$
Hence,
$\left\{ \cos \frac{2\pi k}{n} + i\sin \frac{2\pi k}{n} \right\} \mbox{ for }0\leq k\leq n-1$
Is a complete set of solutions.
Now if $k\geq 1$ and $\gcd(k,n)=1$ then if $\zeta = \cos \frac{2\pi k}{n}+i\sin \frac{2\pi k}{n}$ then $\{\zeta , \zeta^2 ,...,\zeta^n\}$ is a complete set of solution. So that is basically what you need to know. I write them here as a chance to learn if you never did.

Now returning to the problem. We want to show $x-1$ divides $f(x)$ which is equivalent to saying $1$ is a zero of $f(x)$ , i.e. $f(1)=0$ .

Before doing the problem there is one thing you need to know about roots of unity. The sum of the roots of unities is zero!

We know that,
$f(x^5)+xg(x^5)+x^2h(x^5)=(x^4+x^3+x^2+x+1)r(x)$
Let $\zeta = \cos \frac{2\pi}{5}+i\sin \frac{2\pi}{5}$ .
Substitute that to get,
$f(1)+\zeta g(1) + \zeta^2 h(1) = 0$
Now $\zeta^2$ generates the set of roots of unity because $\gcd(2,5)=1$ .
Thus,
$f(1)+\zeta^2 g(1)+\zeta^4 h(1) = 0$ .
Now $\zeta^4$ also generates the set of roots of unitys because $\gcd(4,5)=1$ .
Thus,
$f(1)+\zeta^4g(1)+\zeta^3h(1)=0$ .

Note, we wrote $\zeta^3$ since $\zeta^8 = \zeta^5 \zeta^3=\zeta^3$ .

What he have above is a homogenous system of linear equations. Note the determinant,
$\left| \begin{array}{ccc}1&\zeta&\zeta^2\\1&\zeta^2&\zeta^4 \\ 1&\zeta^4&\zeta^3 \end{array} \right| \not = 0$ .
Which means there are only trivial solution.
Hence,
$f(1)=0$ .
Q.E.D.

ThePerfectHacker · #10 $Old$ 07-23-2007, 03:34 PM

The second problem is an extremely nice and difficult problem I found in a math book. I had to spend several hours on it. One thing that makes it difficult is the familarity with a beautiful identity:
$\sin \frac{\pi}{n} \sin \frac{2\pi}{n} ... \sin \frac{(n-1)\pi}{n} = \frac{n}{2^{n-1}}$
Which can be found here.

But I will give the derivation of that identity here because there I did it a little messy.

Given the polynomial,
$\Phi(z) = 1+z+z^2+...+z^n$
It is a known result (see "roots of unity" above) that we can factor it as,
$\Phi(z)=(z - \zeta)(z-\zeta^2)...(z-\zeta^{n-1})$ where $\zeta = \cos \frac{2\pi}{n}+i\sin\frac{2\pi}{n}$ (since $(z-1)\Phi(z) = z^n-1$ ).
Thus,
$|\Phi(z)| = |z-\zeta||z-\zeta^2|...|z-\zeta^{n-1}|$ (where $|x+iy|=\sqrt{x^2+y^2}$ , called the "absolute value" of complex number).
Thus,
$n=|\Phi(1)| = |1-\zeta|...|1-\zeta^{n-1}|$ .
But (details can be found in link),
$|1-\zeta^k| = 2\sin \frac{\pi k}{n} \mbox{ for }1\leq k\leq n$ .
Thus,
$\sin \frac{\pi}{n} \sin \frac{2\pi}{ n}...\sin \frac{(n-1)\pi}{ n} = \frac{n}{2^{n-1}}$ .

Now we can return to the problem. Eventhough it was posed with 7 points, it works in general with $n$ points with a simple formula. Note, instead of doing this in general, I will do it specifically for $n=7$ and $n=8$ . Because there are minor changes in the proof depending whether $n$ is even or odd. And once that is done you can easily generalize this in general by following similar reasoning. I just do not want to do the general case at once because it is a little longer to type and it might be more difficult to follow.

Seven Points: Using the Roots of Unity approach again we can think of these points in the complex plane without lose of generality we can say those are $1,\zeta,\zeta^2,...,\zeta^6$ with $\zeta = \cos \frac{2\pi}{n}+i\sin \frac{2\pi}{n}$ .
Given two points $z_1 \mbox{ and }z_2$ their distance is $|z_1-z_2|$ where $| \ |$ means "absolute value" and was defined above.
Thus, we all the segments we get for $7$ points are:
$|\zeta - 1|, |\zeta^2 - 1|, ... , |\zeta^6 - 1|$
$|\zeta^2 - \zeta|, |\zeta^3 - \zeta| , ... , |\zeta^5 - \zeta|$
$|\zeta^3 - \zeta^2|, |\zeta^4 - \zeta^2|,...,|\zeta^6 - \zeta^2|$
$|\zeta^4-\zeta^3|, |\zeta^5-\zeta^3| , |\zeta^6 - \zeta^4|$
$|\zeta^5 - \zeta^4| , |\zeta^6 - \zeta^4|$
$|\zeta^6-\zeta^5|$
We just wrote them out conviently in rows, we will see why that is convient soon.

But notice that, $|\zeta^2 - \zeta| = |\zeta||\zeta - 1|= |\zeta - 1|$ . And $|\zeta^4 - \zeta^2| = |\zeta^2||\zeta^2 - 1|$ and so one.... Using this simplification trick we find:
$|\zeta - 1|, ... ,|\zeta^6 - 1|$
$|\zeta - 1|, ... , |\zeta^5 - 1|$
$|\zeta - 1|, ... , |\zeta^4 - 1|$
$|\zeta - 1|, ... , |\zeta^3 - 1|$
$|\zeta - 1||\zeta^2 - 1|$
$|\zeta - 1|$
Again we keep them conviently in those rows.

Now let us write them out using the fact that $|\zeta^k - 1| = 2\sin \frac{\pi k}{7}$ (details omiited, but this is basic trigonometry).

Thus, keeping them in convient rows,
$2\sin \frac{\pi}{7}, 2\sin \frac{2\pi }{7} , ... , 2\sin \frac{6\pi }{7}$
$2\sin \frac{\pi}{7} , 2\sin \frac{2\pi}{7}, ... , 2\sin \frac{5\pi}{7}$
$2\sin \frac{\pi}{7}, 2\sin \frac{2\pi}{7}, ... , 2\sin \frac{4\pi}{7}$
$2\sin \frac{\pi}{7}, 2\sin \frac{2\pi}{7} , 2\sin \frac{3\pi}{7}$
$2\sin \frac{\pi}{7}, 2\sin \frac{2\pi}{7}$
$2\sin \frac{\pi}{7}$

Now we need to multiply those numbers out

. But do not worry it is not that bad, we still have that identity above sines above which we never used.

Do the following steps:
-------------------------
1)Multiply all elements in Row 1. That is simply the identity above and we get $7$ .

2)Multiply all the elements in Row 2 with Row 6 and use the fact that $\sin \frac{\pi}{7} = \sin \left(\pi - \frac{\pi}{7} \right) = \sin \frac{6\pi}{7}$ . So we get the identity again! (Sneaky ... I know). Thus we get $7$ again.

3)Multiply all the elements in Row 3 with Row 5 and use the fact that $\sin \frac{\pi}{7} = \sin \frac{6\pi}{7}$ and $\sin \frac{2\pi}{7} = \sin \frac{5\pi}{7}$ . So we get the identity again! (Even more sneaky). Thus we get $7$ again.

4)We are left with Row 4. What do we pair it with we exhausted all the cases? We can pair it with itself. Meaning, let $X = 2\sin \frac{\pi}{7} \cdot 2\sin \frac{2\pi}{7} \cdot 2\sin \frac{3\pi}{7}$ .
Thus,
$X^2 = 2^6 \sin \frac{\pi}{7} \sin \frac{2\pi}{7} \sin \frac{3\pi}{7}\sin \frac{3\pi}{7}\sin \frac{2\pi}{7} \sin \frac{\pi}{7}$
Thus,
$X^2 = 2^6 \sin \frac{\pi}{7}\sin \frac{2\pi}{7}\sin \frac{3\pi}{7}\sin \frac{4\pi}{7}\sin \frac{5\pi}{7} \sin \frac{6\pi}{7}=7$
Thus,
$X=\sqrt{7}$ .

So in total when we multiply Steps 1 through 4 we get:
$\boxed{7^3\sqrt{7}}$ .

Eight Points: Follow the exact same idea as above. But here the problem gets a little easier. Because we do not need to pair the middle row to itself and take square roots. We can in fact pair everything together using the Sine Reduction trick since there is an even number of terms. The answer you should get is $8^4$ .

In General: By succesfully doing 7 and 8 points you should get the general idea. Which is the,
$\boxed{n^{n/2}}$ .

Q.E.D.