Skip to main content
added 519 characters in body
Source Link
Jaap Scherphuis
  • 55.7k
  • 8
  • 130
  • 221

The row of coins can be fully removed if it has the following property:

It has an odd number of heads

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins with an odd number of heads.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it is solvable by the induction hypothesis. The row to the left will also have an odd number of coins because before the flip it had en even number, so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable (and a good next move is the last heads of the row).

Case 2: A row of $n+1$ coins with an even number of heads.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has an even number of heads (one removed, and and coin flipped), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have an even number, the other will have an odd number of heads. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins changes the parity of the number of heads to odd, and splitting the row then means that exactly one of the resulting rows must be odd and one even. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.

Solving strategy:

The proof shows that you can solve a row by always making your move on the last (or first) heads coin of the row.
Note that making a move in the middle somewhere can sometimes lead to a dead end, where it splits the row into two that are both unsolvable (both have an even number of heads). The simplest example is of course a row of three heads (HHH) which would turn into two separate tails coins if your move was the middle one.

The row of coins can be fully removed if it has the following property:

It has an odd number of heads

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins with an odd number of heads.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it is solvable by the induction hypothesis. The row to the left will also have an odd number of coins because before the flip it had en even number, so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable.

Case 2: A row of $n+1$ coins with an even number of heads.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has an even number of heads (one removed, and and coin flipped), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have an even number, the other will have an odd number of heads. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins changes the parity of the number of heads to odd, and splitting the row then means that exactly one of the resulting rows must be odd and one even. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.

The row of coins can be fully removed if it has the following property:

It has an odd number of heads

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins with an odd number of heads.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it is solvable by the induction hypothesis. The row to the left will also have an odd number of coins because before the flip it had en even number, so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable (and a good next move is the last heads of the row).

Case 2: A row of $n+1$ coins with an even number of heads.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has an even number of heads (one removed, and and coin flipped), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have an even number, the other will have an odd number of heads. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins changes the parity of the number of heads to odd, and splitting the row then means that exactly one of the resulting rows must be odd and one even. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.

Solving strategy:

The proof shows that you can solve a row by always making your move on the last (or first) heads coin of the row.
Note that making a move in the middle somewhere can sometimes lead to a dead end, where it splits the row into two that are both unsolvable (both have an even number of heads). The simplest example is of course a row of three heads (HHH) which would turn into two separate tails coins if your move was the middle one.

Post Undeleted by Jaap Scherphuis
deleted 529 characters in body
Source Link
Jaap Scherphuis
  • 55.7k
  • 8
  • 130
  • 221

The row of coins can be fully removed if it has the following property:

Number the coint locations in the row from $1$ to $n$. Count the number of heads at theIt has an odd-numbered locations. Also count the number of heads at the odd-numbered locations. The row is solvable if those two counts have different parities, i.e. one of them is even and the other is odd. If they have the same parity then it is not solvable.

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins where the two parities are differentwith an odd number of heads.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it has different parities and is solvable by the induction hypothesis. The row to the left will also have different parities (one parity changed becausean odd number of the heads coin at location $m$ you removed, the other parity changedcoins because ofbefore the flipped coin at location $m-1$)flip it had en even number, so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable.

Case 2: A row of $n+1$ coins where the two parities are the samewith an even number of heads.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has its two parities the samean even number of heads (both changed, one by removing a head coinone removed, the other changed by flipping the adjacentand and coin flipped), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have equal paritiesan even number, the other will have differing paritiesan odd number of heads. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins causeschanges the paritiesparity of the number of heads to become differentodd, and splitting the row then means that exactly one of the resulting rows must have that different parity while the other does notbe odd and one even. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.

The row of coins can be fully removed if it has the following property:

Number the coint locations in the row from $1$ to $n$. Count the number of heads at the odd-numbered locations. Also count the number of heads at the odd-numbered locations. The row is solvable if those two counts have different parities, i.e. one of them is even and the other is odd. If they have the same parity then it is not solvable.

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins where the two parities are different.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it has different parities and is solvable by the induction hypothesis. The row to the left will also have different parities (one parity changed because of the heads coin at location $m$ you removed, the other parity changed because of the flipped coin at location $m-1$), so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable.

Case 2: A row of $n+1$ coins where the two parities are the same.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has its two parities the same (both changed, one by removing a head coin, the other changed by flipping the adjacent coin), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have equal parities, the other will have differing parities. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins causes the parities to become different, and splitting the row then means that exactly one of the resulting rows must have that different parity while the other does not. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.

The row of coins can be fully removed if it has the following property:

It has an odd number of heads

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins with an odd number of heads.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it is solvable by the induction hypothesis. The row to the left will also have an odd number of coins because before the flip it had en even number, so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable.

Case 2: A row of $n+1$ coins with an even number of heads.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has an even number of heads (one removed, and and coin flipped), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have an even number, the other will have an odd number of heads. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins changes the parity of the number of heads to odd, and splitting the row then means that exactly one of the resulting rows must be odd and one even. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.

Post Deleted by Jaap Scherphuis
Source Link
Jaap Scherphuis
  • 55.7k
  • 8
  • 130
  • 221

The row of coins can be fully removed if it has the following property:

Number the coint locations in the row from $1$ to $n$. Count the number of heads at the odd-numbered locations. Also count the number of heads at the odd-numbered locations. The row is solvable if those two counts have different parities, i.e. one of them is even and the other is odd. If they have the same parity then it is not solvable.

Proof:

By induction.
The property obviously correctly predicts solvability for a row of length 1, where "H" is solvable and "T" is not.
Suppose the property correctly predicts solvability for the row lengths $1$ to $n$.

Case 1: A row of $n+1$ coins where the two parities are different.
Do a move on the last heads coin, which is at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If the row to the right is non-empty, it will have one head (at location $m+1$ that you flipped) and the rest tails, so it has different parities and is solvable by the induction hypothesis. The row to the left will also have different parities (one parity changed because of the heads coin at location $m$ you removed, the other parity changed because of the flipped coin at location $m-1$), so that is also solvable by the induction hypothesis. Therefore the original row of $n+1$ coins is solvable.

Case 2: A row of $n+1$ coins where the two parities are the same.
Do a move on any heads coin, at location $m$. This leaves a row of coins to the left of length $m-1$, and a row to the right of length $n-m+1$. If either of the two rows is empty ($m=1$ or $m=n+1$), then we have a single row of $n$ coins that still has its two parities the same (both changed, one by removing a head coin, the other changed by flipping the adjacent coin), so it is unsolvable by the induction hypothesis.
If you really do have two rows now, then one of the rows will have equal parities, the other will have differing parities. You can think of the move as flipping three coins in a row (the middle of which was heads) and then removing the middle tails coin to split the row. Flipping the three coins causes the parities to become different, and splitting the row then means that exactly one of the resulting rows must have that different parity while the other does not. By the induction hypothesis, one of these rows is not solvable.
The coins become unsolvable whichever move you make, so the original row was unsolvable.

By induction, the property correctly predicts solvability for all values of $n$.