Komentarz

XLIX OM - I - Zadanie 7

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:

\[<br /> \textrm{jeżeli } k,l \in A,\ k \leq l, \textrm{ to } f(f(k)) = f(k) \leq f(l).<br /> \]

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:

\[<br /> \qquad (1) l_i = \textrm{największa liczba } j \in A, \textrm{ dla której } f(j) = k_i.<br /> \]

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

\[<br /> \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.<br /> \]

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

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

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

\[<br /> \qquad (3)\begin{split}<br /> &a_i = k_i+i - 1 \textrm{ dla } i = 1,\ldots,m, \\<br /> &b_i = l_i + i \textrm{ dla } i = 1,\ldots,m-1.<br /> \end{split}<br /> \]

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

\[<br /> \qquad (4) 0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_{m-1} < b_{m-1} < a_m < n + m.<br /> \]

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

\[<br /> \qquad (3)\begin{split}<br /> &k_i = a_i-i + 1 \textrm{ dla } i = 1,\ldots,m, \\<br /> &l_i = b_i - i \textrm{ dla } i = 1,\ldots,m-1;<br /> \end{split}<br /> \]

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.)

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz