3

There is a line of ones and zeroes of length $n$. Every second, $10$ changes to $01$. Prove that it takes no longer than $10n$ seconds until there is nothing to change in the line.

Example:

  1. 1110010
  2. 1101001
  3. 1010101
  4. 0101011
  5. 0010111
  6. 0001111

My reasoning went like this:

  1. base case: obvious (for $0$ and $1$, there's nothing to change from the start);
  2. hypothesis: let's assume the statement is true for a line of length $n$;
  3. step: what can we say about a line of length $n+1$, then? Let's note that a line of length $n+1$ is just a line of length $n$ from the hypothesis with a $1$ or a $0$ added to it (let's say at the right).

If (line of length $n$)$1$, then $1$ stays intact, and we can apply the hypothesis.

If (line of length $n$ ending with $1$)$0$, then it changes to (line of length $n$)$1$, and our time becomes $10n+1$ at most.

However, if (line of length $n$ ending with $0$)$0$, I don't know how to see the following: that, at the last second of $10n$, it's not possible for the before-last $0$ in the line to change to $1$ and start a chain reaction inside the subline of length $n$, giving us $10n+10n=20n>10(n+1)=10n+10$ seconds of time.

While my book suggests induction for this problem, I am interested in and will be grateful for any proof, no matter inductive or not.

Thank you.

fragileradius
  • 1,207
  • 1
    See https://puzzling.stackexchange.com/questions/17403/confused-soldiers. This puzzle is equivalent one linked, where 1 = "soldier facing east" and 0 = "soldier facing west". – Mike Earnest Aug 04 '18 at 15:31

1 Answers1

0

Your hypothesis could be stated more clearly as

For any string of length $n$ there will be no changes after $10n$ seconds

and your induction argument goes through. As you say, a string of length $n+1$ can be considered as a string of length $n$ followed by one more bit. You have justified that a string of length $n+1$ will not change after $10n+1$ seconds. Now observe $10n+1 \le 10(n+1)$ and you have verified the statement for length $n+1$. Yes, the string of length $n$ might change after the first second, but we assumed that any string of that length will not change after $10n$ seconds so we don't care if it changes. The important thing is that you noted the last bit cannot change after the first second.

In fact you don't need the factor $10$ out front. You can do the same proof without it and show that no changes will happen after $n$ seconds for a string of length $n$.

Ross Millikan
  • 374,822