An Additive Game : Part II
We left Part I having found one solution that fits the rules, but we didn’t come up with a general way to find more solutions. The method of swapping cards was also arbitrary depending on unspecified heuristics.
Let’s take some time to review the problem again:
- We have been given 12 cards, numbered 1 through to 13 excluding 12.
- We need to divide the cards into 4 buckets making sure to use up all the cards.
- A card may be shared by a maximum of two buckets, and no two buckets can share more than one card.
- When we add up the numerical values in each bucket, they must come up to exactly 23.
Starting with the last requirement we can build up a general method of finding (or at least searching for) solutions.
Read Part I here: https://newtonmigosi.medium.com/an-additive-game-part-i-b8a6a2935ae3
So, how many ways can you add up four numbers less than 13 to come up with 23? Listing all of them will give us all the valid buckets our system can have. Though this list is finite we can guess it will be rather long so we need to find a shortcut first.
If we look at the largest three cards with values 10, 11, and 13 we can immediately figure out that they can never share a bucket. Why? Well suppose, 10 and 13 were to share a bucket. Then this would mean that we need to find two cards to put in that bucket that would add up to the remainder of 23-(10+13)=0, but no such pair exists so we can rule out any attempt to put 10 and 13 together. A similar argument follows for all the other combinations of 10, 11, and 13.
Figuring this out saves us a lot of work because now we have (partially) fixed the contents of three out of four of our buckets. This also means that we don’t have to list out all possible ways to add four numbers up to 23, we just have to look at those that have 10, 11 and 13. It’s a bit of work but we find:
I’ve named the three fixed buckets A, B and C, with the mysterious fourth one called X. We’ll get back to it later. From the table we see that there are only four different ways to add up to 23 which include 13: 13+7+2+1, 13+6+3+1, 13+5+4+1 and 13+5+3+2.
Using our table we can generate possible solutions by picking out from the options for A, B and C. But before we do that we can glean even more information about our system.
For starters, we can show that 13 can never be shared by two buckets — in the context of the square, this means that it can never be in a corner. Why? Well, I’m glad you asked.
Suppose 13 was in fact placed in a corner. Then this would mean two of the four options for bucket A have occurred simultaneously. However, three of them also include a 1 in addition to 13 which breaks our rule of buckets sharing at most one card. As for the option that doesn’t include a 1, we can see that it shares at least one more card with all the other three options. Therefore we can conclude that it’s not possible for 13 to be shared by two buckets.
A direct consequence of this is that we can rule out the possibility of 13 being found in X. Speaking of which, let’s try and construct a solution to see how the contents of X can be determined.
Let’s start by choosing the first option for A: 13+7+2+1=23. We see that making this choice immediately reduces our options for B and C. In particular, after choosing 7 to be our second card in A, we can rule out it out from being present in either B or C because otherwise they would have to share more than one card. In addition, choosing 7 to be in A also excludes 9 from being in B, for the same reason.
After making the choice for A, the table reduces to:
We are now only left with 4 options for B, and if we pick the first option: 11+8+3+1, the table shrinks even further. This time C has only two options left that do not go against our rules.
Let’s try to build a solution by choosing the first option for C: 10+6+5+2=23.
So far, we have A={13,7,2,1} ; B={11,8,3,1}; C={10,6,5,2}. We see that 1 is shared by A and B, while 2 is shared by A and C. This means that they must be in corners. But what about X?
Well, our choices for A, B and C have left out 4 and 9; so they must be in X. And we also know that they can’t be in corners otherwise they would have already been listed. Before we go any further let’s have a look at our partially completed puzzle:
Where do the rest of the cards go? Even though we fixed B and C, we cannot place their cards in a way that still respects our rules. If we look at X, we see that so far we have 4+9=13 as its sum. However, we cannot find two numbers from B and C (one coming from each), that add up to the remainder of ten. You might wonder what about 8 and 2? but remember 2 is already being shared by A and C so it can’t be in X.
We are forced to come to the conclusion that our choices for A,B and C cannot form a solution. This is rather disappointing given all the work we’ve done in our search. All the same it did shed some light as to how a search for solutions can be carried out, which was what we were looking for in the first place.
In summary, we came up with the following method for searching for all solutions:
- List all the ways you can use 13 with the rest of the cards to add up to 23, we found there’s only four.
- Choose one of them then list all the ways you can use 11 with the remaining cards. Repeat for 10 as well.
- Any shared cards go in the corners, and any left out cards go in the last bucket.
- To complete the solution pick two cards from the adjoining buckets that add up to the remainder of the last bucket. If no such pair exists then the choices you made do not form a solution.
With that we can call it a day! Look out for Part III coming soon, where we implement this in software.
Read Part III here: https://newtonmigosi.medium.com/an-additive-game-part-iii-the-implementation-d9f6868c7f60