Sum Free Sets

The article this week comes from the brilliant educational site MathPickle, and specifically the problem they call Bubbling Cauldrons. It’s a great, simple, puzzle to help children learn simple addition.

The premise is simple. You start with two cauldrons (or hats, or buckets …), and a collection of sequentially numbered coins: 1,2,3,4 …

The goal is to place the coins, one by one, into the two cauldrons with the restriction that you can’t place a coin into a bucket if that bucket already contains any pair of coins whose totals add up to the new coin value. For example, you can’t place the coin marked 7 into a bucket if it already contains coins 3 and 4. Mathematicians talk about these things as sum free sets; There are no pairs of numbers in any set (bucket) that add up to any other number in the set.

This problem was first investigated by the Russian mathematician Issai Schur.

The largest number of coins it is possible to place into two buckets is eight. Can you find the solution? Below is an app that allows you to experiment.

To use the app, simply tap inside the bucket of choice to place the next coin in that bucket. By default, the game starts in Hard Mode, which results in instant death on a mistake. If you fail in hard mode, your only option is to reset and start again from scratch. In Easy Mode, an undo button appears. This undo button allows the last coin placed to be removed (recursively). Want more of a challenge? Try increasing the number of buckets to three. Below are hints and solutions to the two and three bucket problems. If you want to challenge yourself, don’t click the buttons without trying! (I’ve also included the ability to play with one bucket, for completeness. You don’t really have a choice where to place each coin!)

Too easy? Try three buckets. Click the button below if you want a hint about the target you are aiming for.

Got it? Click the button below to validate your solution (or see the answer).

For more of a challenge, try a larger number of buckets. Here you can try four and five buckets. It’s a different app as I have to render the coins smaller. Also, there is no hard mode (you are welcome!)

Since first publishing this article, a couple of readers emailed me that a solution for 5 buckets is known. Thank you to Koen Timmermans and Kang Jin Cho for your correspondence.

Koen confirmed that a solution of 196 is possible and used the app to input the numbers. (It looks like we need bigger buckets!)

The sequence of answers is in OEIS, and the 196 solution was found in 2012.

Here is the N=196 solution in a differnet format, this time showing the numbers in the each bucket. When there are runs, these are shown inside square braces (inclusive).

Bucket 1: 1 2 4 8 11 22 25 50 63 69 135 140 150 155 178 183 193
Bucket 2: 3 [5, 7] 19 21 23 [51, 53] [64, 66] [137, 139] [151, 153] [180, 182] [194, 196]
Bucket 3: [9, 10] [12, 18] 20 [54, 62] [141, 149] [184, 192]
Bucket 4: 24 [26, 49] 154 [156, 177] 179
Bucket 5: [67, 68] [70, 134] 136