Return to Answer

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 9
        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$

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$

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$
Bottom up dynamic programming using the recurrence gives $\rm{best}(100,9,9)=46$

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 9
        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$

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$
Solving the recurrence gives $\rm{best}(100,9,9)=46$

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$
Bottom up dynamic programming using the recurrence gives $\rm{best}(100,9,9)=46$