How to Divide the Loot Fairly?

Consider this problem: two robbers who teamed up for more than three years decided to split up, due to various reasons. None of them was like O'Henry's Shark Dodson. So they took a fair road and elected to share their accumulated loot. The first divided the booty into two piles he thought equal. The second did not quite agree with his friend. In his opinion, one pile was a little bigger than the other. He thought himself very clever to pick the bigger pile. The first had no problem with the remaining one. So each was under impression he got at least one half of the booty.

O'Henry wrote about two friends but we may not stop here. What if there were 3 of them? Or even an arbitrary number n? Is it possible for them to find a way to share their loot in such a way that each will leave with the impression of getting at least 1/n-th part?

The following solution was sent to me by Richard Beigel.

One robber divides the loot into n piles that he considers equal size. For each pile he asks, "any takers." Each pirate must indicate if he would be satisfied with that pile, i.e., whether he considers that pile to be at least 1/n-th of the total.

For each set S of piles, let takers(S) be the set of pirates that is satisfied with at least one pile in S. Let P be the smallest nonempty set of piles satisfying |takers(S)| ≤ |S|. Such a P exists, because the set consisting of all n piles satisfies the inequality. If R is any proper subset of P then |takers(R)| > |R|.

Claim:

|takers(P)| ≥ |P|.

Proof:

If |P| = 1, this is true because the first robber is in takers(P). If |P| > 1 then let x be any element of P. Then |takers(P)| ≥ |takers(P-x)| > |P-x| = |P| - 1.

Therefore |takers(P)| = |P|. Thus if R is any subset of P then |takers(R)| ≥ |R|. By Hall's marriage theorem, there is a 1-1 mapping t from P to takers(P) such that for each x, t(x) in takers({x}). Piles in P are given to robbers according to t. The piles not in P are merged and the loot they contain is divided recursively among the robbers not in range(t).

The second solution has been kindly provided by Yuri Kifer of the Hebrew University.

As before, the first robber divides the loot into n piles which he considers to be equal. A robber likes a pile if he thinks that it is at least 1/n-th of the whole booty. If, for any k, 0 < k < n, any group of k robbers likes (together) at least k piles then by the Marriage Theorem we can satisfy everybody. Suppose not.

Denote by R the set of all robbers, by B the whole booty of piles, and, for a set A of robbers, by covet(A), the set of all piles which robbers from A like (together). By our assumption, there are sets A of robbers with the property |covet(A)| < |A|. Let Q be a maximal group of robbers that saisfies this inequality (maximal in the sense that it cannot be enlarged without violating the inequality.)

Clearly, |Q|< |R| since the first robber (who divided the booty) cannot be in Q (otherwise, covet(Q) = B). Now consider robbers from R - Q and the piles from B - covet(Q). It is clear that any group of k robbers from R - Q likes (together) at least k piles from B - covet(Q); for, otherwise, we can join this group with Q and the larger group will like less piles than its number i.e. Q will not be maximal. Thus we can "marry" robbers from R - Q with piles from B - covet(Q) and they will be satisfied.

Since all robbers from Q think that each pile from B - covet(Q) is less than 1/n-th of the whole loot, they will think that robbers from R - Q took |R - Q| piles each less than 1/n i.e. that they took less than |R - Q|/n of the whole booty and left more than |Q|/n to the robbers from Q. Now, by the induction step, (you know it for n = 1, right?) since |Q| < n the robbers from Q can be satisfied too.

So we have two proofs: one concentrating on the desired piles, the other on the robbers' desires. A comparison of the two proofs raises an interesting question. Is there any connection between the minimal set P of piles that satisfies |takers(P)| ≤ |P| and the maximal set Q of robbers that satisfies |covet(Q)| < |Q|?

There is a third, quite elementary solution for which thanks are due to Michael Kifer from SUNY,

Let N-1 robbers divide the whole pile the way they agree is equitable. Then the Nth robber steps in and asks each of the N-1 robbers to divide his share in N equal pieces (ie, each robber must think that he divided his share in N equal pieces).

Finally, the Nth robber goes around and collects the largest (in his view) N-th piece from each robber.

Clearly, each must think that he's got at least 1/N of the whole pile.

Since we know how to divide for N = 2, the problem is solved by induction.

Latin Squares

40614901