Danube 2007 - Problema 1

[Madalina]

Fie \( n\geq2 \) un numar natural si \( S_{n} \) multimea permutarilor pe \( \{1,\ 2,\ ...\ , \ n} \). Pentru \( s \in S_{n} \) definim \( l(s) = \min |s(i+1) - s(i)|,\ 1 \leq i \leq n-1 \). Sa se determine \( \max\ l(s), \ s \in S_{n} \).

[Filip Chindea]

Welcome to mateforum! Pentru mai multe detalii tehnice relativ la comenzile \( \LaTeX \), vezi si topicurile corespunzatoare.

Madalina wrote:

Pentru orice întreg pozitiv \( n \ge 2 \) determinati

\( \max_{\sigma \in S_n} \ \min_{k \in \overline{1, n-1}} |\sigma(k + 1) - \sigma(k)| \).

Afirmam ca \( l(\sigma) \le \lfloor \frac{n}{2} \rfloor \). Acest maxim este atins efectiv, de exemplu, de
\( \left\{ \begin{array}{lcll} n = 2k, k \in \mathbb{Z}_+ & \Rightarrow & \sigma(2m + 1) = k - m, & \sigma(2m) = n + 1 - m \\ n = 2k - 1, k \in \mathbb{Z}_+ \backslash \{ 1 \} & \Rightarrow & \sigma(2m - 1) = m, & \sigma(2m) = k + m \end{array} \right. \).
Mai ramane de vazut ca exista un modul cel mult egal cu pragul propus; însa \( \sigma \) bijectiva, deci ia valoarea \( \lfloor \frac{n}{2} \rfloor + 1 \), iar pentru \( v \in \overline{1, n} \) luata în punctul adiacent are loc \( \left| \lfloor \frac{n}{2} \rfloor + 1 - v \right| \le \lfloor \frac{n}{2} \rfloor \).
PS. Asa cum am formulat cerinta, tot ce ai de facut e sa vezi "behind the scenes", solutia este destul de naturala