Alex chose positive integers a, b, c, d, e, f and completely multiplied out the polynomial product (^ means exponent btw): (1 - z)^a(1 + x)^b(1 - x + x²)^c(1+x²)^d(1+x+x²)^e(1+x+x²+x³+x^4)^f After she simplified her result, she discarded any term involving x to any power larger than 6 and was astonished to see that what was left was 1 - 2x. If a d + e + f and b c + d and e c, what value of a did she choose? a) 17 b) 19 c) 20 d) 21 e) 23 Can someone help please? This problem is from the Fermat math contest. This is question 25 from the contest.

Question

Alex chose positive integers a, b, c, d, e, f and completely multiplied out the polynomial product (^ means exponent btw): (1 - z)^a(1 + x)^b(1 - x + x²)^c(1+x²)^d(1+x+x²)^e(1+x+x²+x³+x^4)^f After she simplified her result, she discarded any term involving x to any power larger than 6 and was astonished to see that what was left was 1 - 2x. If a > d + e + f and b > c + d and e > c, what value of a did she choose? a) 17 b) 19 c) 20 d) 21 e) 23 Can someone help please? This problem is from the Fermat math contest. This is question 25 from the contest.

kinggeorge · Answer

Just to clarify, in the first term, should that be $(1-x)^a$ instead of $(1-z)^a$? Or is it correct as written?

kinggeorge · Answer

So I found the solutions online, and it would be quite a pain to type out here. However, they have a quite a nice explanation that's a full two pages long over here. http://www.cemc.uwaterloo.ca/contests/past_contests/2010/2010FermatSolution.pdf

kinggeorge · Answer

long story short, the answer is E. 23

anonymous · Answer

Yes I know where the answers are. But the explanation is difficult to understand. The problem is from the 2010 fermat contest, and I can't understand the solution. Can you e

anonymous · Answer

Can you explain the solution to me if you understand it?

kinggeorge · Answer

The solution is definitely hard to follow. Is there a specific part you have in mind?

anonymous · Answer

How would you come about to the numbers that add up to 23? Also there is another solution available here: http://ca.answers.yahoo.com/question/index?qid=20100225130900AA90S21 It's much shorter, like 1/2 a page, probably less. If you could, read it and explain it to me please? I shall remain ever grateful. This solution is also easier to follow.

kinggeorge · Answer

The most important part in that proof which is explained well is the part that describes how to factor
(1 - x²) = (1 - x).(1 + x)
(1 - x³) = (1 - x).(1 + x + x²)
(1 - x^4) = (1 - x).(1 + x).(1 + x²)
(1 - x^5) = (1 - x).(1 + x + x² + x³ + x^4)
(1 - x^6) = (1 - x).(1 + x).(1 - x + x²).(1 + x + x²)
At this point, all polynomials here can't be factored farther over the integers, so we can leave them as is. 

It is important to note that each factorization is of the form$$(1-x)p(x)$$Where $p(x)$is a polynomial not divisible by $1-x$

kinggeorge · Answer

Next, he starts generating the polynomial needed. First, notice that $(1-x)^2=1-2x+x^2$ And that this is the simplest way to generate a $1-2x$ term using the polynomial $(1-x)$ and only multiplying. So he calls $$P_0=(1-x)^2=1-2x+x^2$$

kinggeorge · Answer

However, you don't want that $x^2$ term. So you can multiply by $1-x^2=(1-x)(1+x)$ to get rid of it. This works because the $x^2$ term in $1-x^2$ will be multiplied by 1, so you get a $-x^2$ to remove the original. It will also leave the $1-2x$ untouched because of the different degrees.

Thus, when you multiply it all out and simplify, you get $$P_1=1 - 2x + 2x^3 - x^4$$

kinggeorge · Answer

Just to keep track, $$P_1=(1-x)^3f(x)$$For some $f(x)$.

kinggeorge · Answer

Now, we need to get rid of the $2x^3$ term in $P_1$. Now you need to notice that $(1-x^3)^2=1-2x^3+x^6$ Which has that $-2x^3$ term we need. So we multiply $P_1$ by $(1-x^3)^2$ to get rid of the $x^3$ term and we get $$P_2=1 - 2x + 3x^4 - 3x^6 +...$$We can just put dots on the end because those terms are over 6, and will thus be discarded.

kinggeorge · Answer

Just like before, we now need to get rid of the $3x^4$ term. So we need to notice that $$(1-x^4)^3=1-3x^4+...$$Where all other terms have degree greater than 6, so we don't care about them. So if we multiply $P_2$ by this polynomial again, we get$$P_3=1 - 2x + 6x^5 - 3x^6+...$$

Once again, just to keep track, we now have that $$P_3=(1-x)^8 g(x)$$Where $g(x)$ is some polynomial not divisible by $(1-x)$.

kinggeorge · Answer

Following the same patter, we need to get rid of $6x^5$ now. Similarly, we can tell that $(1-x^5)^6=1-6x^5+...$ So we multiply again to get $$P_4=1 - 2x + 9x^6 + ...$$

This means that $$P_4=(1-x)^{8+6} \;h(x)=(1-x)^{14}\;h(x)$$

kinggeorge · Answer

Now we're on the last step. We just need to get rid of that $9x^6$. Like above, notice that $(1-x^6)^9=1-9x^6+...$ So can just multiply one more time. This means we get $$P_5=1 - 2x +...$$ Where everything with degree greater than 6 is contained in the dots. This is exactly the polynomial we're looking for. So we just need to find the degree of $(1-x)$ in the polynomial. Since we've been keeping track, this is easy.
$$P_5=(1-x)^{14+9} \;q(x)=(1-x)^{23}\;q(x)$$ Where $q(x)$ is not divisible by $(1-x)$. Thus, our answer must be $a=23$

kinggeorge · Answer

Did this help make it clearer?

anonymous · Answer

I am studying your solution in depth

anonymous · Answer

But thank you very much for your explanation. If I have a question, I'll message you =).

kinggeorge · Answer

Sounds good.

kinggeorge · Answer

I suppose I should mention one more thing now that I remember it. If you notice in the original factorization I wrote out above, each polynomial was of the form $$(1-x)p(x)$$Where $p(x)$ is a polynomial not divisible by $(1-x)$ and each $p(x)$ is of the form of one or more of the terms in $$(1 + x)^b(1 - x + x²)^c(1+x²)^d(1+x+x²)^e(1+x+x²+x³+x^4)^f$$

kinggeorge · Answer

This guarantees that the final polynomial will look like $$\large (1 - x)^a(1 + x)^b(1 - x + x²)^c(1+x²)^d(1+x+x²)^e(1+x+x²+x³+x^4)^f$$

kinggeorge · Answer

Do you still need some help understanding how the process worked?