Coin Flipping Game with the Devil

Question

You die, and awake in Hell. Satan awaits you, and has prepared a curious game. He has arranged $n$ quarters in a line, going in the east/west direction. He placed the coins at the ends tails up, and all others heads up, like so: $$ \text{T H H H }\cdots \text{ H H H T} $$

Satan explains the rules.

• Once a day, a coin is removed from the east end, and placed on the west end.
  • If the coin was initially tails-up, then you get to choose whether the coin is placed heads up or down.
  • If it was initially heads-up, then Satan gets to make this choice.
• If the coins are all heads up at the end of a day, you get to leave Hell.

Satan will of course try his hardest to make sure you never leave.

For example, when $n=5$, we start with $\text{T H H } \color{red}{\text H} \color{green}{\text{ T}}$. The first day is your choice; if you choose heads, the arrangement becomes $\color{green}{\text{H }}\text{T H H } \color{red}{\text H} $. The next three days, however, will be Satan's choice. He may fight back on the second day by choosing tails, resulting in $\color{red}{\text{T } }\color{green}{\text{H }}\text{T H H } $.

Is there a strategy that eventually guarantees your salvation? Or can Satan conspire to keep you in Hell forever?

Addendum: To give credit where it is due, this puzzle from The Puzzle Toad, (under the name "Zeroise Me") which is a superb collection of similarly clever and enjoyable conundrums.

Answer 1

Satan should stick to fiddling. You will win, and here is a simple proof.

Consider the game $n$ turns at a time. After each cycle of $n$ turns, all the coins are in their original position (though not necessarily flipped the same way).

Replace $H$ with $0$ and $T$ with $1$.

In each cycle, you flip all $1$'s to $0$'s, until Satan flips a $0$ to a $1$. Once Satan makes a flip, you stop and leave the rest of this cycle's coins alone.

Satan must always make a flip during a cycle. If not, then you have just flipped all the coins to $0$, and you win.

Read the sequence of coins as a binary number. Each cycle's play starts at the ones place and progresses to the largest place. Satan makes the last flip in each cycle, and that flip flips a $0$ to a $1$. Therefore, after each cycle, the number gets larger.

But it can't get larger forever. After at most $2^n$ cycles, it reaches $111...1$. Put on your smuggest face and flip all the coins for a well-deserved win.

Answer 2

Charlie always wins.

Let's split the chain of coins up into two sections: the tails-chain and the heads-chain. The tails-chain is Charlie's long chain of tails. I will use a vertical bar to denote where the chains split. It starts out as the two Ts in TTH...H, written TT|H...H. The heads chain is everything bounded by the two H coins of Satan's.

A postulate: Tails in a chain will always connect, and Satan will never get them back. This is pretty easy to prove. Once the tails have joined Charlie's chain, Charlie just has to choose not to flip them to heads again.

A postulate: Satan must have at least one tails in his chain. If Satan at any point has all heads in his chain, then the chain must pass through the state H...H|T...T, which means he loses. Thus, there must be at least one tails in his chain.

Final postulate: Charlie can force the tails in Satan's chain one step further towards its 'tail' with each loop through. (Note that there is a special case for this, detailed below.)

This leads to the win condition. In order to win, Charlie needs to force Satan's chain to spit out tails. Those tails will connect with Charlie's chain, and Satan will lose them. Repeat this process indefinitely, and Charlie wins.

To do this, Charlie flips any tails resting between two heads to heads. That means the soonest Satan can put a new tails in is the next coin. This forces Satan's tails coin one coin further down the heads-chain, until it contacts the tails-chain and becomes part of it.

At that point, he loses another heads, as he has to have a tails in his chain. Satan will eventually only have one heads, and will lose.

An example chain: HHTH|TT -> HTHH|TT -> THHH|TT. At this point, Charlie's chain is actually three tails long: TTT|HHH. Satan can't help but move HTH|TTT -> THH|TTT, which means Charlie's chain becomes four tails long. At this point, Satan's loss is inevitable.

