A Subset-Sum Puzzle: How Many Sums Are Divisible by Five?

ZUSAMMENFASSUNG

In 30 Sekunden

3Blue1Brown poses a counting problem about subsets of the integers from 1 to 2,000. A five-number example illustrates the question; the short clip points to a longer video for the solution.

1The questionCount subsets of {1, …, 2000} whose elements add up to a multiple of five.
2A smaller exampleAmong the 32 subsets of {1, 2, 3, 4, 5}, eight have a sum divisible by five.
3An exact countThe challenge is to find the precise answer for the larger set, not just estimate it.

Das Wichtigste

The problem asks for subsets whose element sums are divisible by five.
The set {1, 2, 3, 4, 5} has 32 subsets, eight of which have sums divisible by five.
The full set has 2^2000 subsets, making the exact count a much larger challenge.

ThemenMathematics Education

VOLLTEXT

Den bearbeiteten Text nach Kapiteln lesen

Transkript zeigen

Nur das Transkript

The puzzle and a small example

The speaker introduces the subset-sum question and illustrates it with five numbers.

How many subsets of {1, 2, 3, …, 2000} have elements that sum to a multiple of five? The question is easy to state, but finding an exact count is the challenge.

FOLIE 1 / 1The five-number exampleThe diagram lists subsets and their sums, illustrating which totals are divisible by five.

Start with the smaller set {1, 2, 3, 4, 5}. It has 2^5 = 32 subsets. If you add the elements in each subset and group the results by sum, eight have a sum divisible by five; the empty subset counts because its sum is zero.

The larger challenge

The exact count for 2,000 numbers requires a deeper technique, explained in the linked full video.

For the set through 2,000, there are 2^2000 subsets. A rough estimate might be tempting, but the problem asks for the exact answer. The speaker points to a surprising mathematical technique in the [full video](https://youtu.be/bOXCLR3Wric); this short clip does not give the solution.