Olympiad Level Counting - How Many Subsets of {1,…,2000} Have a Sum Divisible by 5?
3Blue1Brown via YouTube
Overview
Google, IBM & Meta Certificates – 40% Off
One plan covers every Professional Certificate on Coursera.
Unlock All Certificates
Explore an advanced mathematics lesson on generating functions and complex numbers for solving a challenging counting problem. Dive into an Olympiad-level question about subsets with sums divisible by 5, starting with simpler examples before tackling the main puzzle. Learn evaluation tricks, discover the power of roots of unity, and gain insights into problem-solving techniques. Follow along with animated explanations, recaps, and key takeaways in this 35-minute video that bridges combinatorics, algebra, and number theory.
Syllabus
- Puzzle statement and motivation.
- Simpler example.
- The generating function.
- Evaluation tricks.
- Roots of unity.
- Recap and final trick.
- Takeaways.
Taught by
3Blue1Brown