Day 4 — Combinatorics
Time: ~45 min · Topic: combinatorics
The problem
In how many ways can 12 identical balls be placed into 5 distinct boxes so that no box contains more than 4 balls?
Hint: Start with unrestricted stars and bars, then use inclusion-exclusion to remove the cases that violate the cap.
Try it yourself
Take a few minutes. Don't peek at the steps. If you get stuck, the hint above is enough to nudge you forward.
Step-by-step solution
- Without the cap, use stars and bars. Distributing 12 identical balls into 5 distinct boxes gives C(16, 4) = 1820 total ways.
- Subtract overflows. If at least one box has 5+ balls, substitute y = x - 5 for that box. The remaining distribution has C(11, 4) = 330 solutions. With 5 possible boxes, subtract 5 * 330 = 1650.
- Add back double-counted cases where two or more boxes each have 5+ balls. For each pair, the remaining sum is 2 across 5 boxes: C(6, 4) = 15. With C(5, 2) = 10 pairs, add back 10 * 15 = 150.
- Three boxes with 5+ balls would require at least 15 balls — impossible with only 12. So by inclusion-exclusion: 1820 - 1650 + 150 = 320.
Answer: 320
Why this matters
The inclusion-exclusion principle is the engine behind the Sieve of Eratosthenes — the same idea that counts balls in boxes also finds every prime number up to a billion.
This day in math: The Man Who Bottled a New Geometry
April 24, 1849 · Felix Klein
On April 25, 1849, Felix Klein was born in Düsseldorf, Prussia. He became a full professor at the astonishing age of 23 and went on to revolutionize mathematics with his 1872 Erlangen Program, which unified all of geometry under the language of symmetry and group theory. He also introduced the Klein bottle — a mind-bending surface with no inside or outside that can only exist without self-intersection in four dimensions.
Why it matters: Klein's Erlangen Program fundamentally changed how mathematicians think about geometry, showing that every type of geometry is really a study of what stays the same under certain transformations. His ideas laid the groundwork for modern topology, theoretical physics, and the role of symmetry throughout all of mathematics.
Did you know?
Einstein never actually wrote E = mc^2 in his groundbreaking 1905 paper. He originally expressed the idea as m = L/c^2, using the letter L for energy, and framed it as mass decreasing when a body releases energy — the reverse of how we usually think about the equation today.
In his 1905 paper, Einstein used "L" for energy (a convention common in German physics at the time) and concluded that a body's mass diminishes by L/c^2 when it radiates energy. The now-iconic form E = mc^2 only appeared in Einstein's later work and was popularized over the following decades. The original framing — that energy loss reduces mass — was actually a more precise statement of his discovery than the version the world came to memorize.
Done?
- Solved the problem (or read through the steps)
- Read the history note
- Read the "did you know" fact