November 2024
—————————
In the Math Corner of my November 2024 Diary I posted the following brainteaser.
Brainteaser: Browsing in Jon Millington's wee 2008 collection from the Mother Country Mathematical Snacks I came to Snack Number Ten:
Groups of numbers
If you put whole numbers, starting at 1, into two groups, how far can you get so that no two numbers and their total appear in the same group?
The idea is to plod through the positive whole numbers 1, 2, 3, 4, 5, 6, … writing each one down to make a list, as I just did … except that it is at no point allowed for any number to be in the list if it is equal to the sum of two already listed. I'll refer to this condition as "additive purity." (I made that up myself; Jon Millington is not responsible.)
So we start listing: 1, 2, … but 3 is a problem. It violates additive purity, because 1+2 = 3. If we're only allowed one list, 2 is as far as we can go.
No prob; to accomodate 3 we just start a second list. I'll refer to the lists as L1 and L2 and put each into curly brackets:
L1 = {1, 2}
L2 = {3}.
Proceeding: 4 is no problem, it goes right into L1, making it {1, 2, 4}; but then 5 is a problem, because 1+4 = 5. We can put it into L2, however, without violating L2's additive purity. The same applies to 6, because 2+4 = 6. We now have
L1 = {1, 2, 4}
L2 = {3, 5, 6}
Breezing along, 7 is no problem: it goes nicely into L1. That, however, means that 8 can't go into L1 because 1+7 = 8. Unfortunately 3+5 = 8, so 8 can't go into L2 either.
We seem to have reached the limit to how far we can take this. The limit is 7.
But wait! There is nothing in the rules to prevent us moving 7 from L1 to L2 and replacing it in L1 by 8. Neither move violates additive purity.
L1 = {1, 2, 4, 8}
L2 = {3, 5, 6, 7}
The number 9, however, is a real game-stopper. It violates additive purity in both lists, because 1+8 = 9 and 3+6 = 9; and there is no way to do the kind of swap we did with 7 and 8. L1 and L2, as just shown, are as far as we can go with two lists. The limit is 8.
We could take the matter further by using 9 to start a third list, L3. Ten would have to go into it, too, since 2+8 = 10 and 3+7 = 10. Eleven, however, could go into L1 without violating additive purity (although not into L2 because 5+6 = 11) …
So, brainteaser: The limit for one list is 2, the limit for two lists is 8. What's the limit for three lists?
• Solution.
You just have to continue chewing through the numbers after 8, as I began to do. If you preserve additive purity and stay alert to possible swaps like the one for 7 and 8 that I did back there, you will hit a three-list limit at 23. The three lists look like this:
L1 = {1, 2, 4, 8, 11, 22}
L2 = {3, 5, 6, 7, 19, 21, 23}
L3 = {9, 10, 12, 13, 14, 15, 16, 17, 18, 20}
The Online Encyclopedia of Integer Sequences has a relevant entry. It gives the limit for four lists as "at least 66":
L1 = {1, 2, 4, 8, 11, 16, 22, 25, 40, 43, 53, 66}
L2 = {3, 5, 6, 7, 19, 21, 23, 34, 35, 50, 51, 52, 63, 64, 65}
L3 = {9, 10, 12, 13, 14, 15, 17, 18, 20, 54, 55, 56, 57, 58, 59, 60, 61, 62}
L4 = {24, 26, 27, 28, 29, 30, 31, 32, 33, 36, 37, 38, 39, 41, 42, 44, 45, 46, 47, 48, 49}
The limit of 66 for four lists seems not to have been rigorously proved. However, the latest date on the OEIS references as I write is 2019, so there may have been developments the past five years not yet recorded.
For more than four lists OEIS likewise gives only lower bounds for the limit at the time of writing: for five lists 196, for six 582, for seven 1740, for eight 5201, for nine 15596.
The mathematical connections go deep, to Schur Numbers in Ramsey Theory. Enjoy!