4
$\begingroup$

You are given this sequence composed of the characters A and B:

A B B B A B B A A B A A B A A B A B A A A B B A B B B A

At each step you can select any contiguous subsequence and flip it.

For example, you can select the highlighted portion of the sequence:

A B B B A B B A A B A A B A A B A B A A A B B A B B B A

And turn it into:

A B B B A A B B A B A A B A A B A B A A A B B A B B B A

How many steps are required at least to turn the initial sequence into a sequence composed of alternating A and Bs?

A B A B A B A B A B A B A B A B A B A B A B A B A B A B

$\endgroup$

2 Answers 2

7
$\begingroup$

A lower bound for the number of moves is

6

because

there are 6 B-B adjacent pairs, and each move can only separate at most one such pair. There are also 5 A-A pairs. So we might solve it if we can do 5 moves that split a BB at one end and an AA at the other, followed by one move for the final BB pair.

This can be done as follows:

A B B B A B B A A B A A B A A B A B A A A B B A B B B A
A B B B A B A B A B A A B A A B A B A A A B B A B B B A
A B B B A B A B A B A A B A A B A B A A B A B A B B B A
A B B A B A B A B A B A B A A B A B A A B A B A B B B A
A B A B A B A B A B A B A B A B A B A A B A B A B B B A
A B A B A B A B A B A B A B A B A B A B A B A B A B B A
A B A B A B A B A B A B A B A B A B A B A B A B A B A B

$\endgroup$
4
  • $\begingroup$ Ha, ninjaed you by a minute and a half :-). $\endgroup$
    – Gareth McCaughan
    May 13, 2020 at 12:47
  • $\begingroup$ @GarethMcCaughan but they also provided the sequence of steps, so they deserve the green tick (: $\endgroup$
    – melfnt
    May 13, 2020 at 20:52
  • 1
    $\begingroup$ But the question wasn't "give the sequence of steps", it was "how many steps?". I answered that question. (My answer proves that the number it gives is correct, and also gives a general way of answering questions of this type.) $\endgroup$
    – Gareth McCaughan
    May 13, 2020 at 23:05
  • $\begingroup$ (For the avoidance of doubt, you're fully entitled to give the checkmark to any answer for any reason. And I'm allowed to say that the reason you gave doesn't make much sense to me :-).) $\endgroup$
    – Gareth McCaughan
    May 13, 2020 at 23:06
5
$\begingroup$

We need

six reversals

for the following reason:

In the starting sequence there are 11 "letter-pairs" AA or BB. We will have succeeded when this figure is reduced to zero. When we reverse a subsequence we can decrease the number of letter-pairs by at most 2, one at each end. We can get a decrease of 2 whenever there is a subsequence that looks like AA...BB or BB...AA (in each case, split the two letter-pairs). If a sequence doesn't have any such subsequence and isn't yet strictly alternating, then either its only pairs are all AA or its only pairs are all BB. (Because if it isn't strictly alternating then it has at least one pair; and if it has an AA pair and a BB pair then we can decrease the pair-count by 2, as above.) For a sequence like this one which has equal numbers of A and B, there can then only be one letter-pair. (Suppose e.g. there are exactly two and they are both AA. Then we have ...AA...AA... where each ... is strictly alternating; the portion up to the first A has at least as many A as B, the portion from the last A onward has too, and the A...A section in between has one more A than B.) In this case we have ...AA... and to have equal numbers of A and B the ends must be B. So split the letter-pair and reverse either of the two pieces, and we are done. What we have shown is that if we have a sequence of $2n$ letters composed of $n$ As and $n$ Bs, and if the number of adjacent AA or BB pairs is $m$, then the number of reversals we need is the "ceiling" of (smallest integer not smaller than) $\frac m2$. In the present case where $m=11$ this means we need six reversals.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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