Olympiad level counting (Generating functions)

Summary by Krater

This video explains how to solve a combinatorial puzzle about counting subsets with sums divisible by five, using complex numbers, generating functions, and roots of unity.

From the video

Answers: How do you count the number of subsets of {1, 2, ..., 2000} whose elements sum to a multiple of 5?

• combinatorial puzzle
• subsets with sums divisible by five
• generating functions
• roots of unity
• complex numbers in discrete math
• Riemann hypothesis connections
• Fourier transform connections

What it concludes

• The number of subsets of {1, 2, ..., 2000} whose sum is divisible by 5 is equal to 1/5 * (2^2000 + 4 * 2^400).