46th Putnam 1985 Problem A5 Let f n (x) = cos x cos 2x ... cos nx. For which n in the range 1, 2, ... , 10 is the integral from 0 to 2π of f n (x) non-zero? Solution
: 3, 4, 7, 8. Note first that since cos x = cos(2π - x), the integral is twice the integral over 0 to π, so it is sufficient to consider the smaller range. cos(nπ/2 - x) = (-1) n cos(nπ/2 + x). So cos(nπ/2 - x)) = cos(nπ/2 + x) for n even, and - cos(nπ/2 + x) for n odd. Hence for n = 1, 2, 5, 6, 9, 10, f n (π/2 - x) = - f n (π/2 + x) and so the integral over 0 to π is zero. It remains to consider the cases n = 3, 4, 7, 8. I cannot see a neat way of proving them non-zero. What follows is an inelegant proof using cos a cos b = (cos(a+b) + cos(a-b) )/2 repeatedly. So cos x cos 3x = 1/2 cos 4x + 1/2 cos 2x. So f 3 (x) = 1/2 cos 2 2x + 1/2 cos 2x cos 4x = 1/2 cos 2 2x + 1/4 cos 2x + 1/4 cos 6x. The integral of the first term is positive and the integrals of the second and third terms are zero. So f 3 has non-zero integral. Similarly, f 4 (x) = (cos x cos 2x) (cos 3x cos 4x) = 1/4 (cos x + cos 3x)(cos x + cos 7x) = 1/4 cos 2 x + 1/8 (cos 2x + cos 4x + cos 6x + cos 8x + cos 4x + cos 10x). All terms except the first integrate to zero and the first has a non-zero integral. Hence f 4 has non-zero integral. Similarly, f 7 (x) = cos x (cos 2x cos 3x) (cos 4x cos 5x) (cos 6x cos 7x) = 1/8 cos x (cos x + cos 5x)(cos x + cos 9x)(cos x + cos 13x) = 1/8 cos x( cos 2 x + cos x cos 5x + cos x cos 9x + cos 5x cos 9x)(cos x + cos 13x) = 1/16 cos x (1 + cos 2x + cos 4x + cos 6x + cos 8x + cos 10x + cos 4x + cos 14x)(cos x + cos 13x) = 1/32 cos x (cos x + cos x + cos 3x + 2cos 3x + 2cos 5x + cos 5x + cos 7x + cos 7x + cos 9x + cos 9x + cos 11x + cos 13x + cos 15x + cos 11x + cos 15x + 2 cos 9x + 2 cos 17x + cos 7x + cos 19x + cos 5x + cos 21x + cos 3x + cos 23x + cos x + cos 27x) = 1/32 ( 3cos 2 x + other terms), where the other terms all have the form cos ax cox bx with a and b unequal and hence integrate to zero. So f 7 has non-zero integral. Finally, f 8 (x) = 1/16 (cos x + cos 3x)(cos x + cos 7x)(cos x + cos 11x)(cos x + cos 15x) = 1/32 (1 + 2 cos2x + 2cos 4x + cos 6x + cos 8x + cos 10x)(cos x + cos 11x)(cos x + cos 15x) = (4 cos x + 5 cos 3x + 4 cos 5x + 4 cos 7x + 4 cos 9x + 2 cos 11x + 2 cos 13x + 2 cos 15x + cos 17x + cos 19x + cos 21x)(cos x + cos 15x) = 1/64 (6 + other terms). So f 8 has non-zero integral. A neater approach is due to Xiannan Li First establish by induction that the sum over all 2 n terms cos(+-A+-B+-C + ... ), where we take every possible sign combination, is just 2 n cos A cos B ... .Now observe that the integral of cos mx is zero if m is non-zero and 2π if m is zero. Thus the integral given is non-zero iff there is some sign combination for which 1 +- 2 +- 3 +- ... +- n = 0. If n = 4k, we have (1 + 4k) - (2 + 4k-1) + ... - (2k + 2k+1) = 0. If n = 4k+3, we have (1 - 2 + 3) + (4 + 4k+3) - (5 + 4k+2) + ... - (2k+1 + 2k+2) = 0. If n = 1 or 2 mod 4, then 1 + 2 + ... + n = n(n+1)/2 is odd, so there cannot be a sign combination. Thus the integral is non-zero iff n = 0 or 3 mod 4. 46th Putnam 1985 © John Scholes jscholes@kalva.demon.co.uk 7 Jan 2001 Last updated 4 Aug 03