74
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ All the answers give are quite fun but the devil would win, you're in hell, he's the devil, he does not play by the rules, he can do what ever he wants in hell. $\endgroup$ – Vincent Apr 15 '15 at 8:55
  • 40
    $\begingroup$ The Devil went down to Georgia / lookin' for a soul to claim / so he sat me down at his table / to play a combinatorial game $\endgroup$ – Lopsy Apr 15 '15 at 9:23
  • 12
    $\begingroup$ If hell is a place where we get to play logic puzzles with the devil for eternity, why try to leave? $\endgroup$ – RemcoGerlich Apr 15 '15 at 12:16
  • 12
    $\begingroup$ The game seems fair until you n days in you find out that the last coin is tails on both sides. $\endgroup$ – aslum Apr 15 '15 at 14:40
  • 7
    $\begingroup$ @RemcoGerlich This game only occupies a minute or so of each day, presumedly the rest of the day is not as intellectually stimulating. $\endgroup$ – Mike Earnest Apr 15 '15 at 15:30
50
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ What a nice, simple proof! Unfortunately for Satan, fiddling didn't turn out so well either. $\endgroup$ – xnor Apr 15 '15 at 9:16
  • 4
    $\begingroup$ Since we have now proven you win from every configuration, we can also prove you can win in $2^n$ steps, after all there are only $2^n$ configurations. $\endgroup$ – Dorus Apr 15 '15 at 14:20
  • 2
    $\begingroup$ Although $2^n$ is indeed an upper bound, I contend that your solution is not optimal in terms of fewest moves. $\endgroup$ – Joe Z. Apr 15 '15 at 23:04
  • $\begingroup$ @JoeZ. I agree. As far as I can tell, the optimal solution is as of yet an open problem. One way to optimize this strategy is to rotate the viewing window on certain turns, which can increase the current number. The dynamics quickly become difficult to describe. $\endgroup$ – Mike Earnest Apr 16 '15 at 0:24
  • $\begingroup$ I described them in my solution, although I still haven't made a program to count them yet. $\endgroup$ – Joe Z. Apr 16 '15 at 0:25
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've moved the comments here to chat, as there's valuable content but it's mostly chat content. $\endgroup$ – Aza Apr 15 '15 at 5:46
  • 3
    $\begingroup$ One question - who's Charlie? $\endgroup$ – mdc32 Apr 16 '15 at 19:15
  • 1
    $\begingroup$ @mdc Just a name I gave our poor tortured friend. $\endgroup$ – Aza Apr 16 '15 at 19:16
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The two possibilities after HTHTT in scenario 1 are THHTH and HTHTH. Your solution flips the coins, but doesn't ever move them. $\endgroup$ – Red Alert Apr 15 '15 at 3:50
  • $\begingroup$ I'm in the middle of editing to clarify that. $\endgroup$ – Joe Z. Apr 15 '15 at 3:56
  • $\begingroup$ Also, the reason my solution doesn't move the coins is because it deals in complete revolutions. $\endgroup$ – Joe Z. Apr 15 '15 at 4:14
  • $\begingroup$ @JoeZ. I think I fully understand what you are doing, but your second to last section, where you explain the strategy, could use some expanding. This description, as it stands, does not cover all cases (you turn the first series of heads you see.. then what?). I get that you can piece together what to do from your entire post's discussion, but it would be nicer if you at some point wrote a simple algorithm that clearly describe's Charlie's decisions in all cases, as if programming a Turing machine. $\endgroup$ – Mike Earnest Apr 15 '15 at 6:15
  • 2
    $\begingroup$ Yes it is, and I can't think of any way Satan could beat that. But you should convince Charlie beyond all doubt that your strategy works, for all $n$; false hope is a dangerous thing in Hell, so Charlie won't accept any strategy without a proof. $\endgroup$ – Mike Earnest Apr 15 '15 at 7:09
5
$\begingroup$

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..."

$\endgroup$
  • $\begingroup$ Good point. Prisoner is he. $\endgroup$ – Joshua Apr 16 '15 at 20:09
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Best way to explain it, +1, easyer to follow than the others :) $\endgroup$ – Vincent Apr 15 '15 at 7:26
2
$\begingroup$

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$).

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.