Communications of the ACM
Last byte
Dust Wars
Credit: Andrij Borys Associates
When their parents die in a tragic accident, daughters Joan and Marie read their parents' Last Will and Testament. The Will is very short, because there is only one asset: two kilograms of gold dust.
The Will states that Joan, as the elder sister, should divide the dust into two piles: we will call those piles A and B. Then she is to cut pile A into two smaller piles that we will call A1 and A2. Marie can decide to choose one of A1 or A2 or not. If Marie chooses, then Joan takes the other smaller pile and all of pile B. If Marie does not choose between A1 and A2, then Joan can choose one of them (presumably the larger one) and give Marie the other one and then Joan must cut pile B into B1 and B2 and Marie can choose which one she wants.
Joan and Marie, though clever mathematicians, have never gotten along. Each wants as much gold dust as possible while obeying the rules of the Will.
Warm-Up: Suppose Joan divides the two kilograms equally (as depicted in the figure), so pile A weighs one kilogram as does B. How much can Joan be sure to receive as part of her inheritance no matter how clever Marie is?
Solution to Warm-Up: If piles A and B each weighs 1 kilogram, then Joan can guarantee to get 1 1/4 kilograms of gold dust. Here is how: she divides the A pile into subpile A1 consisting of 3/4 kilogram and subpile A2 consisting of 1/4 kilogram. If Marie chooses A1, then Joan gets A2 and all of B, thus 1 1/4 kilograms. If Marie declines to choose either A1 or A2, then Joan gives Marie A2 and divides pile B into B1 consisting of 1/2 kilogram and B2 also consisting of 1/2 kilogram. No matter which one Marie chooses, Marie will get 1/4 + 1/2, leaving Joan with 1 1/4.
Question: Prove Joan cannot do any better if the two piles are equal.
Solution: To see intuitively that Joan cannot do any better, suppose she divides up pile A into more unequal portions, say 7/8 in A1 and 1/8 in A2. In that case, Marie takes A1 and Joan receives only 1 1/8 in total. Suppose Joan divides pile A into less unequal portions, say 5/8 in A1 and 3/8 in A2. In that case, Marie declines to choose among A1 and A2. Joan then takes A1 but now Joan must divide up B into equal portions (otherwise Marie will take the larger portion). So, Joan would accumulate only 5/8 + 1/2 = 9/8 = 11/8.
Joan realizes she is not obligated to divide up the two kilograms into two equal piles. Clearly, she does not want them to be too unequal. For example, if A were tiny, then Marie would simply not choose between A1 and A2 and get 1/2 of B yielding her nearly 1 kilogram. That would leave Joan with approximately the same amount of gold dust.
Question: Can she do better by dividing them in some other way?
Solution: However, suppose Joan divides the two so that A is 2/3 kilograms and B is 4/3 (or 1 1/3) kilograms. Then Joan divides A into A1 consisting of all 2/3 kilograms and A2 consisting of one piece of dust. If Marie takes A1, then Joan gets all of B or 1 1/3 kilograms. If Marie declines to choose, then Joan gets all 2/3 from A and then Joan divides B equally into 2/3 kilogram for B1 and 2/3 kilogram for B2. This second case yields 2/3 + 2/3 for Joan or 1 1/3 kilograms. Of course, 1 1/3 > 1 1/4, so Joan is better off with this division.
Question: Prove this is optimal for Joan.
Solution: To see this is optimal for Joan, suppose A weighed less than 2/3 of a kilogram. In that case, Marie could decline to choose among A1 and A2 and then get half of pile B. Pile B would weigh more than 4/3 kilograms, so Marie would end up with more than 2/3 kilograms, leaving Joan with less than 1 1/3.
Now suppose A weighs w = 2/3 + e kilograms. In that case, if either A1 or A2 weighed more than 2/3 of a kilogram, Marie would take it, leaving Joan with less than 1 1/3. If both A1 and A2 weigh less than 2/3 of a kilogram, then Marie would decline to choose and would receive some portion we will call w2. Then Marie would receive w2 plus at least half of B. Because B weighs 2 - w, this comes out to w2 + 1/2 (2 - w). Joan then receives (w - w2) + 1/2 (2 - w). Now, we know that w = 2/3 + e, where e is a positive weight and we know that w - w2 <= 2/3 (because otherwise Marie would have chosen the subpile weighing more than 2/3). So, w - w2 = 2/3 + e - w2 <= 2/3. Rewriting, we get e <= w2. Now let's look at Joan's inheritance (w - w2) + 1/2 (2 - w) = (2/3 + e - w2) + 1 - (1/3 + e/2) = 1 1/3 + e/2 - w2. Because w2 >= e, w2 > e/2 and so the expression e/2 - w2 is negative. Thus, Joan receives less than 1 1/3. Let's check this with the case where e = 1/3 (so the two piles are equal). Joan would receive 1 1/3 + 1/6 - 1/4 = 1 1/2 - 1/4 = 1 1/4.
Upstart: How does this generalize to k kilograms and k piles where Marie gets to choose (a) 1 time, (b) k-1 times, or (c) 1 < m < k-1 times?
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
©2019 ACM 0001-0782/19/10
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2019 ACM, Inc.
No entries found