XLIX OM - I - Zadanie 7

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

Dane są liczby całkowite dodatnie $m$ oraz $n$ . Niech $A=\{1,2,3,\ldots,n\}$ . Wyznaczyć liczbę funkcji $f:A \to A$ przyjmujących dokładnie $m$ wartości oraz spełniających warunek:

$ \textrm{jeżeli } k,l \in A,\ k \leq l, \textrm{ to } f(f(k)) = f(k) \leq f(l). $

Rozwiązanie

Sposób I} Funkcję $f$ spełniającą podane warunki będziemy nazywać {\it dobrą

. Jest jasne, że jeśli $m>n$ , to dobre funkcje nie istnieją. Wystarczy więc zająć się przypadkiem, gdy zadane liczby naturalne $n$ i $m$ spełniają nierówność $n \geq m \geq 1$ .

Niech $f:A \to A$ będzie funkcją dobrą i niech liczby $k_1<\ldots < k_m$ będą wszystkimi jej wartościami. Dla każdego numeru $i\in\{1,\ldots,m\}$ określamy:

$ \qquad (1) l_i = \textrm{największa liczba } j \in A, \textrm{ dla której } f(j) = k_i. $

Oczywiście $l_m=n$ . Z określenia (1) oraz z warunków definiujących funkcje dobre wynika, że $f(k_i)=f(f(l_i))=f(l_i)=k_i$ , dla $i=1,\ldots,m$ , i wobec tego

$ \qquad (2) 0<k_1\leq l_1 <k_2 \leq l_2 < \ldots < k_{m-1} \leq l_{m-1}<k_m\leq n. $

Na odwrót, jeżeli $(k_1,l_1,k_2,l_2, \ldots , k_{m-1}, l_{m-1}, k_m)$ jest dowolnym ciągiem liczb naturalnych spełniającym warunki (2), to wzór

$ f(j)= \left\{\begin{array}{lll} k_1&\textrm{gdy}& 0 <j \leq l_1\\ k_2&\textrm{gdy}& l_1 <j \leq l_2\\ &\vdots&\\ k_m&\textrm{gdy}& l_{m-1} <j \leq n\\ \end{array}\right. $

określa dobrą funkcję $f:A\to A$ , której wartościami są liczby $k_i$ , a warunek (1) wyznacza zadane liczby $l_i$ (trzeba tylko przyjąć $l_m=n$ ). Dobrych funkcji $f$ jest więc tyle, ile ciągów typu (2).

Każdemu ciągowi liczb naturalnych spełniającemu warunki (2) przyporządkujemy ciąg $(a_1,b_1,a_2,b_2,\ldots,a_{m-1},b_{m-1},a_m)$ o wyrazach

$ \qquad (3)\begin{split} &a_i = k_i+i - 1 \textrm{ dla } i = 1,\ldots,m, \\ &b_i = l_i + i \textrm{ dla } i = 1,\ldots,m-1. \end{split} $

Z układu nierówności (2) wynika, że wówczas

$ \qquad (4) 0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_{m-1} < b_{m-1} < a_m < n + m. $

Na odwrót, mając dany dowolny ciąg spełniający warunki (4) możemy odtworzyć ciąg $(k_1,l_1,k_2,l_2,\ldots,k_{m-1},l_{m-1},k_m)$ przyjmując

$ \qquad (3)\begin{split} &k_i = a_i-i + 1 \textrm{ dla } i = 1,\ldots,m, \\ &l_i = b_i - i \textrm{ dla } i = 1,\ldots,m-1; \end{split} $

nierówności (2) będą spełnione. Wzajemnie odwrotne układy równań (3) i (5) ustalają wzajemnie jednoznaczną odpowiedniość między ciągami typu (2) i ciągami typu (4).

Wniosek: dolnych funkcji $f: A \to A$ jest tyle, ile $(2m-1)$ --wyrazowych ciągów liczb naturalnych spełniających warunki (4) - czyli tyle, ile $(2m-1)$ --elementowych podzbiorów ma zbiór $\{1,2,\ldots,n+m-1\}$ . Ta szukana liczba jest równa $\binom{n+m-1}{2m-1}$ .

Sposób II

Niech $f:A\to A$ będzie funkcją dobrą (zachowujemy tę na zwę z poprzedniego rozwiązania). W prostokątnym układzie współrzędnych zaznaczmy punkty wykresu funkcji $f$ , czyli punkty $(j,f(j))$ dla $j = 1,\ldots, n$ . Każdy taki punkt $(j,f(j))$ jest środkiem kwadratu jednostkowego (lewym dolnym wierzchołkiem tego kwadratu jest punkt $(j- \frac{1}{2}, f(j)-\frac{1}{2})$ ).

Podana implikacja $k\leq l \Rightarrow f(k)\leq f(l)$ oznacza, że funkcja. $f$ jest niemalejąca. Zaznaczone kwadraty układają się więc w poziome paski odpowiadające wartościom funkcji $f$ ; każdy kolejny pasek (gdy je liczymy od lewej do prawej strony) jest położony wyżej niż poprzedni.

Warunek $f(f(k)) = f(k)$ mówi, że jeśli liczba $w$ jest wartością funkcji $f$ , to punkt $(w,w)$ jest jednym z zaznaczonych punktów. Kwadrat jednostkowy o środku w tym punkcie jest zawarty w pasku odpowiadającym wartości $w$ ; zaznaczmy ten kwadrat krzyżykiem. W ten sposób w każdym pasku został wyróżniony jeden kwadracik.

Przesuńmy teraz wszystkie te paski w kierunku pionowym tak, by ich poziomy zrównały się. Tworzy się jeden pasek $P$ długości $n$ podzielony na $m$ bloków, a w każdym bloku jest wyróżniony jeden kwadracik.

Na odwrót, jeśli mamy dany prostokąt $P$ o wymiarach $n \times 1$ , złożony z $n$ kwadratów jednostkowych, z zaznaczonymi liniami dzielącymi go na $m$ bloków (prostokątów o długościach całkowitych dodatnich) i z wyróżnionym jednym kwadratem w każdym bloku, to możemy przesunąć każdy blok do takiego położenia, by środek wyróżnionego kwadratu trafił na prostą $y = x$ ; środki wszystkich kwadratów tak poprzesuwanych bloków utworzą wykres dobrej funkcji $f$ .

Pomiędzy każde dwa kolejne bloki, z których składa się prostokąt $P$ wstawmy po jednym dodatkowym kwadracie jednostkowym. W ten sposób dołożyliśmy $m-1$ kwadratów. Oznaczmy je kółkami. Powstał prostokąt $Q$ złożony z $n+m-1$ kwadratów, przy czym $m$ kwadratów jest oznaczonych krzyżykami, a $m-1$ - kółkami. Każde ,,kółko'' leży między dwoma ,,krzyżykami''.

Każdy taki diagram możemy uważać za kod pewnej dobrej funkcji $f$ , pozwalający jednoznacznie odtworzyć tę funkcję. [Na przykład prostokąt $Q$ z rysunku 4, z zaznaczonymi krzyżykami i kółkami, powstał przez rozsunięcie bloków prostokąta $P$ , który odpowiada funkcji $f:\{1,\ldots,8\} \to \{1,...,8\}$ danej wzorami: $f(1) = f(2) = f(3) = 2$ , $f(4)=4$ , $f(5) = f(6) = f(7) = f(8) = 5$ .]

Pozostaje zliczyć takie diagramy (dla ustalonych liczb $n\geq m\geq 1$ ). Zauważmy, że znając pozycje $2m-1$ wyróżnionych kwadratów, nie potrzebujemy informacji, które; z nich są oznaczone krzyżykami, a które kółkami: wiadomo, że te dwa rodzaje oznaczeń występują na przemian, przy czym na skrajnych pozycjach są krzyżyki. Problem został zatem sprowadzony do policzenia, na ile sposobów można wybrać $2m-1$ kwadratów z rządku liczącego $n+m-1$ kwadratów. Liczba ta jest równa $\binom{n+m-1}{2m-1}$ ; i jest to jednocześnie liczba dobrych funkcji $f$ (dla zadanych $n$ , $m$ ).

Uwaga: Powyższe dwa rozwiązania nie różnią się istotnie. Argumentacja kombinatoryczna, przedstawiona w drugim rozwiązaniu w sposób dość poglądowy, daje się sformalizować. Efektem formalizacji jest pierwsze rozwiązanie - choć dostrzeżenie, że tak rzeczywiście jest, może wymagać trochę wysiłku. (Na przykład wprowadzenie składników ,,i'' we wzorach (3) i (5) odpowiada operacji rozsunięcia bloków i wstawienia kwadratów z „kółkami" w rozwiązaniu sposobem II.)

XLIX OM - I - Zadanie 7

Rozwiązanie

Sposób I} Funkcję spełniającą podane warunki będziemy nazywać {\it dobrą

Sposób II

Sposób I} Funkcję $f$ spełniającą podane warunki będziemy nazywać {\it dobrą