Upgrading A Coin
You have a fair coin. On each side of it is the number 1. You want each side to have a number that is at least 4. To do this, you use an intricate way. You will toss the coin. The number that comes up is the number of upgrade points you gain. You can spend one upgrade point to increase the number on a side by 1. You may distribute the upgrade points in any way you wish.
As an example round:
- You toss the coin. The number 1 comes up. You upgrade a side to 2; now you have a side of 1 and a side of 2.
- You toss the coin again. The number 2 comes up. You decide to upgrade each side once, so you have a side of 2 and a side of 3.
- You toss the coin again. The number 3 comes up. You decide to upgrade the side of 3 three times, so you have a side of 2 and a side of 6.
- You toss the coin again. The number 6 comes up. You upgrade both sides to have the number 7.
Since now each side is at least 4, you win; it took four tosses. You could have won in three tosses, if you upgraded correctly in the third toss to have both sides 4.
Suppose you play optimally (that is, you upgrade the sides in such a way to minimize the expected number of tosses required). What is the expected number of tosses required to complete the task?