Interestly, the first player can always have the control to collect all the numer at the even index or odd index. If the sum of nums at even index is greater then sum of odd index, then just select sum of even index.
Is that true the first player always has the control?
[4, 3, 1, 7, 2, 1]
Assume I am the first player and I found 4 + 1 + 2 < 3 + 7 + 1
The question now becomes can I get 3, 7, 1
YES, I can choose the last 1 first, the next player could choose 4 or 2 from [4, 3, 1, 7, 2]
If he chooses 4 then I choose 3
If he chooses 2 then i choose 7
So the first player always wins.
No comments:
Post a Comment