Mathematical puzzles often have a knack for engaging our curiosity and sharpening our reasoning skills. The subset sum puzzle is one such brainteaser that has surfaced as part of a monthly series created in collaboration with the Museum of Mathematics (MoMath). This deceptively simple challenge involves analyzing sets of numbers to determine whether there's a guaranteed winning strategy—and for whom. Let’s unpack the puzzle and the fascinating mathematical ideas it introduces.

How does the subset sum puzzle work?

The game begins with you as the solver and a puzzle creator—let’s call them the challenger. The challenger looks at all the integers from 1 to 100 and selects 10 distinct numbers. Once this set of 10 numbers is locked in, the numbers are presented to you. The task is to identify two distinct subsets of these 10 numbers that have the same sum. A subset is just a selection of numbers from the set, and in this case, the subsets must not include the exact same elements.

For example, suppose the challenger selects the numbers 5, 7, 10, 12, 18, 20, 23, 25, 30, and 35. You might determine that the subsets {7, 10, 18, 25} and {12, 20, 30} both add up to 60. If you find subsets like these, you win the game. However, if the challenger is able to construct a set of 10 numbers where no matter how hard you try, you cannot find two subsets with the same sum, the victory goes to the challenger.

The question that defines the puzzle

The core of the problem lies in determining whether the challenger or the solver has the winning advantage. Is it possible for the challenger to choose 10 numbers from the range of 1 to 100 such that there is no pair of subsets with equal sums? Or will mathematics guarantee that the solver can always find two such subsets, regardless of the numbers the challenger picks?

Numbers, combinations, and a paradox of choice

At first glance, this might seem like a straightforward question of computation. However, the puzzle connects to a fascinating aspect of mathematics—the number of possible subsets of a set. For any set of n elements, the number of subsets is 2^n. For a set of 10 numbers, this means there are 2^10 = 1,024 subsets (including the empty subset and the full set of 10 numbers).

Among these subsets, the solver is tasked with finding two distinct ones that share the same sum. While this might sound daunting, there’s a key mathematical principle at play: the pigeonhole principle. This principle states that if you have more "pigeons" (in this case, potential subset sums) than "holes" (distinct numerical sum values), some "pigeons" must share a hole. Are there always more subsets than possible distinct sums? For this puzzle, understanding this principle is crucial to solving the mystery.

Narrowing the focus: Who is guaranteed to win?

Although the set of numbers spans 1 to 100, the act of picking only 10 numbers constrains the problem to manageable boundaries. With 10 numbers, subset sums will fall within a range, and the total number of distinct sums depends on the numbers chosen. The solver’s task depends on the challenger’s ability to avoid overlapping sums—and herein lies the challenge.

While the source material does not explicitly provide the ultimate solution, we can hypothesize two possibilities:

1. The solver wins: Given the sheer number of subsets (1,024), it may be impossible for the challenger to choose 10 numbers such that no subsets share the same sum. If this is the case, the solver always has the upper hand.
2. The challenger wins: If there exists a specific combination of 10 numbers from 1 to 100 that avoids overlapping subset sums, the solver could be left without a winning move. This would hand victory to the challenger.

The answer hinges on whether a theoretically rigorous proof can identify such a collection of numbers—or prove its impossibility.

Why this puzzle matters

Apart from being a delightful exercise in logic, the subset sum puzzle illustrates deeper mathematical concepts that underpin fields like cryptography and computational theory. For instance, finding subsets with specified properties is a common challenge in algorithm design, and real-world applications range from data compression to security algorithms.

This puzzle also demonstrates the elegance of abstract mathematical ideas. It shows how something as simple as addition can lead to rich problem spaces and require sophisticated logical reasoning.

What’s next for puzzlers?

If you’re intrigued and want to know the solution, the puzzle creator encourages you to stay tuned either via their platform or by following MoMath’s updates. As part of a larger series of monthly brainteasers, this puzzle offers a recurring opportunity to stretch your intellectual muscles and engage with a broader community of problem solvers.

Whether the subset sum puzzle ultimately favors the solver or the challenger, it will leave math enthusiasts pondering the cleverness hidden in numbers. Why not give it a try and see if you can claim victory in this game of subsets?