Various numbers of different-colored (but otherwise identical) marbles are placed in a bag. Marbles are randomly removed from the bag one at a time. You are given the opportunity to guess the color of each marble immediately before it is removed, and with each guess you place a wager. If the color of the marble matches your guess you win the amount of your wager, otherwise you lose that amount.
Each wager can be anywhere from 0 to the total amount of money you have at the time of your wager, inclusive. Your goal is to carefully choose your wagers in order to guarantee yourself the highest possible winnings in the end. Given the total number of marbles of each color initially in the bag and $1.00, determine the greatest amount of money you can guarantee yourself to end up with.
For example, if the bag starts with 1 blue, 1 red, and 1 yellow marble, your best strategy is to wager zero on the first two marbles and then wager everything on the third marble, guaranteeing yourself $2.00 at the end. If you wager anything on either of the first two marbles, there is a chance that you will guess wrong and lose money. Even after doubling your money on the last marble you could end up with less than $2.00. So in this case, the answer is 2.
You can always end up with $2.00 by waiting until there is only one marble left. But often you can do better than that. If the bag begins with 1 blue and 2 red marbles, your best strategy is to bet 1/3 of your money on red. If you are correct (the first marble is red), you will end up with 4/3, bet nothing on the second marble, and then double your money betting on the last marble to 8/3. If you are incorrect (and the first marble is blue) you will have 2/3 left, but you will be able to double your money twice (because you know the last two marbles are both red), thus ending up with 8/3. Notice that you don't care if your first guess is right or wrong -- either outcome leads to ending up with 8/3.
|