Question 30
Eva looks at “words” consisting of $n$ characters, each equal to ‘L’ or ‘R’. In one turn, Eva may replace ‘RL’ anywhere in the word with ‘LR’. For example, in two turns, she takes the word ‘LRRLRRRLR’ to the word ‘LRLRRRLRR’. If there is no ‘L’ immediately to the right of an ‘R’, Eva cannot make a turn.
a. Eva has such a word of length $n$. Prove that Eva can only make a finite number of turns.
b. Given $n \gt 1$ and $\ell$ with $0 \lt \ell \lt n$. For every word of length $n$ with exactly $\ell$ times an ‘L’ Eva writes down how many turns she can take at most. What is the biggest number she wrote down? (Give your answer in terms of $n$ and $\ell$.)
*Prove that your answer is correct. This means: give a word of length $n$ with exactly $\ell$ times the character 'L' for which the maximum number of turns is achieved and prove that the maximum number of turns for all other words of length $n$ with exactly $\ell$ times the character 'L' cannot be greater.*
c. Let $n \ge 2$. For every word of length $n$ (with 1 or more times an 'L' and 1 or more times an 'R') Eva writes down how many turns she can take at most. How many characters 'L' contains the word (or words) for which she has written down the biggest number? (Give your answer in terms of $n$.)
a. Eva has such a word of length $n$. Prove that Eva can only make a finite number of turns.
b. Given $n \gt 1$ and $\ell$ with $0 \lt \ell \lt n$. For every word of length $n$ with exactly $\ell$ times an ‘L’ Eva writes down how many turns she can take at most. What is the biggest number she wrote down? (Give your answer in terms of $n$ and $\ell$.)
*Prove that your answer is correct. This means: give a word of length $n$ with exactly $\ell$ times the character 'L' for which the maximum number of turns is achieved and prove that the maximum number of turns for all other words of length $n$ with exactly $\ell$ times the character 'L' cannot be greater.*
c. Let $n \ge 2$. For every word of length $n$ (with 1 or more times an 'L' and 1 or more times an 'R') Eva writes down how many turns she can take at most. How many characters 'L' contains the word (or words) for which she has written down the biggest number? (Give your answer in terms of $n$.)