1
$\begingroup$

I hope you can help me with this excersise:

Lets have finite sequence of characters $0$ and $1$. We are doing following algorithm:
If the sequence starts with $0$, we add $00$ to the end.
If the sequence starts with $1$, we add $1101$ to the end.
Then we remove first three characters.

Prove, that if the sequence repeats in cycles, the cycles are of even length.

Proof:
We are changing the length of the sequence, doing $n$ steps, by $n$. To get to the starting state of the loop, the length has to be changed doing $n$ steps, by $-n$. The total number of steps is $2n$, which is even.

We assume, that if $n = n+1$, the number of steps is still even.
We are changing the length of the sequence, doing $n+1$ steps, by $n+1$. To get to the starting state of the loop, the length has to be changed doing $n+1$ steps, by $-(n+1)$. The total number of steps is $2n + 2$, which is even.

Here are some examples:

In order to create a $2$-step loop, we need a sequence starting which some time comes to state $0xx1xx$ or $1xx0x$.
Both these constructions will generate the other one.

To create a $6$-step loop, we need
$1xx1xx1xx0xx0$ or
$1xx1xx0xx0xx0x$ or
$1xx0xx0xx0xx1xx$ or
$0xx0xx0xx1xx1xx1$ or
$0xx0xx1xx1xx1xx$ or
$0xx1xx1xx1xx0x$.
They generate the other one in that order.

  • 1
    *which* sequence repeats? The sequence you start with, the sequence of actions you take, the sequence you end up with, or the sequence of *finite sequences* that you obtain from the process?2010-12-06
  • 0
    It is always the same sequence, and the length of the cycle is the number of steps after it returns to its previous state (not necessarily starting state). E.g. starting sequence 10000 -> 10100 -> 001101 ->10100 -> 001101 -> ... and so on. Here the length of cycle is 2. I found that the length is typically 2 or 6.2010-12-06
  • 1
    Just a nit because you could start with 10100, but shouldn't 10000 to to 001101?2010-12-06
  • 0
    You are correct, i made a mistake, it should be 10000 -> 001101 -> 10100 -> 001101...2010-12-06
  • 0
    Your argument is not very clear in my opinion. For one thing, if you "assume $n=n+1$", then you are assuming that $0=1$ and you can prove anything you want. This is really rather simple: if the cycle is length $n$, then after $n$ steps the total change in length must be $0$. If you apply the first rule (which decreases the total length by $1$) $k$ times, and you apply the second rule (which *increases* the total length by $1$) $\ell$ times, with $n=k+\ell$ being the number of steps in the cycle, then the length changes by $\ell-k$. And since the total change must be $0$...2010-12-06

1 Answers 1

2

Assuming you are talking about the sequence of bitstrings repeating in cycles, and the period of that,

Hint: You either increase the length of the bitstring by 1 or reduce it by 1.

  • 0
    So should I base the proof on the fact, that in order to start cycle, the count of 1 = count of 0?2010-12-06
  • 0
    @Ondrej: No. Length = count of 0 + count of 1.2010-12-06
  • 0
    Maybe you misundestood, or maybe its me, but obviously, the length of bitstring is count of 0 + count of 1. What I meant was that i must happen (count of 0 / count of 1) = 1 in order to create a cycle.2010-12-06
  • 0
    @Ondrej: If it is obvious, then the hint should be clear! Also you talk about cycles being of even length, not the individual bitstrings themselves. In fact the example you gave has a bitstring of length 5 which repeats (and so cannot have count of 0 = count of 1).2010-12-06
  • 0
    We are arguing about different things. We have the Bitstring. Lets call 1 execution of the algorithm a STEP. After some STEPs the Bitstring reaches a state A, when afer n STEPs the state B equals A, and that is our first CYCLE. Then the CYCLE repeats. We want to prove that every n is even. Also I get your hint, I am just not sure, how to put the idea formally.2010-12-06
  • 0
    @Ondrej: We are talking the same thing! And the hint I gave applies to that.2010-12-06
  • 0
    so the proof is: If we increase the length by 2n, then we have to decrease it by 2n on order to achieve original state. 2n + 2n = 4n and that is even. If we increase the length by 2n+1, then we have to decrease it by 2n+1 on order to achieve original state. 2n+1 + 2n+1 = 4n + 2 and that is even.2010-12-06
  • 0
    @ondrej: That is incomplete. You cannot assume there is an increase first, and then a decrease. It could be any combination of increase/decrease.2010-12-06
  • 0
    ok, so: we change the length by 2n, then we have to change it back with -2n and the sum of steps is 0(even). Same with 2n+1 ..we must do -(2n+1).2010-12-06
  • 0
    @Ondrej: What do you exactly mean "change length by 2n"? At what point in the cycle are you talking about this change? In talking about making the change back with -2n, aren't you already assuming something stronger than what you are trying to prove?2010-12-06
  • 0
    I mean if we do 1..2n steps, which will change the length of the string by 1, then we have Sum(the taken steps). In order to achieve original state, we have to do -Sum(..) steps.2010-12-06
  • 0
    I missed the period to edit, so here it is again: I mean if we do 1..2n steps, which will change the length of the string by 1, then we have Sum(the taken steps). In order to achieve original state, we have to do -Sum(..) steps. Same goes for 1..2n+1 steps.2010-12-06
  • 0
    @Ondrej: I suggest you try writing a complete proof and edit that into the question.2010-12-06
  • 0
    I made the proof, what do you think, @Moron? Btw thans for the help so far..2010-12-06
  • 0
    @Ondrej: I don't think it is a valid proof yet. Perhaps you should explicitly mention the number of operations which increase the length (when first bit is 1) and the number of operations which decrease the length (when first bit is 0) and then show that the total is even. btw, Welcome :-)2010-12-06