The Problem Pit: The Disappearing Subset Sums Problem

 

The Disappearing Subset Sums Problem: Why Can’t I Pin This Down?

I wanted my first “seriously stuck” blog post to be worthy of the name, so instead of chasing a problem that collapses with a clever trick, I picked one that looked simple, but has enough depth to swallow you whole.

The Problem:
Given a set of integers $\{1, 2, \dots, n\}$, consider all possible subset sums. For which values of $n$ is it true that every integer from 1 up to the maximum possible sum can be expressed as a subset sum?

In other words: if I take all subsets of $\{1,2,\dots,n\}$ and add their elements, do I get a perfectly “gapless” sequence of sums from 1 up to $\tfrac{n(n+1)}{2}$?

---

Step 1: Falling Into the Trap of Optimism

At first glance, I was sure the answer was “always.” Why wouldn’t it be? With small $n$, it seems so:

• For $n=1$: Subsets = $\{ \}, \{1\}$. Sums = $\{0,1\}$. Covers 1. Fine.

• For $n=2$: Subsets = sums are 0,1,2,3. We cover 1,2,3. Fine.

• For $n=3$: Sums are 0,1,2,3,4,5,6. Perfect coverage.

• For $n=4$: Sums are 0 through 10. Every number shows up.

By this point, I was writing confidently in my notebook: Clearly, by induction, this always works. That was my first false start.

---

Step 2: The Crash

The trouble started with $n=5$.

Subsets of $\{1,2,3,4,5\}$ can sum from 0 up to 15. I expected a full range. But when I checked systematically, I realized: actually, they do cover all the numbers. 1 through 15 are all present.

Okay, so far so good.

Then $n=6$. Maximum sum = 21. Do we cover everything from 1 to 21? At first, it looked fine. But then I noticed something subtle:

Try making the sum 20.

• If I use 6, I need 14 from $\{1,2,3,4,5\}$. Possible: 5+4+3+2 = 14. Great.

• If I don’t use 6, I need 20 from $\{1,2,3,4,5\}$. Impossible (max is 15).

So 20 is reachable. Fine.

But then I tried 19.

• With 6: need 13 from $\{1,2,3,4,5\}$. Yes (5+4+3+1).

• Without 6: need 19 from $\{1,2,3,4,5\}$. Impossible.

So 19 works too.

At this point, I had checked maybe 30 different subsets, scribbling frantic sums everywhere. My desk was covered with scratch paper. And every time I thought I had found a missing number, I found a way to build it.

The set $\{1,2,3,4,5,6\}$ actually does cover 1 through 21.

---

Step 3: The Suspicion

Now I was getting paranoid. Maybe it is always true. But a faint memory tugged at me — I had once read about something called “complete sequences,” and I remembered it wasn’t always this easy.

So I pushed on to $n=7$.

Max sum = 28. I started testing specific targets. Could I make 27? Yes. Could I make 26? Yes. Could I make 25? Yes.

Every time I thought there’d be a gap, I managed to wiggle out with some combination.

Was this problem too easy after all?

---

Step 4: The Wall

I finally cracked open some references — but I avoided full spoilers. I learned that the sequence of sets $\{1,2,\dots,n\}$ is indeed special: they are complete. That means they really do cover all sums without gaps.

So the problem, as I had stated it, wasn’t hard at all — it was always true.

But the real depth lies in the generalization:

For which sequences of positive integers (not just 1 through $n$) do the subset sums form a complete interval with no gaps?

That’s the rabbit hole. It’s tied to Erdős–Graham-type additive number theory, and the classification is extremely hard. Even for simple sequences like $\{1,3,4,5\}$, gaps appear, and characterizing exactly when they appear or disappear is a deep combinatorial puzzle.

---

Step 5: Reflection on Being Stuck

I had gone in expecting a small, crunchy problem, and instead what I found was:

• At first, a “trick” (check small cases, guess it always works).

• Then, endless checking, false leads, and wasted paper.

• Then, the realization: I had stumbled onto the tip of a mountain. The real problem isn’t $\{1,2,\dots,n\}$, but the general classification — which is still very much alive in research.

I didn’t solve it. I barely scratched the surface. But that was the experience I wanted: to get tangled in a problem, fight with it, feel the ground shift under me, and walk away knowing the question is deeper than it looked.

---

This, to me, is what makes a math blog exciting: not just the solution, but the feeling of being swallowed whole by something that refuses to yield.

---