Skip to main content
added 546 characters in body
Source Link
Jafe
  • 80.9k
  • 8
  • 167
  • 654

Let $h$ be the number of heads-up coins. If $h=0$,

We have no starting moves so no solution available.

If $h=1$,

The solution is trivial. Flip the one heads-up coin, after which we have on both sides either a smaller line with $h=1$, or no line at all if the heads-up coin was at either end to start with.

If $h=2$,

There is no solution. There is no move which would bring the number of coins in the current continuous line from 2 to 1. If the heads-up coins are next to each other, flipping either one will leave a tails-up coin with no heads-up coins left. And if there is a gap, flipping either one will create a smaller continuous line with $n=2$$h=2$ and a gap which is one smaller. Eventually you get to a position where the heads-up coins are next to each other.

If $h=3$,

This is always solvable. If the three heads-up coins are next to each other, we can remove the left-most one, leaving the current line with $h=1$. On the left-hand side of the created gap we either have nothing (if the flipped coin was on the edge) or a separate line with $h=1$, so both sides are solvable.

...TTTTHHHTTTT...

Flip the left-most one
...TTTH THTTTT... (both parts are solvable with $h=1$)

For any odd $h$,

We can always "move" the left-most heads-up coin right with the aforementioned process until we have two heads-up coins next to each other on the left side. When we flip those, we're left with $h_{new}=h-2$, eventually reaching 1.

For any even $h$,

I think these are always unsolvable but don't know how.

Let's say $h$ is even and take a look at an arbitrary heads-up coin H. If we look at the sub-lines on the right and left side of H. Since $h$is even, one of the sub-lines has to prove it yethave an even number of heads-up coins and one of them an odd number. When we flip H, one of the coins in the odd sub-line is flipped, resulting in a sub-line with an even number of heads-up coins. This can be zero, but in this case there is always at least one tails-up coin remaining (the one we flipped on our last move). So there is no way to make both sub-lines solvable after the flip.

Let $h$ be the number of heads-up coins. If $h=0$,

We have no starting moves so no solution available.

If $h=1$,

The solution is trivial. Flip the one heads-up coin, after which we have on both sides either a smaller line with $h=1$, or no line at all if the heads-up coin was at either end to start with.

If $h=2$,

There is no solution. There is no move which would bring the number of coins in the current continuous line from 2 to 1. If the heads-up coins are next to each other, flipping either one will leave a tails-up coin with no heads-up coins left. And if there is a gap, flipping either one will create a smaller continuous line with $n=2$ and a gap which is one smaller. Eventually you get to a position where the heads-up coins are next to each other.

If $h=3$,

This is always solvable. If the three heads-up coins are next to each other, we can remove the left-most one, leaving the current line with $h=1$. On the left-hand side of the created gap we either have nothing (if the flipped coin was on the edge) or a separate line with $h=1$, so both sides are solvable.

For any odd $h$,

We can always "move" the left-most heads-up coin right with the aforementioned process until we have two heads-up coins next to each other on the left side. When we flip those, we're left with $h_{new}=h-2$, eventually reaching 1.

For any even $h$,

I think these are always unsolvable but don't know how to prove it yet...

Let $h$ be the number of heads-up coins. If $h=0$,

We have no starting moves so no solution available.

If $h=1$,

The solution is trivial. Flip the one heads-up coin, after which we have on both sides either a smaller line with $h=1$, or no line at all if the heads-up coin was at either end to start with.

If $h=2$,

There is no solution. There is no move which would bring the number of coins in the current continuous line from 2 to 1. If the heads-up coins are next to each other, flipping either one will leave a tails-up coin with no heads-up coins left. And if there is a gap, flipping either one will create a smaller continuous line with $h=2$ and a gap which is one smaller. Eventually you get to a position where the heads-up coins are next to each other.

If $h=3$,

This is always solvable. If the three heads-up coins are next to each other, we can remove the left-most one, leaving the current line with $h=1$. On the left-hand side of the created gap we either have nothing (if the flipped coin was on the edge) or a separate line with $h=1$, so both sides are solvable.

...TTTTHHHTTTT...

Flip the left-most one
...TTTH THTTTT... (both parts are solvable with $h=1$)

For any odd $h$,

We can always "move" the left-most heads-up coin right with the aforementioned process until we have two heads-up coins next to each other on the left side. When we flip those, we're left with $h_{new}=h-2$, eventually reaching 1.

For any even $h$,

I think these are always unsolvable.

Let's say $h$ is even and take a look at an arbitrary heads-up coin H. If we look at the sub-lines on the right and left side of H. Since $h$is even, one of the sub-lines has to have an even number of heads-up coins and one of them an odd number. When we flip H, one of the coins in the odd sub-line is flipped, resulting in a sub-line with an even number of heads-up coins. This can be zero, but in this case there is always at least one tails-up coin remaining (the one we flipped on our last move). So there is no way to make both sub-lines solvable after the flip.

Source Link
Jafe
  • 80.9k
  • 8
  • 167
  • 654

Let $h$ be the number of heads-up coins. If $h=0$,

We have no starting moves so no solution available.

If $h=1$,

The solution is trivial. Flip the one heads-up coin, after which we have on both sides either a smaller line with $h=1$, or no line at all if the heads-up coin was at either end to start with.

If $h=2$,

There is no solution. There is no move which would bring the number of coins in the current continuous line from 2 to 1. If the heads-up coins are next to each other, flipping either one will leave a tails-up coin with no heads-up coins left. And if there is a gap, flipping either one will create a smaller continuous line with $n=2$ and a gap which is one smaller. Eventually you get to a position where the heads-up coins are next to each other.

If $h=3$,

This is always solvable. If the three heads-up coins are next to each other, we can remove the left-most one, leaving the current line with $h=1$. On the left-hand side of the created gap we either have nothing (if the flipped coin was on the edge) or a separate line with $h=1$, so both sides are solvable.

For any odd $h$,

We can always "move" the left-most heads-up coin right with the aforementioned process until we have two heads-up coins next to each other on the left side. When we flip those, we're left with $h_{new}=h-2$, eventually reaching 1.

For any even $h$,

I think these are always unsolvable but don't know how to prove it yet...