XLV OM - III - Zadanie 3

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

III

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:

$ w(A \cap B) = \min(w(A),w(B)) \quad \text{ dla } A, B \subset \{1,2, \ldots , n\}. $

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$ :

$ M_1 = \{2,3, \ldots ,n\}, \quad M_2 = \{1,3, \ldots ,n\},\quad \ldots ,\quad M_n = \{1,2, \ldots ,n-1\}. $

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ść

$ f(i) = w(M_i) = m(M \cap M_i) = \min (w(M),w(M_i)) = \min (m,f(i)), $

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

$ f(i) \leq m \quad \textrm{dla} \ i = 1,2,\ldots,n. $

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

$ (1) \qquad f:M \to \{1,2, \ldots ,m\}, \quad \textrm{gdzie } m = w(M). $

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

$ w(A \cap B) = \min(w(A),w(B)) \quad \textrm{dla } A,B \subset \{1,2,\ldots,n\} $

wynika przez indukcję równość

$ (2) \qquad w(A_1 \cap \ldots \cap A_k) = \min (w( A_1), \ldots , w(A_k)) $

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$ :

$ (3) \qquad M \setminus A = \{i_1,\ldots,i_k\}. $

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

$ (4) \qquad A = M_{i_1} \cap \ldots \cap M_{i_k}. $

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ść

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

(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

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

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

$ a(n) = \sum_{m=1}^c m^n = 1+2^n + \ldots + c^n. $

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

$ (6) \qquad c \leq \sqrt[n]{a(n)} \leq c \cdot \sqrt[n]{c}. $

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