# 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? – Luke Mathieson Nov 16 '13 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$.
• Moreover, what is $x^k$? Is it a coefficient? – lars Oct 19 '13 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 Oct 19 '13 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. – Yuval Filmus Oct 20 '13 at 0:20