Browse · MathNet
PrintUkrainian Mathematical Olympiad
Ukraine counting and probability
Problem
There are soldiers in the captain Petrenko's squad, and none two of them have the same height. The captain has drawn them all up into a single rank (not necessarily sorted by height). We call a "wave" any subsequence of soldiers in this rank (they are not supposed to stand next to each other) such that the first (leftmost) soldier in the wave is higher than the second soldier in it, but the second soldier in it is lower than the third one, who is in turn higher than the fourth one, and so on. (For example, if , the soldiers are enumerated in ascending order by height, and the captain aligned them as 9-3-5-7-1-2-6-4-8, then one of the longest waves for this rank is 9-3-7-1-6-4-8. However, if the captain aligns them as 1-2-3-4-5-6-7-8-9, then each longest wave will consist of a single soldier, who can be anyone.) For every , consider the number of possible ranks with the longest waves of even lengths and the number of possible ranks with the longest waves of odd lengths. Which of these numbers is bigger?
Solution
Спочатку покажемо, що одна з найдовших "хвиль" шеренги містить найвищого солдата цієї шеренги. Дійсно, нехай солдат не входить до жодної найдовшої "хвилі". Якщо вся найдовша "хвиля" знаходиться справа від , то першого солдата "хвилі" замінюємо на . Якщо вся "хвиля" знаходиться зліва від , то "хвиля" має закінчуватися на підйом (інакше, додавши , ми зробили б "хвилю" довшою), і ми останнього солдата "хвилі" замінюємо на . Розглянемо тепер двох солдатів і найдовшої "хвилі", які найближче стоять до по різні боки від цього. Тоді вищого в парі і ми можемо замінити на , і зрозуміло, що при цьому довжина "хвилі" не зміниться.
Далі розглядаються тільки такі найдовші “хвилі”, котрі містять солдата . Серед усіх солдатів шеренги, що стоять справа від (якщо такі існують), оберемо найнижчого. Легко довести, що існує найдовша “хвиля” нашої шеренги, яка містить цього солдата. Серед тих, хто стоїть в шерензі після нього, ми обираємо найвищого. Аналогічно, можемо вважати, що одна з найдовших “хвиль” шеренги містить і цього солдата. Продовжуючи описаний процес, дістанемося такою “хвилею” найбільшої довжини до, принаймні, одного з двох останніх солдатів шеренги. Нехай, наприклад, він був обраний як найвищий у черговому “хвості” шеренги (випадок, коли його обирали як найнижчого в такому “хвості”, розглядається аналогічно). Позначимо цього солдата через . Якщо стоїть на передостанньому місці шеренги, то “хвиля” дістанеться до кінця шеренги, причому буде закінчуватися на “спад”, а тому — міститиме парну кількість солдатів. Якщо ж стоїть на останньому місці шеренги, то найдовша “хвиля” шеренги ним закінчується, причому — на “підйом”, тобто, містить непарну кількість солдатів. Звідси випливає, що коли ми поміняємо місцями останніх двох солдатів шеренги, парність найдовшої “хвилі” шеренги зміниться. Для кожного () існує рівно різних способів вишикувати солдатів у шеренгу. Тому всі перестановок солдатів можна розбити на такі пари, що шеренги однієї пари відрізняються розташуванням лише останніх двох солдатів. За доведеним, найдовша “хвиля” однієї шеренги пари буде складатися з парної кількості солдатів, а найдовша “хвиля” другої шеренги пари — з непарної. Це й завершує розв’язання задачі.
Далі розглядаються тільки такі найдовші “хвилі”, котрі містять солдата . Серед усіх солдатів шеренги, що стоять справа від (якщо такі існують), оберемо найнижчого. Легко довести, що існує найдовша “хвиля” нашої шеренги, яка містить цього солдата. Серед тих, хто стоїть в шерензі після нього, ми обираємо найвищого. Аналогічно, можемо вважати, що одна з найдовших “хвиль” шеренги містить і цього солдата. Продовжуючи описаний процес, дістанемося такою “хвилею” найбільшої довжини до, принаймні, одного з двох останніх солдатів шеренги. Нехай, наприклад, він був обраний як найвищий у черговому “хвості” шеренги (випадок, коли його обирали як найнижчого в такому “хвості”, розглядається аналогічно). Позначимо цього солдата через . Якщо стоїть на передостанньому місці шеренги, то “хвиля” дістанеться до кінця шеренги, причому буде закінчуватися на “спад”, а тому — міститиме парну кількість солдатів. Якщо ж стоїть на останньому місці шеренги, то найдовша “хвиля” шеренги ним закінчується, причому — на “підйом”, тобто, містить непарну кількість солдатів. Звідси випливає, що коли ми поміняємо місцями останніх двох солдатів шеренги, парність найдовшої “хвилі” шеренги зміниться. Для кожного () існує рівно різних способів вишикувати солдатів у шеренгу. Тому всі перестановок солдатів можна розбити на такі пари, що шеренги однієї пари відрізняються розташуванням лише останніх двох солдатів. За доведеним, найдовша “хвиля” однієї шеренги пари буде складатися з парної кількості солдатів, а найдовша “хвиля” другої шеренги пари — з непарної. Це й завершує розв’язання задачі.
Final answer
They are equal; the numbers are the same for every n.
Techniques
Recursion, bijectionEnumeration with symmetryColoring schemes, extremal arguments