Another example chain: HHHTH|TT -> HTHHH|TT. At this point Satan might flip the fourth coin again resulting in HTHTH|TT, but if Charlie leaves this alone and flips the second tail back when he gets around to it, Satan will have no choice but to flip the third coin from the left, resulting in HTTHH|TT. Then, on the next go-around, Charlie increases the length of the chain by 1 again. Consequently, Satan will eventually lose all his open coins.

---

After there are enough coins, Satan may be able to introduce multiple tails. This is non-trivial, but results in a loss for Satan anyway. If Satan introduces multiple tails, do nothing. Then, start pushing coins from the front of the chain toward the back.

For instance, let's say you have TT|HTHHH. Then, Satan is a jerk and creates HTH|TT|HT. Now, instead of flipping your lingering tails coin, do nothing with it: TT|HTHTH. Now, keep flipping your tails to heads until Satan flips a coin. This leads to the following chain:

H|TT|HTHT -> HH|TT|HTH -> HHH|TT|HT -> HHHH|TT|H -> THHHH|TT -> TTT|HHHH

In other words, up until the point where Satan flips a coin, you keep flipping tails to heads. As an example with more coins:

TT|HTHHHTH -> H|TT|HTHHHT -> HH|TT|HTHHH -> THH|TT|HTHH -> TT|HTHHTHH
TT|HTHHTHH -> HH|TT|HTHHT -> HHH|TT|HTHH -> THHH|TT|HTH -> TT|HTHTHHH

It's pretty clear that eventually you'll end up in the configuration:

TT|HTTTHHH

You can keep pushing Satan's tokens further down the chain. Once you do, you're in control of them, and Satan needs to add another tails further up the chain otherwise you'll bump the last heads into your chain.

To illustrate, let's say Satan doesn't add a new tails. Then you have: TT|THHHHHH -> TTT|HHHHHH

However, if he adds another one, it will become TT|HTTTHTH, which you can easily force into TT|HTTTTHH on your next turn. From there, Satan has nowhere to go, and loses a coin.

Therefore, no matter what Satan does, Charlie always wins.

---

Here are a few extraneous notes.

