Банк мiста Бат виробляє монети з лiтерою \(H\) на одному боцi та лiтерою \(T\) на iншому боцi. Гаррi виклав \(n\) таких монет у ряд злiва направо. Вiн послiдовно виконує таку операцiю: якщо в ряду рiвно \(k \gt 0\) монет лежать догори лiтерою \(H\), то вiн перевертає \(k\)-ту злiва монету; iнакше усi монети лежать догори лiтерою \(T\) i вiн зупиняється. Наприклад, якщо \(n=3\) та процес починається з конфiгурацiї \(THT\), то послiдовнiсть операцiй матиме такий вигляд: \(THT \to HHT \to HTT \to TTT \), тобто процес зупиниться пiсля трьох операцiй. \( \newline \) (a) Доведiть, що для будь-якої початкової конфiгурацiї процес зупиниться пiсля скiнченної кiлькостi операцiй. \( \newline \) (b) Для кожної початкової конфiгурацiї \(C\) позначимо за \(L(C)\) кiлькiсть операцiй, пiсля яких процес зупиниться. Наприклад, \(L(THT)=3\) та \(L(TTT)=0\). \( \newline \) Знайдiть середнє арифметичне значень \(L(C)\), якщо \(C\) пробiгає всi \(2n\) можливих початкових конфiгурацiй.
| Attributes | Олімпіадна |
|---|---|
| Source | International Mathematical Olympiad |
| Year | 2019 |
| Number | 5 |
| Difficulty | 10.0 |
| Themes |