Câu hỏi 30
Eva xét các "từ" gồm $n$ kí tự, mỗi kí tự là ‘L’ hoặc ‘R’. Trong một lượt, Eva có thể thay một cụm ‘RL’ ở bất kỳ vị trí nào trong từ bằng ‘LR’. Ví dụ, trong hai lượt, cô biến từ ‘LRRLRRRLR’ thành từ ‘LRLRRRLRR’. Nếu không có ‘L’ nào đứng ngay bên phải một ‘R’ thì Eva không thể thực hiện lượt nào.
a. Eva có một từ như vậy với độ dài $n$. Chứng minh rằng Eva chỉ có thể thực hiện hữu hạn lượt.
b. Cho $n \gt 1$ và $\ell$ với $0 \lt \ell \lt n$. Với mỗi từ độ dài $n$ có đúng $\ell$ kí tự ‘L’, Eva ghi lại số lượt nhiều nhất mà cô có thể thực hiện. Số lớn nhất mà cô đã ghi là bao nhiêu? (Hãy trả lời theo $n$ và $\ell$.)
*Hãy chứng minh câu trả lời của bạn là đúng. Nghĩa là: hãy đưa ra một từ độ dài $n$ có đúng $\ell$ kí tự 'L' mà với nó số lượt tối đa đạt được, và chứng minh rằng số lượt tối đa với mọi từ khác độ dài $n$ có đúng $\ell$ kí tự 'L' không thể lớn hơn.*
c. Cho $n \ge 2$. Với mỗi từ độ dài $n$ (có ít nhất một kí tự 'L' và ít nhất một kí tự 'R'), Eva ghi lại số lượt nhiều nhất mà cô có thể thực hiện. Từ (hoặc các từ) mà với nó cô đã ghi số lớn nhất chứa bao nhiêu kí tự 'L'? (Hãy trả lời theo $n$.)
a. Eva có một từ như vậy với độ dài $n$. Chứng minh rằng Eva chỉ có thể thực hiện hữu hạn lượt.
b. Cho $n \gt 1$ và $\ell$ với $0 \lt \ell \lt n$. Với mỗi từ độ dài $n$ có đúng $\ell$ kí tự ‘L’, Eva ghi lại số lượt nhiều nhất mà cô có thể thực hiện. Số lớn nhất mà cô đã ghi là bao nhiêu? (Hãy trả lời theo $n$ và $\ell$.)
*Hãy chứng minh câu trả lời của bạn là đúng. Nghĩa là: hãy đưa ra một từ độ dài $n$ có đúng $\ell$ kí tự 'L' mà với nó số lượt tối đa đạt được, và chứng minh rằng số lượt tối đa với mọi từ khác độ dài $n$ có đúng $\ell$ kí tự 'L' không thể lớn hơn.*
c. Cho $n \ge 2$. Với mỗi từ độ dài $n$ (có ít nhất một kí tự 'L' và ít nhất một kí tự 'R'), Eva ghi lại số lượt nhiều nhất mà cô có thể thực hiện. Từ (hoặc các từ) mà với nó cô đã ghi số lớn nhất chứa bao nhiêu kí tự 'L'? (Hãy trả lời theo $n$.)