Two notorious robbers have just made a big score and managed to escape to their
ID: 3736020 • Letter: T
Question
Two notorious robbers have just made a big score and managed to escape to their safe-house. Their loot is a collection of n diamonds of various value and an associate has helped them evaluate the price of each diamond. Being in an immensely cerebral mood, instead of splitting the loot in half, they decide to play a game that will determine the cut. They allocate the n diamonds arbitrarily into a row. Suppose the diamond row is denoted as a sequence d1,d2... ,dn, with respective values v1,v2, ... ,vn, where diamond di has value vi. Remember that these values are known to both of them. The game goes as follows: The two robbers take turns picking a diamond from the sequence, but can only pick the first or the last diamond of the (remaining) sequence. The goal from each robber’s perspective is to collect the maximum possible value of diamonds by the end of the game. Finally, suppose that n is even.
1. Imagine that the strategy of the robber that starts first is to always pick the available diamond of greater value. Remember they are only allowed to pick the first or last diamond of the remaining sequence at each turn. This is a natural greedy strategy. Is it optimal? Show a small sequence of diamonds (decide the values yourselves) such that this strategy will not achieve the maximum possible total value for the robber that starts first. Show why this greedy strategy fails in your sequence and also show what would be the optimal strategy for the robber in that particular sequence.
Explanation / Answer
1. Natural Strategy is not optimal
consider this sequence
9, 10, 3, 6
If robber one choses 9 first and then he can only get either 3 or 6 (because 10 must be choosen by player 2).
He can gain 9 + 6 = 15. And the other robber will get (10 + 3 = 13). Although first robber gets more than second
robber but he can do more than this.
Consider these steps
1. robber one choses 6
2. robber two choses 9
3. robber one choses 10
4. robber two choses 3
In this case robber one can get (10 + 6 = 16)
2. Strategy to win this game and get maximum value.
First player can always make sure that he wins the maximum value.
The strategy is
1. Find the sum of values of odd positioned diamonds ( in this case 9 + 3 = 12)
2. Find the sum of values of even positioned diamonds ( in this case 10 + 6 = 16)
3. If sum of odd positioned diamonds is greater than sum of even positioned diamonds then player first should keep picking odd postioned diamonds. Player one can pick a odd positioned diamond and can block all other odd positioned diamonds.
4. If sum of even positioned diamonds is greater than sum of odd positioned diamonds then player first should keep picking even postioned diamonds. Player one can pick a even positioned diamond and can block all other even positioned diamonds.
Example in above sequence 9, 10, 3, 6
Sum of even positioned diamonds is greater.
So goal is to get diamond value 10 & 6
If you pick 6 then 10 is blocked because other player can only pick from (9,3). This way you can get maximum value