Some raw experimentation shows that the number of 'cycles' it takes to flip $n$ coins over is $F_n$, the $n$th Fibonacci number. (Here, I'm defining a cycle as the number of moves until the tails-chain is at the front again.)

Because the tails-chain gets shifted backward one step for every coin assimilated, the total number of moves ends up being $n*F_n-(n-1)=n(F_n-1)+1$.

I'd gander that if there were even 20 coins, it would take $20*6765-19=135281$ days for you to actually escape. Several centuries would have passed before you ever left, for any reasonable number of coins. What a jerk, that Satan.

Answer 3

For $n = 2$, the solution is trivial - you flip both coins heads-up for the first two days, and leave.

---

For $n = 3$, you leave the first coin alone, leaving Satan with TTH. But no matter whether Satan flips this coin or leaves it alone, you can flip all the T's in a row afterwards, so you win.

---

For $n = 4$, you leave the first coin alone, leaving Satan with TTHH. Regardless of how Satan flips these two coins, in all four cases you're left with a string of 2, 3, or 4 consecutive T's, so you can flip all of them and win.

(In the case of flipping only the second one, you're left with THTT, but just leave those two alone and no matter what Satan flips, you can flip all of them the second time around.)

---

$n = 5$ is the first interesting case. Then, if Satan flips only the second H out of three after you leave the first coin alone, you're left with HTHTT. If you leave this alone, then Satan will also leave it alone, and you'll be stuck in a loop forever. So the only thing to do is to either flip the solitary T, or flip one or both of the two consecutive T's.

1. If you flip one of the two consecutive T's, you've left Satan with either HTHTH or THHTH depending on which one you flipped. Satan can just leave this alone, which means you're stuck in an infinite loop until you decide to flip one of the others.

   • If you flip the first one, Satan's left with HHHTH. If he leaves this alone, then you flip the T and win. So he has to flip this H, leaving you with THHHT, back where you started.

   • If you flip the second one, Satan's left with HHTHH. But he can just leave the first H alone and flip the second one, leaving you back where you started as well.

2. If you flip the solitary T, then Satan's left with HHTTH. If he leaves this H alone, then you flip the T and win. So he has to flip the T, leaving you with THHTT. Just leave these two alone, leaving Satan with TTTHH and the same quandary he had in the $n = 4$ case.

---

In general, you want to leave Satan with a situation where all the T's are in a single bunch and a single H follows them. Then, he's forced to increase the length of the T chain by 1 (and thereby effectively reduce the number of coins in the game inductively), and if you can keep doing that, then by induction you win.

For $n = 6$, Satan can flip one, the other, or both of the two coins not next to the existing T's, leaving you with one of HHTHTT, HTHHTT, or HTTHTT once you've gone a full revolution. In any case where Satan flips the coin right before the leftmost H, you leave them alone (and your first two T's) the first time around, and flip them all back to heads the second round, leaving Satan with HHHTTH and you winning.

So Satan has to flip the first coin only where he's left with HHTTHH and has the choice of flipping the T, which is the only nontrivial variation from $n = 5$.

Let's suppose he does this. Then you're left with HTHHTT, which, from above, is one of the winning strategies. So you win as well.

---

We still haven't deduced a general strategy yet, so let's continue with $n = 7$.

Satan can leave you with HTHTHTT this time, which circumvents the flipping-the-one-next-to-last rule described above since the first flipped T prevents Satan from being forced to flip the H immediately before the string of two T's. But in this case, if you flip the first solitary T the second time around, then Satan has to flip the next H, because if he leaves it alone, you can just flip the next T as well, leaving Satan with HHHHTTH and starting the $n = 6$ case. So he has to flip that H, leaving you with HTTHHTT the second time around. Then you simply flip the left sequence of T's and force the $n = 6$ case again.

But there is one wrinkle here. What if Satan flips to HHTHHTT, and you flip that T only for Satan to flip the H immediately afterwards (resulting in HTHHHTT) and then Satan flips the second H only, resulting in HTHTTHT on your turn? If you flip the T now, and then the next solitary T right afterward, Satan will just flip the next T again, returning you to HHTHHTT.

So, you just leave that second T alone for two days, and the HTHTHTT case plays out exactly as described in the first place.

---

At this point, we finally notice a pattern. You will always flip the series of T's immediately after your longest chain (which starts at length 2 and keeps growing until it's the entire string of coins), which forces Satan to flip the H immediately to the left of them in order to ward off defeat. And if Satan flips any of the H's beforehand, leave the rest of the T's alone and let it go around one more revolution.

This will always result in the set of stray T's moving left towards the end of your longest chain and merging together with other stray sets, or a set of new T's being created that will have to move left anyway, possibly creating an even longer chain in the process.

The longest Satan can drag the game out for when your longest chain is $m$ T's long (without making a longer chain in the process) is until the chain of $m$ T's is followed by a series of chains of $m$ T's each separated by a single H. At that point, any head Satan flips will automatically create a longer chain, so you can flip all the chains of $m$ T's, leaving Satan with the coin right before the last chain of $m$ T's which he must then extend to $m+1$.

And this way, you can always defeat Satan and escape from Hell.

---

Below is a program-like algorithm that you can follow, assuming that instead of moving coins to the left, you keep track of a cursor that moves to the left one space every day.

• Every day, the cursor moves left one space. If the cursor reaches the leftmost coin, it jumps back to the right.
• If you are on your rightmost set of consecutive T's, pass.
• If Satan has not flipped a coin yet since the cursor last jumped to the right and you are currently on a T, flip it. Otherwise, pass.
• If Satan flips the leftmost coin, move that coin to the rightmost position, keeping the cursor on it.

An example of the longest match for $n = 11$, to show how this algorithm might work:

HHHHHHHHHTT   You leave the two T's alone, Satan flips coin 8.
HHHHHHHTHTT   You flip the first T, forcing Satan to flip coin 7.
HHHHHHTHHTT   You flip the first T, forcing Satan to flip coin 6.
...
HTHHHHHHHTT   Satan flips coin 8 again, and you leave everything alone.
HTHHHHHTHTT   You flip coin 8, and keep moving left until Satan reaches coin 4.
HTHTHHHHHTT   Satan flips coin 8 again. This flipping coin 8 and moving to the left continues until all the even-numbered slots are occupied.
HTHTHTHTHTT   You start flipping all the T's from coin 8 onward. If Satan flips any coins before that, stop and let the cursor wrap around again.
HTTHHHHTHTT   This might happen. Then, Satan flips coin 8 and starts the above process all over.
...
HTTHTTHHHTT   This might happen again.
HTTHTTHTHTT   Satan flips coin 8 one last time, but he cannot dodge anymore. You leave the coins alone for one more iteration.
THHHHHHHHTT   You flip all groups of coins, leaving Satan with no choice but to flip coin 1.

HHHHHHHHTTT   The frame of reference of the coins move forward one space.
HHHHHHTHTTT   Satan starts with coin 7 this time.
...
HTHTHTHHTTT   Chains of length 1.
HTHTHTTHTTT   Satan flips coin 7. You leave all the other coins alone.
HTTHHHHHTTT   Satan is forced to do this again.
HTTHHHTHTTT   Same process as before.
...
HTTHTTHHTTT   Chains of length 2. You flip the first chain, Satan flips coin 4.
HTTTHHHHTTT   First chain of length 3. Satan flips coin 7 again, and the process continues.
HTTTHHTHTTT
HTTTHTHHTTT   
HTTTHTTHTTT   In 3 moves, Satan exhausts the chain of length 3. You flip all sequences of coins to the left of your first chain.
THHHHHHHTTT   Again, Satan has no choice but to flip coin 1. The chain extends by length 1 again.
...
THHHHHHTTTT   ???
......
TTTTTTTTTTT   Profit!

It turns out that the number of moves required to force a win grows exponentially compared to the number of coins in a row.

Answer 4

Sadly, you never get out.

To see why, let's consider 8 coins to see the pattern. The goal is to gain control, or in other words to get as many tails in a row as possible so that you can get all heads in the end. First, keep tails on the first move to keep the two tails together:

00: TTHHHHHH //Position after first move

Let's call this the base position. Below are the states each time the coins return to the base position if you and satan both flip optimally for your goals (assuming he wants to keep you there and you want to get out):

TTHHHHHH //Position after first move
TTHHHHTH //satan flips the 2nd coin to tails.  
            -he doesn't flip the first because that would give you 3 tails in a row
            -If he doesn't flip any you could flip your tails to heads at the end 
TTHHHTHH //You flip the 2nd coin to tails and he flips the 3rd to heads
TTHHHTTH //satan flips the 2nd coin to tails and you leave the 3rd alone
TTHHTHHH //You flip 2 and 3 to heads and he flips 4 to tails
TTHHTHTH
TTHHTTHH
TTHHTTTH
TTHTHHHH
TTHTHHTH
TTHTHTHH
TTHTHTTH
TTHTTHHH
TTHTTHTH
TTHTTTHH
TTHTTTTH
TTTHHHHH //Yay, 3 tails in a row!
TTTHHHTH
TTTHHTHH
TTTHHTTH
TTTHTHHH
TTTHTHTH
TTTHTTHH
TTTHTTTH
TTTTHHHH //Yay, 4 tails in a row!
TTTTHHTH
TTTTHTHH
TTTTHTTH
TTTTTHHH //Yay, 5 tails in a row!
TTTTTHTH
TTTTTTHH //Yay, 6 tails in a row!
TTTTTTTH //Yay, 7 tails in a row...almost free!
HHHHHHHT //Yay, one more day until you win the game and go free!

The next day, you get up early and excitedly flip the easternmost coin from tales to heads as you move it to the west side of the pile.

Satan sighs and says in a worn-out tone "Congratulations, you've won the game and you are now free to go."

This has been the news you have been waiting for! You eagerly await the Devil's instructions on how to leave this God-forsaken place.

However, after about 15 seconds of awkward silence where you nervously shift between looking at the burning embers and him, you finally ask "Ok, and how do I go about leaving?"

The devil looks up at the cave-like ceiling miles above and says "That's a good question. To tell you the truth I've been thinking about that a lot myself, but I haven't found a way yet. Don't worry though, when I find one I'll be sure and tell you."

You let the words sink in for a bit. "So I'm free to go, but there's no way out? Curse you, what was this game all about?!!?"

The Devil sighs tiredly and says, "Oh nothing really. I just made it up as a way to pass the time..."

Answer 5

You can force a win.

Your strategy is to aim for the string $\phi\gamma$ where $\gamma$ is comprised only of $T$ and $\phi$ is comprised only of $H$ and it is your turn next..

Clearly, a configuration of $H^iT^j$ wins for us... we just make all $T$ into $H$ and win - regardless of $i$, $j$. Call this configuration $win$.

The strategy in general is, We always play $T$ unless it's a $T$ that is not part of our $win$ T string ($\gamma$) in which case we play $H$ (in order to establish $\phi$).

Here is a demonstration: Say, $n=5$: the string, $S$, is $THHHT$.

So your first choice will always be to choose $T$: $TTHHH$.

Our job is to keep the string of $T$s as long as possible.

There are now 8 ways that Satan can play his moves:

$HHHTT$
$TTHTT$
$THTTT$
$HTTTT$
$HHTTT$
$HTHTT$
$THHTT$
$TTTTT$

I'll remove the ones that are an instance of $win$.

$TTHTT$
$THTTT$
$HTHTT$
$THHTT$

So Satan has 4 ways which don't lose automatically.

Now in all these cases, it's our choice. We want to create or facilitate $win$. We leave the $T$ as they are. I will number them now and remove duplicates.

$1.\ TTTTH$
$2.\ TTHTH$
$3.\ TTTHH$

Now it's Satan's turn. In case 1. Satan has lost. He cannot avoid establishing $win$ for us. Leaving us only with these options.

$1.\ TTHTH$
$2.\ TTTHH$

Let's focus on case $2. TTTHH$. There are 4 ways he can play this one.

$2.1\ HHTTT$
$2.2\ HTTTT$
$2.3\ THTTT$
$2.4\ TTTTT$

These are all now lost for Satan. $2.1$,$2.2$ and $2.4$ are an instance of $win$ and $2.3$ after our moves gives $TTTTH$ where Satan cannot avoid establishing $win$ for us.

So, the only complicated case is $1. TTHTH$. This is only case of a broken string of $H$ or $T$ when considered East to West overflow.

Satan has 2 ways to play the next one:

$1.1\ HTTHT$
$1.2\ TTTHT$

In case $1.2$ we win again, by choosing $T$. For case, $1.1\ HTTHT$ which in general will be the from of the only tricky position. We have 2 ways to play. If we play $T$ nothing changes. This is the only case where we must play $H$. And the result is: $HHTTH$

Now Satan has 2 ways to play.

$1.\ HHHTT$ - this is $win$.
$2.\ THHTT$ - we choose $T$ -> $TTTHH$ - now Satan is lost as before. What a loser :D

Answer 6

The base of this solution is the binary interpretation strategy as shown in Lopsy's answer, but with an improvement to $2^n$ moves instead of $n2^n$

With $T \to 1$ and $H \to 0$, interpret the sequence of coins as a binary number starting from a position called the mark (denoted by inserting an M) with the string left of the mark appended to the right end. The value of the mark at that position is the binary value of that sequence. So if $M_1$ is the mark $0M1100$ its value would be $V(M_1)=11000b=24$

Choosing the mark

The correct position of the mark is the one which yields the highest value for the given sequence. For example, $01101 \to 0M1101$ and the value at that mark is binary value of $11010b=26$. There can be multiple positions which are candidates for the mark (e.g. $M101010$, $10M1010$, $1010M10$). In such cases the mark is chosen by:

• If there are no 1s to the left of the leftmost candidate, then the leftmost candidate
• otherwise the rightmost candidate.

For example $0M10010$ or $10110M1$ would be correct marks.

If after a turn the mark is between different coins than it was before the turn, we will say that the mark "jumped". This can happen either when a coin is flipped changing the set of candidate marks, or when the coins are rotated without flipping and a 1 appears on the left forcing a switch from the leftmost candidate to the rightmost candidate.

The Player's strategy:

• If there are no 1s to the left of the mark, flip $1\to 0$
• otherwise do not flip $1\to 1$

Observation

The position of the mark and P's strategy are both completely determined by the current sequence of coins. If the opponent (S) can cause the same sequence to appear twice, then S has a strategy that can repeat that loop forever because P will respond to it exactly the same the second time. By the contrapositive, if we can prove P's stategy must win, then no sequence repeats, so the total number of moves to win is $< 2^n$.

Lemma 1:

The mark can only jump when S flips. Consider the other cases

1. No flip. When there is no flip, the set of mark candidates won't change, so the only way the mark can jump is if the mark started as the leftmost candidate and then a 1 was placed to it's left forcing a switch to the rightmost candidate.
   • 1a. P does not flip. If there are no 1's left of the mark, P's strategy says flip, so this case can't occur.
   • 1b. S does not flip. It's S's move and he doesn't flip, so the coin placed on the left is a 0 and there is no jump.
2. P does flip. Let $M_1$ be the position of the mark prior to the move, which has value $V(M_1)$. Note that unless there are no 1s, meaning P just won, any valid mark candidate has to have a 1 on its left. Since P just flipped, all bits left of $M_1$ are 0, so no position left of $M_1$ is a mark candidate. Let $M_2$ be some position to the right of $M_1$, with value $V(M_2)$. Since $M_1$ was the mark prior to the move, $V(M_2) <= V(M_1)$. The move reduces the value of each mark based on the significance of the bit that was flipped $1\to 0$. Denote the values of $M_1$ and $M_2$ after the move as $V'(M_1)$ and $V'(M_2)$ respectively. Since $M_2$ is right of $M_1$, the flipped bit is more significant to $M_2$ than it is to $M_1$, so $V(M_2)-V'(M_2) > V(M_1)-V'(M_1)$ and thus $V'(M_2) < V'(M_1)'$. So, no position right of $M_1$ can have as high a value as a mark. Therefore $M_1$ is still the correct mark.

Lemma 2: If S doesn't flip during any full cycle of the mark (from left back to left again), then P wins.

By P's strategy, if S does not flip for a full cycle, P will have flipped all coins to 0, winning.

Lemma 3: When S flips a coin, the marked value after the flip will be higher than the marked value after the last time S flipped

1. S's first flip Trivially satisfied
2. The last flipper was S. S can only flip $0\to 1$ so S's move increase the value, which was unchanged since his last flip since P has not flipped since then.
3. The last flipper was P. By P's strategy and Lemma 1, P has not flipped any coins to the right of the mark since S's last flip. Therefore the total decrease in value from P's flips (since S's last flip) is less than the increase in value from S's flip (since it is a more significant bit).

Conclusion

Combining the above, S must keep making flips every cycle to avoid losing, causing the marked value to increase with each flip. Eventually the value reaches $2^n-1$ and the sequence is all 1s, allowing P to win by flipping all coins. Using our original observation, this means P wins in $<2^n$ steps.

We could improve the upper bound slightly given this starting point by eliminating sequences which can be shown to be not encountered. In particular we can see we will never encounter any sequence without one of (first and last position are 1) or (at least 1 run of 1s of length 2) until we get $0...01$ right before P wins. This only eliminates around $F(n-1) + F(n-3) - 2$, which is very small compared to $2^n$ as n grows.

Speculation on lower bound

The following strategy for S might be generally effective

• if there are no 1s left of the mark and flipping will not jump the mark then flip,
• otherwise do not flip

If this strategy can force us to count through all values which wouldn't cause a jump in the mark, then we could use n-nacci numbers to place a lower bound on the number of non-mark jumping values by playing it safe and skipping all values which have a run of 1s as long as the existing longest run of 1s. The would prove that for any $k < 2$, winning takes $\omega(k^n)$ (i.e. that for some constant c > 0 and and sufficiently large n, the number of moves exceeds $ck^n$).

Answer 7

Originally, this question was asked and solved by Gera Weiss in a paper called "A Combinatorial Game Approach to State Nullification by Hybrid Feedback". Here's a link:

http://www.cs.bgu.ac.il/~geraw/Publications_files/CombinatorialGameApproachToStateNullification.pdf

Answer 8

OPTIMAL STRATEGY to escape in less than 2^n days

You can escape in LESS than 2ⁿ days

1. It was already proven that you can ALWAYS escape in 2ⁿ "cycles" (each cycle has n days) which means escape is always possible. Proof for that is in "The Puzzle Toad" link from original problem, even if that is not optimal play (uses more days than needed, ~n*2ⁿ days ).
2. Optimal play require that you never repeat same position (arrangement of the coins) - because that would mean Devil has won since it will just repeat. But in #1 we proved that you can always escape, therefore an optimal win strategy must exist.
3. Since there are at max 2ⁿ different positions, it means optimal play will free the prisoner in max 2ⁿ days from any starting position.
4. But since we start with THH..HHT position, it will require less than 2ⁿ days.

Additionally, it is possible to:

• define how to generate optimal play strategy for n coins
• find an exact formula for max needed days with n coins starting in THH..HHT position, as days= f(n), where f(n) < 2ⁿ

I proved above that it is always possible to escape in less than 2^n days with optimal play. Here I will also show 'how' to do it (strategy), and prove that it is optimal and always possible.

Strategy

1. Generate ordered list of 'win/optimal positions' ( arrangements of n H/T coins ):
   • starts with HH..HH at position #1, which is target win/optimal position (oPos)
   • assuming previous oPos is in form xCCC (where CCC=CC..CC= all coins except leftmost 'x'), then next oPos is either CCCT ( remove 'x' and set 'T' Tail as rightmost ) or CCCH ( if CCCT already exists as previous oPos )
   • continue until you reach 'THH..HHT' position
2. Start playing:
   • find current position in list, and play so that it turns into next (lower numbered) position
   • that is optimal move for both players - for devil, it guarantee maximal days given that you play optimally, and for you it guarantee minimal number of days given that devil plays optimally
   • therefore, after optimal list is generated in step '1', position of 'THH..HHT' is also optimal number of days needed

Example list for 4 coins:

  1: HHHH
  2: HHHT
  3: HHTT
  4: HTTT
  5: TTTT
  6: TTTH
  7: TTHT
  8: THTT
  9: HTTH
 10: TTHH
 11: THHT ***
 12: HHTH
 13: HTHT
 14: THTH
 15: HTHH
 16: THHH

Proof

If we have list of previous 'win positions' ( those that guarantee win for devil's opponent ), next win position is one that will necessarily result in one of those existing (previous) optimal positions after single move.

If we mark previous win position as xCCC, it is obvious that new position CCCT will result in that previous xCCC in one move ( it is your move since CCCT ends up in 'T', and you would turn it into xCCC, whatever 'x' was ).

When you can not add CCCT (because it already exists in list), you can always add CCCH. Reason for that is that existence of CCCT in list imply existence of both TCCC and HCCC in the list - we already have xCCC as last position, but we also must have yCCC ( where y is complement of x, so if x=heads, y=tails and reverse). That is due to fact that already having CCCT somewhere in the list means that position immediately before it was also in the form of yCCC , and since both that yCCC and last position xCCC are on the list (and we can not have two same positions on the list), it means that x<>y ... so one of them is H and other is T , and we are certain we have both TCCC and HCCC as previous win positions.

When we know that both TCCC and HCCC are previous win position, we can add CCCH as new win position, even if that is position where devil will play, because whatever devil play it will end at other win position. It is in devils interest to play xCCC ( last/previous position) instead of yCCC (which would be earlier win position, and would allow you to escape earlier), but regardless of what devil play it ends up in previous win position, so this CCCH can be added as new latest win position.

This proves that , for every last win position, it is always possible to generate single new win position (that new win position would need one more day for win). Since there are 2^n possible positions ( arrangements of Heads/Tails on n coins ), ordered list of win positions will have exactly 2^n positions.

Optimal days ( needed for you to escape if both you and devil play optimally) for any starting coin arrangement is equal to position of that starting coin arrangement in optimal list. For 4 coins example above, "THHT" is at #11 position , which means you will go free "on 11th day" (or reduce one if you count how many days passed instead, so "in 10 days" )

It also means that, regardless of what is initial coin arrangement, it is possible to escape in 2^n days as worst case. And since "THH..HHT" will not be last position in list, it is possible to escape in less than 2^n days if optimally played.

Formula for days=f(n)

As I mentioned before, it is possible to express optimal number of days ( days needed for you to escape if both you and devil play optimally ) as a function of number of coins, when your starting position is THH..HHT.

Obviously, formula for different starting positions would be different. Trivial example is for HH..HT starting position - it will get you free on 2nd day ( in 1 day, after your first move), so f'(n)=2 , regardless of n. It is not guaranteed that all starting position have formula that can return number of days, but THH..HHT has such formula. That formula is without proof here, but it was not part of the question anyway:

days(n)= 2^n - A014739[n-2]

$days(n)= 2^n - \frac{1}{2}\left[(3+\sqrt5)*(\frac{1+\sqrt5}{2})^{n-2}+(3-\sqrt5)*(\frac{1-\sqrt5}{2})^{n-2}\right]+2 $

Where A014739 is integer sequence #A014739 in Sloane index for expansion of (1+x^2)/(1-2*x+x^3). This formula returns "on which day" player will go free, assuming first day is #1. If you need "in how many days" or "moves", then subtract 1.

Upper bound with optimal approach for any starting position is 2^n, and above days(n) formula is obviously days(n)<=2^n. As a comparison, formula for non-optimal "cycle" solution would have upper bound as upCycle(n)= n * 2^n for any starting position, or cycleDays(n)~[2^(n-1)-2]*(n-1) for starting "THHT".

Example for different number of coins:

• n= 4 coins : upCycle= 64 ; 2^n= 16 ; optimal days(n)= 11
• n=20 coins : upCycle= 20,971,520; 2^n= 1,048,576 ; optimal days(n)= 1,033,451

Answer 9

For n=5 I see no way out.

I'm solving from the end state, not from the beginning.

Satan could always make a T at west out of the H at east. That means, what you need as last state before winning is one of these states:

HHHT

HHHTT

HHTTT

HTTTT

For all these, it's impossible that the H at west was an H at east, because satan would not let it unflipped and make you win.

So, the H at west must have been a T at east. That means HHHHT must have been HHHTT, HHHTT must have been HHTTT and so on.

This only leaves TTTTT as entry state to this set of states. But satan can prevent TTTTT by not flipping TTTTH to TTTTT. But if he does so, he has to give you HTTTT and you would win. So, TTTTH (which forces satan to one of two winning nodes) must be on your route to win.

So, how to get to TTTTH?

Going reverse here again:

TTTTH => TTTHH Impossible, satan doesn't make you win.

TTTTH => TTTHT Yes, it was yours.

This goes for every of the T at west. It was never satans H.

So here's the rest.

TTTHT => TTHTT Yes, it was yours.

TTHTT => THTTT Yes, it was yours.

THTTT => HTTTT Yes, it was yours.

Leading to this problem:

HTTTT => TTTTH Impossible, because a goal node can't be a node on your way to the goal.

HTTTT => TTTTT Impossible, satan does not give you TTTTT.

IMHO There's no way out.