Maths Olympiad Prep

Library / /184 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

Initially, a word of 250250 letters with 125125 letters AA and 125125 letters BB is written on a blackboard. In each operation, we may choose a contiguous string of any length with equal number of letters AA and equal number of letters BB, reverse those letters and then swap each BB with AA and each AA with BB (Example: ABABBAABABBA after the operation becomes BAABABBAABAB). 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 T T be the initial string of 250 letters, consisting of 125 letters A A and 125 letters B B . Define fA(S) f_A(S) as the number of A A 's in even positions in a string S S , and fB(S) f_B(S) as the number of B B 's in even positions.

2. Claim:
The value of fA(S) f_A(S) oscillates between fA(T) f_A(T) and 125fB(T) 125 - f_B(T) under the defined move.

3. Proof of the claim:
- Consider a string S S and a resulting string S1 S_1 after performing the operation on a certain substring of S S .
- If a B B was in an odd position, reversing the substring sends this B B to an even position. Then, flipping the letters turns this B B into an A A . Thus, every B B in an odd position is converted into an A A in an even position.
- The number of B B 's in odd positions is 125fB(S) 125 - f_B(S) .
- Therefore, after the operation:
fA(S1)=125fB(S) f_A(S_1) = 125 - f_B(S)
- Performing the operation again on S1 S_1 results in:
fA(S2)=125fB(S1)=125(125fA(S))=fA(S) f_A(S_2) = 125 - f_B(S_1) = 125 - (125 - f_A(S)) = f_A(S)
- This proves that fA(S) f_A(S) oscillates between fA(T) f_A(T) and 125fB(T) 125 - f_B(T) .

4. Reversing the string:
- When we reverse the string T T , every A A in an even position goes to an odd position. Let T T' be the reversed string of T T .
- Therefore:
fA(T)=125fA(T) f_A(T') = 125 - f_A(T)

5. Condition for the string to be the same as the initial string but reversed:
- We need 125fA(T)=fA(T) 125 - f_A(T) = f_A(T) , which implies:
2fA(T)=125 2f_A(T) = 125
- This is impossible since 125 is odd, and fA(T) f_A(T) must be an integer.
- Alternatively, we need 125fA(T)=125fB(T) 125 - f_A(T) = 125 - f_B(T) , which implies:
fA(T)=fB(T) f_A(T) = f_B(T)
- Since there are 125 even positions in the 250-letter string, this means:
fA(T)=125fA(T) f_A(T) = 125 - f_A(T)
- 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.