Upgrading A Coin

Probability Level 4

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?

The answer is 3.75.

1 solution

Ivan Koswara
Jan 7, 2016

The answer is $\frac{15}{4} = 3.75$ . (In the following, coin $a/b$ means a coin with sides $a,b$ respectively.)

We first present a strategy that allows us to achieve this value. The idea here is simply to make sure the numbers on both sides are as equal as possible.

You toss a 1/1. Either way, you'll get 1; you upgrade to 1/2 and toss it.
Half of the time you'll get the 1; you upgrade to 2/2, which you then upgrade to 3/3, which you then upgrade to 4/5. That takes four tosses.
Half of the time you'll get the 2; you upgrade to 2/3 and toss it.
- Half of the time you'll get the 3; you upgrade to 4/4. That takes three tosses.
- Half of the time you'll get the 2; you upgrade to 3/4 and then you're done (either 5/5 or 5/6) in four tosses.

We can simply compute each branch. A quarter of the time (if you get 2 on the second toss and 3 on the third toss), you're done in three tosses, otherwise it takes four tosses. That's $\frac{1}{4} \cdot 3 + \frac{3}{4} \cdot 4 = \frac{15}{4}$ .

We now show that 3.75 is indeed the best you can do, regardless of the strategy.

1) Your first toss will always give you a 1/2; you don't even have a choice.

2a) If your next toss is a 1, you still need four more upgrade points to finish. Since you can't get a side of 4, this means that we cannot finish in three turns. Hence, we need at least 4 turns, which is achieved by the above strategy.

2b) If your next toss is a 2 instead, you need three more upgrade points. No matter how you distribute them, one of the sides will be less than 3 (the total of the sides is 5, and there are two sides, so one of them will not be greater than $\frac{5}{2} < 3$ ). If the third toss lands on this side, then we will need at least 4 tosses. Hence, the expected number of steps is at least 3.5, which is achieved by the above strategy.

Thus either way, three quarters of the time you'll need four tosses and one quarter of the time you'll need three tosses, so the expected value is at least $\frac{3}{4} \cdot 4 + \frac{1}{4} \cdot 3 = \frac{15}{4}$ . This is what we exhibited in the above strategy.

Moderator note:

It is not always true that having a balanced dice will lead to the minimum. How can we deal with the general case?

The crux of this problem is in showing that the strategy as described indeed minimizes the number of flips. Why is this true?

Calvin Lin Staff - 5 years, 5 months ago

That's described in the latter half of the solution. Although interestingly, it doesn't say anything about needing to keep everything balanced; it's just the absolute lower bound that naturally comes, and keeping everything balanced just happens to meet that bound. I haven't tried more to see if it still holds with other numbers (number of sides and the target number for each side).

Ivan Koswara - 5 years, 5 months ago

After looking into this further, I believe that your claim is wrong. There are benefits from overly weighting one side, in the hopes of finishing earlier half the time.

For example, let's consider the case of starting out with a 2/2 coin, and wanting to reach more than 5. Your prescribed steps are $2/2 \rightarrow 3/3 \rightarrow 4/5 \rightarrow$ done. This takes 3 steps everytime. However, let's consider this alternative sequence:
$2/2 \rightarrow 2/4$ . If we land on 4, we're done in 2 steps.
If we land on 2, we go to $4/4$ , and then we need 1 more step, so we're done in 3 steps.

As such, an unfair weighting can allow for a lower expected number of steps.

It is not clear to me if the goal is to reach $100/100$ , which strategy we should use. I suspect that at the start we want to unfairly weight it still.

Calvin Lin Staff - 5 years, 5 months ago

@Calvin Lin – That's the point; it just happens that balanced strategy works out for this particular scenario.

Ivan Koswara - 5 years, 5 months ago

@Ivan Koswara – In which case, the solution is incorrectly presented. You need to provide the proof that you have indeed calculated the minimum, over all possibilities. This is not immediately obivous, and that's the proof that I was asking for.

Let me update my comment.

Calvin Lin Staff - 5 years, 5 months ago

@Calvin Lin – That one I have already presented in the latter half of the solution ("The more interesting thing is that this is the best you can do.").

Ivan Koswara - 5 years, 5 months ago

@Ivan Koswara – Ah ic. I've edited the structure of your solution to reflect that more clearly.

Calvin Lin Staff - 5 years, 5 months ago

Upgrading A Coin

The answer is 3.75.

1 solution

Moderator note:

0 pending reports