The following is a modified Jane Street interview question.

Question: Given $ 100 Fair currencies For each head obtained, we get $ $ 1 $. If we can flip any amount of coins once, what is the expected value of the game?

By "flipping any amount of coins once," I mean we can flip those coins that do not queue. For example, if we have $ 4 $ coins and we get $ HTHT $, then we can flip the second and fourth currency again to increase our profits.

I know how to solve the problem for $ 4 $ fair coins:

Without turning back, the expected value of the game is $ $ 2. $

With re-flipping, we can calculate the additional gain as follows:

$$ frac {1} {16} times 0 + frac {4} {16} times 0.5 + frac {6} {16} times 1 + frac {4} {16} times 1.5 + frac {1} {16} times 2 = 1. $$

Then, the expected value with re-flip for $ 4 $ fair coins is $ $ 3 $.

I can do the above calculations in my head and get the answer without using pencil and papers.

However, if they give me $ 100 coins, so I can't calculate the additional gain in my head since it's quite tedious.

I wonder if there is a shorter way to solve the $ 100 problem of coins without using pen and paper.