Initially, a word of letters with letters and letters is written on a blackboard. In each operation, we may choose a contiguous string of any length with equal number of letters and equal number of letters , reverse those letters and then swap each with and each with (Example: after the operation becomes ). Decide if it possible to choose initial word, so that after some operations, it will become the same as the first word, but in reverse order.
Solution
1. Define the initial string and functions:
Let be the initial string of 250 letters, consisting of 125 letters and 125 letters . Define as the number of 's in even positions in a string , and as the number of 's in even positions.
2. Claim:
The value of oscillates between and under the defined move.
3. Proof of the claim:
- Consider a string and a resulting string after performing the operation on a certain substring of .
- If a was in an odd position, reversing the substring sends this to an even position. Then, flipping the letters turns this into an . Thus, every in an odd position is converted into an in an even position.
- The number of 's in odd positions is .
- Therefore, after the operation:
- Performing the operation again on results in:
- This proves that oscillates between and .
4. Reversing the string:
- When we reverse the string , every in an even position goes to an odd position. Let be the reversed string of .
- Therefore:
5. Condition for the string to be the same as the initial string but reversed:
- We need , which implies:
- This is impossible since 125 is odd, and must be an integer.
- Alternatively, we need , which implies:
- Since there are 125 even positions in the 250-letter string, this means:
- This is also impossible for the same reason (125 is odd).
6. Conclusion:
- It is clear that one can never reverse the starting string for any ordering of the letters.
The final answer is False.