MathDB

Problem 8.4

Part of 2022 Bulgarian Spring Math Competition

Problems(1)

Optimistic permutations of a set

Source: 2022 Bulgarian Spring Math Competition, Problem 8.4

3/27/2022
Let p=(a1,a2,…,a12)p = (a_{1}, a_{2}, \ldots , a_{12}) be a permutation of 1,2,…,121, 2, \ldots, 12. We will denote Sp=∣a1−a2∣+∣a2−a3∣+…+∣a11−a12∣S_{p} = |a_{1}-a_{2}|+|a_{2}-a_{3}|+\ldots+|a_{11}-a_{12}|We'll call pp <spanclass=′latex−italic′>optimistic</span><span class='latex-italic'>optimistic</span> if ai>min⁡(ai−1,ai+1)a_{i} > \min(a_{i-1}, a_{i+1}) ∀i=2,…,11\forall i = 2, \ldots, 11. a)a) What is the maximum possible value of SpS_{p}. How many permutations pp achieve this maximum?\newline b)b) What is the number of <spanclass=′latex−italic′>optimistic</span><span class='latex-italic'>optimistic</span> permtations pp? c)c) What is the maximum possible value of SpS_{p} for an <spanclass=′latex−italic′>optimistic</span><span class='latex-italic'>optimistic</span> pp? How many <spanclass=′latex−italic′>optimistic</span><span class='latex-italic'>optimistic</span> permutations pp achieve this maximum?
combinatoricsPermutations with restrictions