Initially, a word of $250$ letters with $125$ letters $A$ and $125$ letters $B$ is written on a blackboard. In each operation, we may choose a contiguous string of any length with equal number of letters $A$ and equal number of letters $B$, reverse those letters and then swap each $B$ with $A$ and each $A$ with $B$ (Example: $ABABBA$ after the operation becomes $BAABAB$). 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.
Problem
Source: All-Russian MO 2023 Final stage 9.2
Tags: combinatorics
23.04.2023 19:08
I'm not sure I understand correctly. It seems that we can always just swap any two adjacent digits. But then we can clearly permute the digits in any way we like, in particular we can reach the same string written backward.
23.04.2023 19:17
This was wrong! The Real problem was : Initially, one write letter on a line , 250 letters with 125 letter A and 125 letter B arrange in some order. In each operation, We may choose a piece of consecutive string with equal number of letter A and equal number of letter B (Any length) . then reverse those letters and then swap B into A and swap A into B (Example : ABABBA after the operation it became BAABAB ). Define if it possible to choose initial line, after some operations , it will became the same line but in reverse order.
23.04.2023 20:18
Now it is fixed, sorry for the mistake. @below, okay, done.
23.04.2023 20:22
a_507_bc wrote: Now it is fixed, sorry for the mistake. You should post the original problem , this problem remind me of IMO 2022 P1 @above thank you
24.04.2023 11:33
Vintage Russian. Consider $S=$ #of $A$s at odd positions - #of $A$s at even positions. We claim this value never changes. This is because if an $A$ becomes $B$ in an operation, then its "mirror" in the contiguous string must have also changed from $A$ to $B$. The same is true for $B$ becoming $A$. If an $A$ remains an $A$, its "mirror" $B$ will still stay a $B$. Since each letter and its "mirror" always differ by an odd number of positions, the value never changes. Note that the number of $A$s never change as well. Note the reverse order of the first word has $A$s switching their position parity. Hence we need $S=-S$ or $S=0$. But $S$ is odd since it is $\equiv 125 \pmod2$, so it is impossible.
25.04.2023 10:34
It is impossible to do such thing. We replace the letter A with the vector $(1,1)$ and the letter B with the vector $(1,-1)$. Then the word can be regarded as a broken line segment from $(0,0)$ to $(250,0)$. After an operation, a segment from $(a,i)$ to $(a+2k,i)$($i=-1,0,\text{or},1$) is reflected by the line $x=a+k$. Our goal is, reflect the whole broken line segment by the $x$-axis. For a segment from $(2l,0)$ to $(2m,0)$($l<m$),if $m-l$ is an odd number, and we reflected the segment by $x=m+l$,then the ordinate of the point whose x-coordinate is $m+l$ can't be changed and be zero, so it's impossible to change it in reverse order.
04.05.2023 11:07
@zjugh Our goal is, reflect.... This and subsequent parts seem incorrect.
23.08.2023 01:30
This is impossible to happen. Let $x$ be the number of distinct pairs of $A$ and $B$ in the string where $A$ appears before $B$; and let $y$ be the similar quantity for pairs of $B$ before $A$. By following a specific pair of $A$ and $B$ one sees that $x$ and $y$ are invariant under the procedure. Also $x + y = \binom{250}{2} $ which is odd, so $x\neq y$. But if the string is somehow reversed, $x$ and $y$ would interchange and we must have $x = y$, which is impossible.
30.12.2023 16:01
Solved with rama1728. Let $T$ be the initial string. Let $f_A(S)$ denote the number of $A$s in an even position in a string $S$ and $f_B(S)$ the number of $B$s in an even position. We simply observe the following invariant property of this function under this move. Claim : The value of $f_A(S)$ ossilates between $f_A(T)$ and $125-f_B(T)$ under the defined move. Proof : Say $S_1$ is the resulting string after a move is done on a certain substring of $S$. If a $B$ was in an odd position, we first reverse the string, sending this $B$ to an even position. Then, flipping the letters turns this into an $A$. Thus, every $B$ in an odd position is converted into an $A$ in an even position. Now, the number of $B$s in an odd position is equal to $125-f_B(S)$. \[f_A(S_1)=125-f_B(S)\]Doing this once more will leave one with \[f_A(S_2)=125-f_B(S_1)=125-(125-f_A(S))=f_A(S)\]Thus, we are done with proving the claim. Now, note that when we reverse the string, as mentioned before, every $A$ in an even position goes to an odd position thus, if $T'$ is the reversed string of $T$, \[f_A(T')=125-f_A(T)\]We wish to have, $125-f_A(T)=f_A(T)$ which is impossible since $125$ is odd or $125-f_A(T)=125-f_B(T)$ which requires, $f_A(T)=f_B(T)$ since there are $125$ even positions in this $250$ letter string, this means, $f_A(T)=125-f_A(T)$ which is again impossible for the same reason. Thus, it is clear that one can never reverse the starting string for any ordering of the letters.