Two brothers, Sean and Patrick, are splitting a bag of candy. The candies come in different sizes, each represented by a positive integer value. Sean, as the older brother, will split the candy into two nonempty piles, and give one to Patrick, keeping the other for himself. Patrick will then examine the two piles and decide if he thinks the split is fair. If he decides the split isn't fair, he will start crying.
Unfortunately, Patrick is very young and bad at adding. He can almost add numbers in binary, but he always forgets to carry the 1. So if he wanted to add 13 (=1101) and 6 (=0110), he will get 1011, which is 11. Some other examples are 3+5=6, 4+10=14, 7+4=3.
Sean is good at adding, and wants to take as much candy as possible while not causing his brother to cry. Given a list of numbers the represent the candy values, is it possible to easily determine if Sean can split the candies in such a way that will not make his brother cry? What is the maximum value of candy that Sean's pile can be?
As an example, if the candies are value 3,4,7, we know that Sean can split them (7, 4) vs (3) and keep 11 total for himself, Patrick will perceive this as fair because he thinks 7+4=3. As another example, if the candies are valued 2,3,4, then there is no splitting that Sean can do that will keep Patrick happy.
The puzzle is sort of neat, and gets into some math that I really like that has a lot of importance in combinatorial game theory. Basically I'm just posting the puzzle so that I can make a game theory post while making it look like a puzzle post.
2 comments:
Maybe I'm missing the puzzle (and certainly the game theory in it):
Essentially, Patrick thinks adding numbers is the same as taking the binary XOR.
I doubt there is a maximum for Sean's pile, as the set {2^n-1, 2^n-2,1} is always divisible in a fair manner by giving Patrick the 1.
If you write down all numbers in binary, it is obvious that there is no fair division if there is a column (i.e. power of 2) with an odd number of 1's.
If all columns have an even number of 1's, any division will be fair and keep Patrick happy!
For example, in your {3,4,7} example:
011 = 3
100 = 4
111 = 7
Here, 3=4+7, but also 4=3+7 and 3+4=7.
In other words, if all values together XOR to 0, Patrick can give Sean the lowest value and Sean will be happy.
Somehow I feel like I'm missing the essential point of the puzzle...
No, you've got the essentials of it. The game theory isn't obvious in finding the solution, I'll make a post about that next time. The key realization is that Patrick is just XORing, so if Sean can make Patrick happy, he can do it with any candy split at all.
Post a Comment