Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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? –  Arturo Magidin Dec 6 '10 at 17:27
    
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. –  Ondrej Sotolar Dec 6 '10 at 17:53
1  
Just a nit because you could start with 10100, but shouldn't 10000 to to 001101? –  Ross Millikan Dec 6 '10 at 18:25
    
You are correct, i made a mistake, it should be 10000 -> 001101 -> 10100 -> 001101... –  Ondrej Sotolar Dec 6 '10 at 18:36
    
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$... –  Arturo Magidin Dec 6 '10 at 22:54
add comment

1 Answer

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.

share|improve this answer
    
So should I base the proof on the fact, that in order to start cycle, the count of 1 = count of 0? –  Ondrej Sotolar Dec 6 '10 at 18:05
    
@Ondrej: No. Length = count of 0 + count of 1. –  Aryabhata Dec 6 '10 at 18:07
    
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. –  Ondrej Sotolar Dec 6 '10 at 18:13
    
@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). –  Aryabhata Dec 6 '10 at 18:23
    
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. –  Ondrej Sotolar Dec 6 '10 at 18:51
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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