0
$\begingroup$

Given a string made up of only letters $\mathsf{x}$, $\mathsf{y}$ and $\mathsf{z}$, we need to determine whether it can be changed into a string such that each three-letter substring of the string is either $\mathsf{xyz}$, $\mathsf{yzx}$ or $\mathsf{zxy}$. The only operation permitted is we can select a substring of length three that is not one of these three forms and then rearrange the three letters in any order.

Note that each target string is of the form either $\mathsf{xyzxy\ldots}$ or $\mathsf{yzxyz\ldots}$ or $\mathsf{zxyzx\ldots}$, and is in this sense cyclic.

Now, in the given string the counts of each letter $\mathsf{x}$, $\mathsf{y}$ and $\mathsf{z}$ is such that a cyclic string is possible (e.g., if the string has $8$ characters, then two of the letters must have three occurrences in the string, and the third letter two occurrences). Now, it is necessary to prove that we can rearrange the letters using the permitted operation and create a cycle.

I am confused at this part. How to prove that within a finite number of such operations, we can indeed obtain a cycle?

Example:

  • Suppose the given string is $\mathsf{xxyyyzzz}$, so the $\mathsf{x}$-count is $2$, the $\mathsf{y}$-count is $3$, and the $\mathsf{z}$-count is $3$. We can see that the cycle obtainable from the given string is $\mathsf{yzxyzxyz}$ ($\mathsf{x}$-count $2$, $\mathsf{y}$-count $3$, $\mathsf{z}$-count $3$).

    Now we need to apply the operation of selecting a three-letter substring not equal to either $\mathsf{xyz}$, $\mathsf{yzx}$ or $\mathsf{zxy}$. We can try rearranging using the allowed operation and we can see that we can finally obtain the string $\mathsf{yzxyzxyz}$ from $\mathsf{xxyyyzzz}$.

And guys, when solving such problems, I sometimes get solution intuitively but can't find a proof. And this tenses me much because I can't prove why its correct. So any tips about it would be helpful (how to attack and get a proof).

$\endgroup$
0
$\begingroup$

You always can move a badly placed letter to the first place where it's well placed, isn't it enough ?

As an example if you have :

$_x$xyzxyzxyz

xy$_x$zxyzxyz

xyzx$_x$yzxyz

xyzxy$_x$zxyz

xyzxyzx$_x$yz

xyzxyzxyz$_x$

It's equivalent to say that you always can "move" a well formed subpart of the string to form a biger one (if the number of each letter allows a solution)

as an exemple :

...xxxx$_{xyz}$yyyx...

...xxxx$_{yxyz}$yyx...

...xxxxy$_{yxyz}$yx...

...xxxxyy$_{yxyzx}$...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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