Optimal positions to place 3 coins in a line such that when you keep rolling the die and increment your position, you reach a coin.

Question

You have 3 coins and a die. There is a line with positions from 1 to 1000. you need to place the coins in any of these positions in the line. from position 0, you keep rolling the die and you jump that many steps in the line. if you reach any position with a coin in it, you win. If you cross 1000 without reaching any positions with a coin, you lose. What are the optimal positions to place the coins in the line to maximize your chance of winning the game?

Answer 1

Fix some arrangement of the coins. Let $p_k$ be the winning probability given that you start $k$ positions before the first coin, for $k=1,\ldots,6$. (It doesn’t matter for the argument that this starting position might be before the actual starting position at $0$.) Now if you start $7$ positions before the first coin, you can’t immediately hit a coin, so the winning probability is the average of the $p_k$. That average can’t be higher than the maximum of the $p_k$, so you haven’t gained anything by stepping further back. Applying the same argument inductively shows that there must be an optimum in the first $6$ positions before the first coin. A similar argument shows that there must be an optimum that leaves at most a gap of $5$ free positions between any two coins, because whatever probability distribution we end up with behind a coin, it will form some weighted average of the winning probabilities on later positions, and that weighted average can likewise not be greater than the maximum of those probabilities.

That brings the problem well within the reach of computers (which it sort of already was, though with a lot more computing time). Here’s Java code that calculates the winning probability for all configurations of the coins without gaps greater than $5$. The result confirms the guess that Zoe Allen and I posted in comments: The optimal positions for the coins are $4$, $5$ and $6$. The optimal winning probability is $\frac{343}{432}\approx79\%$.

I wouldn’t be surprised if there were an elegant proof for this without computers, though.