The Devil's Brother

Question

The 1933 movie "The Devil's Brother" (also known under the title "Fra Diavolo") takes place in the Northern Italy of the early 18th century. Stan Laurel and Oliver Hardy play the fierce robbers Stanlio and Ollio. They manage to steal 100 gold coins from the rich Lord Rocburg, and then discuss at length how to share the loot. Finally they decide to play the following game.

• In every step, Stanlio picks a handful of gold coins from the loot.
  Then Ollio decides, whether this handful should go to himself or to Stanlio.
• Once all coins have been assigned, the game ends.
• Once one of them has received 9 handfuls, the game also ends. In this case the other player (who has received at most 8 handfuls up to that moment) receives all the remaining gold coins.

Question: What is the highest number of gold coins that Stanlio can guarantee for himself?
(As usual, we assume that both players use optimal strategies.)

Answer 1

Ok, I'll have a stab. The highest number Stanlio can guarantee is:

46 coins

Optimal strategy:

An optimal strategy for Ollio is to claim a handful that has 6 or more coins, and to pass on handfuls of 5 or fewer coins.

So ...

Stanlio knows this, and so knows that producing a handful with less than 5 coins will result in a bigger pot for Ollio left after 9 rounds. Producing a handful with more than 6 coins just reduces the pot left for himself after 9 rounds.

Which means ...

If Stanlio produces 5 coins at a time, Ollio will let him keep them. This means after 9 rounds Stanlio will have 45 coins and Ollio can claim the remaining 55 coins. If Stanlio produces 6 coins at a time then Ollio will claim them. Meaning that after 9 rounds Ollio will have 54 coins and Stanlio can keep the remaining 46.

Answer 2

I hope this isnt optimal but it is the best Ive found. Offer 6 coins every round until the 9 handfuls condition is met. Mr O will earn 54 if he accepts all hands (as i think he should) and Mr S will earn 46.

Answer 3

The highest number of coins that Stanlio can guarantee for himself is:

46

Proof:

Define $\rm{best}(i,j,k)$ to be the highest number of coins that Stanlio can guarantee for himself with $i$ coins remaining to be given out and $j$ further chances of receiving remaining for Stanlio, and $k$ chances remaining for Ollio. What we want to find is $\rm{best}(100,9,9)$
Finding a recurrence relation is straightforward. At this step, suppose that Stanlio offers $l$ coins. Ollio will choose to assign this set to Stanlio or himself based on which gives less payout to Stanlio. Of all possible values of $l$, Stanlio chooses whichever gives him the best payout. Thus we have:
$$ \rm{best}(i,j,k) = max_l\;min[\rm{best}(i-l,j-1,k)+l,\rm{best}(i-l,j,k-1)]$$ The base cases for the recurrence are $\rm{best}(0,j,k) = \rm{best}(i,0,k) = 0$, $\rm{best}(i,j,0) = i$, $\rm{best}(i,0,0) = -\inf$ for $i$,$j$,$k>0$

Pseudocode

initialise best[][][] with 0
for i=1 to 100
  best [i][0][0]=-inf
  for j=1 to 9
    best [i][j][0]=i
    best [i][0][j]=0
    for k=1 to 9
      for l=1 to i 
        best [i][j][k]=max(best [i][j][k], min ( best [i-l][j-1][k]+l, best [i-l][j][k-1]))

This gives $\rm{best}(100,9,9)=46$

Answer 4

tl;dr Stanlio offers as close as possible to an equal share for each handful, Ollio only accepts if he gets a better than equal portion, and they end up with 46 and 54 coins respectively; this is provably the best possible, and follows for a general formula for this kind of game, given below.

ntl;wr ("not too long, will read")

One correct answer has been stated (several times) before, but the full reasoning isn't there, and the general solution hasn't been stated.

Let's work up from the simplest case. If each has one handful remaining, if Stanlio picks half or more, Ollio will take the coins; otherwise Stanlio gets them. This suggests that the optimal strategy for Ollio is to take "more than his fair share" for the number of handfuls left to distribute.

Let's see if this works out inductively. If Stanlio has m handfuls remaining, and Ollio has n, then a fair share for Ollio is 1/(n+m) and Ollio can if induction works count on at least n/(n+m) of the remaining coins.

