MathDB

4

Part of 2016 Korea Summer Program Practice Test

Problems(1)

Inequality on the number of local extrema and saddles

Source: Korean Summer Program Practice Test 2016 4

8/17/2016
Two integers 0<k<n0 < k < n and distinct real numbers a1,a2,…,ana_1, a_2, \dots ,a_n are given. Define the sets as the following, where all indices are modulo nn. \begin{align*} A &= \{ 1 \le i \le n : a_i > a_{i-k}, a_{i-1}, a_{i+1}, a_{i+k} \text{ or } a_i < a_{i-k}, a_{i-1}, a_{i+1}, a_{i+k} \} \\ B &= \{ 1 \le i \le n : a_i > a_{i-k}, a_{i+k} \text{ and } a_i < a_{i-1}, a_{i+1} \} \\ C &= \{ 1 \le i \le n ; a_i > a_{i-1}, a_{i+1} \text{ and } a_i < a_{i-k}, a_{i+k} \} \end{align*} Prove that ∣A∣≥∣B∣+∣C∣\lvert A \rvert \ge \lvert B \rvert + \lvert C \rvert.
combinatorics