Balance Those p's. Topic: Algebra/Polynomials/S&S. Level: Olympiad.

Problem: (Stanford Putnam Practice) A finite sequence $ a_1, a_2, \ldots, a_n $ is called $ p $-balanced if any sum of the form $ a_k+a_{k+p}+a_{k+2p}+\cdots $ is the same for $ k = 1, 2, \ldots, p $. Prove that if a sequence with $ 50 $ members is $ p $-balanced for $ p = 3, 5, 7, 11, 13, 17 $, then all its members are equal to zero.

Solution: Let $ P(x) = a_{50}x^{49}+a_{49}x^{48}+\cdots+a_2x+a_1 $. Recall the strategy of isolating certain terms in a polynomial. Denoting $ \omega_p $ by the $ p $th root of unity, we have

$ \displaystyle a_1+a_{1+p}+a_{1+2p}+\cdots = \frac{1}{p} \sum_{i=0}^{p-1} P(\omega_p^i) $

because all of the terms will cancel out by the identity $ 1+\omega_p+\omega_p^2+\cdots+\omega_p^{p-1} = 0 $ except for the terms in which the power of the exponent is divisible by $ p $, in which case $ \omega_p^p = 1 $. Similarly, using the polynomials $ xP(x), x^2P(x), \ldots, x^{p-1}P(x) $ we obtain

$ \displaystyle a_k+a_{k+p}+a_{k+2p}+\cdots = \frac{1}{p} \sum_{i=0}^{p-1} \omega_p^{i(p+1-k)}P(\omega_p^i) $

from $ x^{p+1-k}P(x) $ and $ k = 2, 3, \ldots, p $. Hence we have a system of $ p $ equations in the variables

$ P(1), P(\omega_p), \ldots, P(\omega_p^{p-1}) $.

But if we have a system of $ p $ equations for $ p = 3, 5, 7, 11, 13, 17 $, we have a total of $ 3+5+7+11+13+17 = 56 $ equations. Since the only repeated value in the polynomial was $ 1 $ and it showed up $ 6 $ times, once for each prime, there are $ 56-5 = 51 $ distinct points on the polynomial that we now know. However, since a polynomial of degree $ 49 $ is defined by at most $ 50 $ points, it must be the zero polynomial, which means $ a_1 = a_2 = \cdots = a_{50} = 0 $, as desired. QED.

--------------------

Comment: This is an example of generating functions showing up when you least expect it, well not exactly, but it was cool anyway. The proof above is not completely rigorous because we would need to show that a polynomial of degree $ 49 $ actually cannot pass through all $ 51 $ of the points, but it's almost there.

--------------------

Practice Problem: Let $ p(n, k) $ denote the number of ways you can partition $ n $ into $ k $ parts. Show that

$ \displaystyle \sum_{k=1}^n p(n, k) = p(2n, n) $.

Also show that the number of ways $ n $ can be partitioned into unequal parts is equal to the number of ways $ n $ can be partitioned into odd parts.