Let's then give Stanlio an extra handful, and suppose he offers a fraction f. Ollio could take the handful, in which case he'll get f + (1-f)*(n-1)/(n+m) of the remaining coins, or reject it in which case he'll get (1-f)*n/(n+m). Set the two equal to find f = (1-f)/(n+m) which we can rearrange as follows: 1/(1/f-1) = 1/(n+m), 1/f-1 = n+m, 1/f = n+m+1, f = 1/(n+m+1). So Ollio will break even if he takes his fair share of 1/(n+m+1).

Now let's give Ollio an extra handful. We get f + (1-f)*n/(n+m) or f*(n+1)/(n+m), which simplifies exactly the same way to f = 1/(n+m+1). So induction works: Ollio's strategy should be, assuming Stanlio plays perfectly, to take the coins any time he gets at least a fair share. (To really prove this inductively, we also need to handle the m=1 case separately, but that's easy because then Ollio if he refuses just gets all the rest of the coins and he should do that if Stanlio picks up too few.)

There are two wrinkles: coins are not perfectly divisible, and Stanlio might make a mistake.

The first wrinkle actually doesn't change Ollio's strategy at all. The math is exactly the same; it just means that Stanlio can't offer exactly a fair share.

But that Stanlio might make a mistake does impact Ollio's strategy on fair shares. Since it is all the same to Ollio whether he takes or rejects a fair division, but Stanlio has a chance to make a mistake on every game he plays, Ollio should try to draw the game out for as long as possible by distributing fair divisions between himself and Stanlio until they each have one handful remaining. This gives Stanlio the most opportunities to make a mistake.

Stanlio, knowing this, must not make a mistake. Stanlio has one extra dimension of freedom when he cannot offer a fair share: does he offer too much (by a fraction of one coin) and have Ollio take it, or too little (again by a fraction) and take it himself? Does it even matter?

First, Stanlio can simplify the game for himself. If there are h handfuls left and c coins, then a fair share is c/h. Let q be floor(c/h), i.e. c/h rounded down. Let r be the remainder of c/h. Then Stanlio is effectively choosing to offer either 0 or 1 coin (plus q), where there are r 1's to offer and h-r 0's.

Now the analysis is really easy. Every time Stanlio offers 0, Stanlio gets it. If it's a 1, Ollio gets it. If we sort the list of 0's and 1's on offer, Stanlio takes fro the bottom of the list, Ollio from the top. This continues until one or the other runs out of turns. So, if r <= h/2 then Ollio gets all r remaining coins. If r > h/2 then Ollio gets h/2 and Stanlio gets r - h/2.

So now we have an exact formula and algorithm for what will happen:

Let c be the initial number of coins and j be the number of handfuls each (total number of handfuls = h = 2j). Let q = floor(c/h) and r = c - h*q be the remainder. Stanlio will consider that he has r 1's to offer and h-r 0's to offer and can pick at random (actually offering q+0 or q+1 each turn). Ollio will pick only the q+1 offers unless all the 1's have been exhausted. This will leave Ollio with j*q + min(j,r) coins and Stanlio with the remainder, j*q + max(0,r-j).

Let's see how this works out with c=100, j=9. We have q=5 and r=10. We predict Ollio will end up with 45+9=54 coins and Stanlio with 45+1=46.

And if you play it out, with Stanlio offering either 5 or 6 coins at random until either Ollio's turns are exhausted or Stanlio has offered 5 eight times (after which he always offers 6), then this is precisely what will happen.

This gives two equally valid simple answers:

1. Stanlio offers 6 coins 9 times in a row, Ollio accepts every time, and has 54 coins. The remaining 46 are Stanlio's.

2. Stanlio offers 5 coins 8 times in a row, Ollio rejects every time, and Stanlio has 40 coins. Now there is a fair division of 6 coins per handful (10 remaining handfuls of 60), and Stanlio offers 6 each time until Ollio takes 9 and Stanlio gets one: 54 for Ollio and 46 for Stanlio.

Incidentally, if Stanlio had been a little more canny, he might have suggested (or insisted upon) 10 handfuls each (all offers could then be fair). It also suggests that Ollio was quite the mathematician, as 9 handfuls each gives him one of the biggest advantages: only 11 is better until you hit 19.