# Snowball Question FFT

http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf

I'm confused as to the solution for the snowball question. To start with, I have two specific questions:

(1) Each pair $a_i,b_j$ will account for one term (and why ONE term)? What is meant by term here? The coefficient, $c_k$ of the polynomial C? Or maybe the $x$ value at the $kth$ spot?

(2) Why is $c_k$ the number of such pairs?

• Could you copy the relevant information into the question (with attribution of course!) to make the question as self-contained as possible? Commented Nov 16, 2013 at 14:08

Here is the idea of the proof. Let $a_i,b_i$ be the distance thrown by the $i$th male/female. Using FFT, we calculate $$\left(\sum_i x^{a_i}\right) \left(\sum_j x^{b_j}\right) = \sum_{i,j} x^{a_i+b_j}.$$ Each pair $i,j$ satisfying $a_i + b_j = k$ contributes one term $x^k$ to the polynomial on the right. Hence the coefficient of $x^k$ is the number of pairs $i,j$ such that $a_i + b_j = k$.

If things still aren't clear, I suggest you try a few examples.

• First you didn't even try to answer my specific questions. And now we have 3 summation signs, where there were none in the solution. So I am now more confused.
– lars
Commented Oct 19, 2013 at 23:21
• Moreover, what is $x^k$? Is it a coefficient?
– lars
Commented Oct 19, 2013 at 23:23
• Finally, you need an argument to go from Each pair i,j satisfying $a_i+b_j=k$ contributes one term $x^k$ to the polynomial on the right. To the claim that the coefficient of $x^k$ = number of pairs that equal $k$
– lars
Commented Oct 19, 2013 at 23:29
• Here $x^k$ is a monomial ($x$ is known as a "formal variable"). You can also think of it as a polynomial having a single monomial. I suggest you go over the FFT algorithm again - they must have covered polynomials when they discussed the algorithm, especially given the application to multiplying univariate polynomials. Commented Oct 20, 2013 at 0:20
• Re your other comment, I agree that an argument is required, but only if you want to be very formal. Otherwise, I suggest you try a few examples and see how it works. Commented Oct 20, 2013 at 0:20