LVIII OM - I - Zadanie 11

Zawody matematyczne:

LVIII OM, 2006-2007

Etap:

Dla każdej liczby całkowitej dodatniej $n$ wyznaczyć liczbę permutacji $(x_1,x_2,\ldots,x_{6n-1})$ zbioru $\{1,2,\ldots,6n{-}1\}$ , spełniających warunki:

$ \begin{split} \hbox{jeśli}\;\;i-j=2n{+}1,\;\;\hbox{to}\;\;x_i>x_j; \\ \hbox{jeśli}\;\;i-j=4n \phantom{{+}1},\;\;\hbox{to}\;\;x_i<x_j. \\ \end{split} $

Rozwiązanie

Odpowiedź: Szukaną liczbą jest

$ \binom{6n-1}{3n+1}\,. $

Dla dowolnej permutacji spełniającej warunki zadania zachodzą następujące ciągi nierówności

$ (1) \qquad \begin{split} x_{2n}<x_{4n+1}&<x_1<x_{2n+2}< x_{4n+3}<x_3<x_{2n+4}<x_{4n+5}<\ldots \\ & <x_{2n-3}<x_{4n-2}<x_{6n-1}<x_{2n-1}<x_{4n}, \end{split} $

$ (2) \qquad \begin{split} x_{2n+1}<x_{4n+2}&<x_2<x_{2n+3}< x_{4n+4}<x_4<x_{2n+5}<x_{4n+6}<\ldots \\ &<x_{2n-4}<x_{4n-3}<x_{6n-2}<x_{2n-2}<x_{4n-1}. \end{split} $

Zauważmy, że każdy z elementów $x_1$ , $x_2$ , $\ldots$ , $x_{6n-1}$ został w rozważanych wierszach wypisany dokładnie raz. Rzeczywiście, w nierównościach (1) pojawiły się wszystkie wskaźniki nieparzyste z przedziału $\langle 1;2n-1\rangle$ , parzyste z przedziału $\langle 2n;4n\rangle$ i nieparzyste z przedziału $\langle 4n+1;6n-1\rangle$ , w nierównościach (2) zaś - wszystkie wskaźniki parzyste z przedziału $\langle 2;2n-2\rangle$ , nieparzyste z przedziału $\langle 2n+1; 4n-1\rangle$ i parzyste z przedziału $\langle 4n+2;6n-2\rangle$ . Badając ilość liczb parzystych i nieparzystych w odpowiednich przedziałach obliczamy, że w związku (1) występuje $n+(n+1)+n=3n+1$ liczb, a w związku (2) występuje $(n-1)+n+(n-1)=3n-2$ liczb.

Nietrudno spostrzec, że każda nierówność postaci $x_i<x_j$ lub $x_i>x_j$ dająca się wywnioskować z warunków zadania znajduje się w zależności (1) lub (2). To oznacza, że jeżeli dla pewnej permutacji oba te ciągi nierówności są spełnione, to permutacja ta ma postulowane własności. Wobec tego każda permutacja spełniająca warunki zadania jest jednoznacznie wyznaczona przez podanie $3n+1$ liczb wypisanych w nierównościach (1) - należy bowiem uszeregować je rosnąco, za $x_{2n}$ przyjąć najmniejszą z tych liczb, za $x_{4n+1}$ liczbę bezpośrednio po niej następującą itd., co pozwala jednoznacznie określić wyrazy permutacji znajdujące się w związkach (1); pozostałe $3n-2$ liczb po ustawieniu w kolejności rosnącej analogicznie określają wyrazy permutacji znajdujące się w związkach (2).

Zatem liczba permutacji mających żądaną własność jest równa liczbie $(3n+1)$ -elementowych podzbiorów zbioru $(6n-1)$ -elementowego, czyli liczbie

$ \binom{6n-1}{3n+1}\,. $