Problem 17 Generating Functions

Problem 17: Generating Functions

China HSM 1994

Problem: Find the number of subsets of 1, ..., 2000, the sum of whose elements is divisible by 5. Solution: We can create a generating function f (x) = (1 + x)(1 + x2 )...(1 + x2000 ). Now we must find the sum of all coefficients of x5k in f (x), where k is a positive integer. But first, let’s look at the properties of the fifth roots of unity: ω5 = 1 1 + ω + ω2 + ω3 + ω4 = 0 1n + ω n + ω 2n + ω 3n + ω 4n = 0 iff k 6≡ 0 (mod 5) (*) Consider the polynomial we get when we completely expand f (x). Now consider the sum S = f (1) + f (ω) + f (ω 2 ) + f (ω 3 ) + f (ω 4 ), where ω is a fifth root of unity. Consider some axn in S, where n is not divisible by 5, and a is the coefficient of xn As an example, consider ax12 . Evaluating, we get ax12 = a(112 + ω 12 + ω 2(12) + ω 3(12) + ω 4(12) ) = a(1 + ω 2 + ω 4 + ω 1 + ω 3 ) = a(0) = 0. This works for x12 , and upon further examination, we can use a modular argument to see that it works for all xn when n is not divisible by 5(by * from above). However, let’s look at what happens when n IS divisible by 5. Let n = 5k for some positive integer k, and we get: ax5k = a(15k + ω 5k + ω 2(5k) + ω 3(5k) + ω 4(5k) ) = 5a. So we see that S = f (1) + f (ω) + f (ω 2 ) + f (ω 3 ) + f (ω 4 ) will give us 5 times the sum of the coefficients of all terms of the form x5k in f (x), where k is a positive integer. So the sum we S are looking for is . 5 Evaluating, we get S = 22000 + 2402 , so

S 22000 + 2402 = 5 5

Note: The technique used here is sometimes called roots of unity filtering. This same technique is used in Problem 18, so be sure to attempt it using this method before looking at the solution.

Solution was written by Sean Soni and compiled from Art of Problem Solving Forums.