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 found an interesting problem: We are given $n$ bits in a row, some of them are equal to $1$, and some of them are equal to $0$. This is our starting combination. And we are also given the ending combination. The only operation we can perform is negation of chosen bit. But it negates also its neighbours (first and last bits have only one neighbour). Our task is to find the minimal number of operations we need to perform in order to obtain ending combination from starting combination. Or say it's not possible. By this I mean to write an effective algorithm solving this problem.

For example:

1) start: $1001$; end: $0010$. Optimal number of operations is $2$, because $1001\rightarrow 0101\rightarrow 0010$ (firstly negate first bit, then third).

2) But from: $10$; to: $00$ it is impossible to get.

I think it's a quite well known problem but I'm not sure. Maybe it's known in some other form. I would be very grateful for any hints.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Let consider the input as a vector of $\mathbb{F}_2$, so that $1+1 = 0$. Going from $a$ to $b$ is the same as going from $a+b$ to $0$. Now, there are two cases, you can start from $a+b+\mathtt{00000\ldots}$ or you can start from $a+b+\mathtt{11000\ldots}$ (the first move differs from all the rest, because you change only two places).

Now, the important part is that you should interpret your move not as "with $i$-th bit you change also $i-1$ and $i+1$", but as

With $i$-th bit you change $(i+1)$-th and $(i+2)$-th bits.

That means that you can work with induction, because the previous bits that you have already set won't change. The step is simple, if the $i$-th place is set, you need to apply the bit flip (so it will match $\mathtt{000\ldots}$). The next bits of the sequence might change for better or worse, but the previous part won't. You can work through the all indices and you will be left with $\mathtt{\ldots0000}$ or $\mathtt{\ldots0011}$ or $\mathtt{\ldots0001}$ or $\mathtt{\ldots0010}$. The first two - you win, the second two - you loose.

Observe, that from the start you didn't have much choice, each time you flipped the bit, you had to do it, because it was the only available move that would make the vector match at the considered place. This is informal, but with a bit of work you can make it a proof that the algorithm is optimal, that is, it is the shortest solution, and if you won't find a solution, then there is none.

I hope this helps ;-)

share|improve this answer
    
Sure it helped! Thank you very much :-) –  xan Mar 12 '13 at 20:46
add comment

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.