Komentarz

XLV OM - III - Zadanie 3

Dana jest liczba całkowita $ c \geq 1 $. Każdemu podzbiorowi $ A $ zbioru $ \{1,2, \ldots ,n\} $ przyporządkowujemy liczbę $ w(A) $ ze zbioru $ \{1,2, \ldots ,c\} $ tak, by był spełniony następujący warunek:

\[<br /> w(A \cap B) = \min(w(A),w(B)) \quad \text{ dla } A, B \subset \{1,2, \ldots , n\}.<br /> \]

Niech $ a(n) $ będzie liczbą takich przyporządkowań. Obliczyć $ \lim_{n\to \infty}\sqrt[n]{a(n)} $.

Uwaga: $ \min(x,y) $ jest nie większą z liczb $ x $, $ y $.

Rozwiązanie

Oznaczmy przez $ M $ zbiór $ \{1,2,\ldots,n\} $, a przez $ M_i $ - zbiór $ (n-1) $-elementowy, powstały ze zbioru $ M $ przez usunięcie liczby $ i $:

\[<br /> M_1 = \{2,3, \ldots ,n\}, \quad M_2 = \{1,3, \ldots ,n\},\quad \ldots ,\quad M_n = \{1,2, \ldots ,n-1\}.<br /> \]

Niech będzie dane przyporządkowanie, o jakim mowa w zadaniu. Oznaczmy wartość $ w(M) $ przez $ m $, a wartość $ w(M_i) $ - przez $ f(i) $ (dla $ i = 1,2, \ldots ,n $). W myśl warunków zadania, wartości $ f(1), \ldots ,f(n) $ oraz $ m $ są liczbami ze zbioru $ \{1,2, \ldots ,c\} $, a ponadto dla każdego $ i $ ma miejsce równość

\[<br /> f(i) = w(M_i) = m(M \cap M_i) = \min (w(M),w(M_i)) = \min (m,f(i)),<br /> \]

która jest po prostu wymyślnym sposobem zapisu nierówności

\[<br /> f(i) \leq m \quad \textrm{dla} \ i = 1,2,\ldots,n.<br /> \]

Tak więc z przyporządkowaniem $ w(\cdot) $ została skojarzona funkcja

\[<br /> (1) \qquad f:M \to \{1,2, \ldots ,m\}, \quad \textrm{gdzie } m = w(M).<br /> \]

Z nałożonego na przyporządkowanie $ w(\cdot) $ warunku

\[<br /> w(A \cap B) = \min(w(A),w(B)) \quad \textrm{dla } A,B \subset \{1,2,\ldots,n\}<br /> \]

wynika przez indukcję równość

\[<br /> (2) \qquad w(A_1 \cap \ldots \cap A_k) = \min (w( A_1), \ldots , w(A_k))<br /> \]

dla dowolnych zbiorów $ A_1,\ldots,A_k $ zawartych w $ M $. (Symbol $ \min(x_1,\ldots,x_k) $ oznacza najmniejszą z liczb $ x_1,\ldots,x_k $; może to być oczywiście wspólna wartość kilku tych liczb.)

Niech $ A $ będzie dowolnym podzbiorem zbioru $ M $, nie identycznym z całym zbiorem $ M $, i niech $ i_1,\ldots,i_k $ będą wszystkimi liczbami z $ M $, które {\it nie należą} do $ A $:

\[<br /> (3) \qquad M \setminus A = \{i_1,\ldots,i_k\}.<br /> \]

Zbiór $ A $ jest wówczas dokładnie częścią wspólną zbiorów $ M_{i_1},\ldots,M_{i_k} $:

\[<br /> (4) \qquad A = M_{i_1} \cap \ldots \cap M_{i_k}.<br /> \]

Istotnie: liczba $ i $ należy jednocześnie do wszystkich zbiorów $ M_{i_1},\ldots,M_{i_k} $ wtedy i tylko wtedy, gdy należy do $ M $ i jest różna od liczb $ i_1,\ldots,i_k $ - a więc (zgodnie z (3)) wtedy i tylko wtedy, gdy jest elementem zbioru $ A $.

Ze związków (4), (2), (3) wynika równość

\[<br /> w(A) = \min(w(M_{i_1}),\ldots,w(M_{i_k})) = \min(f(i_1),\ldots,f(i_k)) = \min_{i \not \in A}f(i).<br /> \]

(Symbol $ \min_{i \not \in A}f(i) $ oznacza minimalną wartość przyjmowaną przez funkcję $ f $ na tych elementach zbioru $ M $, które nie należą do zbioru $ A $.)

Wniosek: przyporządkowanie $ w(\cdot) $ jest w pełni wyznaczone przez zadanie wartości $ m = w(M) $ oraz wartości $ f(i) = w(M_i) $ dla $ i = 1,2,\ldots ,n $. Innymi słowy, jest wyznaczone przez wybór liczby $ m $ oraz funkcji (1); jest wówczas dane wzorem

\[<br /> (5) \qquad w(A) = \left\{<br /> \begin{array}{rl}\displaystyle<br /> \min_{i \not \in A}f(i)& \textrm{dla } A \subset M,\ A \neq M,\\<br /> m& \textrm{dla } A=M.<br /> \end{array} \right.<br /> \]

I na odwrót: jeśli $ m $ jest dowolną liczbą całkowitą dodatnią, nie przekraczającą $ c $, oraz jeśli $ f $ jest dowolnym odwzorowaniem zbioru $ M $ w zbiór $ \{1,2,\ldots,m\} $, to wzór (5) definiuje przyporządkowanie $ A \mapsto w(A) $ spełniające postawiony w zadaniu warunek.

Dla ustalonego $ m $ istnieje dokładnie $ m^n $ funkcji (1). Wobec tego liczba dopuszczalnych przyporządkowań (5) wynosi

\[<br /> a(n) = \sum_{m=1}^c m^n = 1+2^n + \ldots + c^n.<br /> \]

Otrzymujemy dwustronne oszacowanie $ c^n \leq a(n) \leq c^n \cdot c $; a stąd

\[<br /> (6) \qquad c \leq \sqrt[n]{a(n)} \leq c \cdot \sqrt[n]{c}.<br /> \]

Gdy $ n $ dąży do nieskończoności, pierwiastek stopnia $ n $ z dowolnie ustalonej liczby dodatniej dąży do $ 1 $. W takim razie wyrażenie po prawej stronie nierówności (6) dąży do $ c $ i na mocy twierdzenia o trzech ciągach $ \displaystyle \lim_{n \to \infty} \sqrt[n]{a(n)} = c $.

Mamy odpowiedź: Szukaną wartością graniczną jest liczba $ c $.

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

Dodaj komentarz