Two Notorious Robbers Made Big Score Managed Escape Safe House Loot Collection N Diamonds Q27720139

Two notorious robbers have just made a big score and managed toescape to their safe-house. Their loot is a collection of ndiamonds of various value and an associate has helped them evaluatethe price of each diamond. Being in an immensely cerebral mood,instead of splitting the loot in half, they decide to play a gamethat will determine the cut. They allocate the n diamondsarbitrarily into a row. Suppose the diamond row is denoted as asequence d1,d2,… ,dn, with respective values v1,v2, … ,vn,where diamond di has value vi. Remember that these values are knownto both of them. The game goes as follows: The two robbers taketurns picking a diamond from the sequence, but can only pick thefirst or the last diamond of the (remaining) sequence. The goalfrom each robber’s perspective is to collect the maximum possiblevalue of diamonds by the end of the game. Finally, suppose that nis even.

1. Imagine that the strategy of the robber that starts first isto always pick the available diamond of greater value. Rememberthey are only allowed to pick the first or last diamond of theremaining sequence at each turn. This is a natural greedy strategy.Is it optimal? Show a small sequence of diamonds (decide the valuesyourselves) such that this strategy will not achieve the maximumpossible total value for the robber that starts first. Show whythis greedy strategy fails in your sequence and also show whatwould be the optimal strategy for the robber in that particularsequence.

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *