1.A game is played as follows. Coins with value x1 , . . . , xn are laid on a table in a row. Two players alternate turns taking a coin from either end of what’s left of the row of coins until the coins are gone. The object is to accumulate as much value as possible. For example, there may be n = 6 coins worth (x1, x2, x3, x4, x5, x6) = (2, 5, 3, 1, 4, 3). Let us agree that a game has value V to the player who goes first (first player) if: (i) no matter how second player plays, first player can obtain coins worth V ; and (ii) no matter how first player plays, second player can make sure first player gets coins worth no more than V. LetV(i,j)(1≤i≤j≤n)denote thisvalue if there are j−i+1coins in the game and they are worth (xi,...,xj). For example, in our sample game: V(5,5) = 4 (there’s only one coin, worth 4, and the player who goes first gets it); V (2, 3) = 5 (there are two coins, worth 5 and 3, and the player who goes first will pick the 5); and V (4, 6) = 4 (there are three coins, worth 1, 4, and 3, and the player who goes first picks the 3 and then the 1 after second player takes the 4).

(a) For j ≥ i + 1, find a recursive formula for V (i, j) in terms of V (i + 1, j) and V (i, j − 1). Argue your answer carefully. Be sure to indicate what the boundary conditions are.

(b) Suppose I play randomly: each time it’s my turn I choose a coin independently from either end each with probability 1. (If there’s only one coin left when it’s my turn,

obviously I take it with probability 1.) Furthermore suppose you know I’m going to do this. As above, but assuming my random strategy, let W(i,j) denote the value to you assuming you play optimally to maximize expected value if you go first and the coins are (xi,...,xj). For j ≥ i + 2, find a recursive formula for W(i,j) in terms of W(i,j − 2), W (i + 1, j − 1), and W (i + 2, j). Argue your answer carefully. Be sure to indicate what the boundary conditions are.

Subject | Mathematics |

Due By (Pacific Time) | 05/19/2015 12:00 am |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |