L OM - I - Zadanie 8

Zawody matematyczne:

L OM, 1998-1999

Etap:

Dana jest liczba naturalna $n \geq 2$ oraz zbiór $n$ -elementowy $S$ . Wyznaczyć najmniejszą liczbę naturalną $k$ , dla której istnieją podzbiory $A_1, A_2,\ldots, A_k$ zbioru $S$ o następującej własności:

dla dowolnych dwóch różnych elementów $a, b \in S$ , istnieje taka liczba $j \in \{1, 2,\ldots, k\}$ , że zbiór $A_j \cap \{a, b\}$ jest jednoelementowy.

Rozwiązanie

Wykażemy, że $k = [\log_2(n-1) +1]$ , tzn. $2^{k-1} <n\leq 2^k$ .

Mając liczbę $k$ określoną jak wyżej, konstruujemy zbiory $A_j$ następująco: numerujemy elementy zbioru $S$ liczbami $k$ -cyfrowymi w układzie dwójkowym (dopuszczamy zera początkowe). Mamy więc do dyspozycji $2^k\geq n$ liczb. Następnie za $A_i$ bierzemy zbiór tych elementów zbioru $S$ , których numer ma na $i$ -tym miejscu jedynkę. Dowolne różne elementy $a$ i $b$ zbioru $S$ mają wówczas przypisane różne numery, które różnią się, powiedzmy, na $j$ -tym miejscu. Wtedy do zbioru $A_j$ należy dokładnie jeden z elementów $a$ , $b$ .

Tak znaleziona liczba $k$ jest najmniejsza. Załóżmy bowiem, że istnieją zbiory $A_1,A_2,\ldots,A_k$ spełniające warunki zadania dla $2^k <n$ . Każdemu elementowi $x$ zbioru $S$ przypisujemy układ $k$ liczb $(c_1,c_2,\ldots,c_k)$ według następującej zasady:

$ c_i=\left\{\begin{array}{lll} 0&\textrm{gdy}&x\notin A_i\\ 1&\textrm{gdy}&x\in A_i\\ \end{array}\right. (i=1,2,\ldots,k). $

Ponieważ $2^k < n$ , więc istnieją takie dwa różne elementy $a,b \in S$ , które mają przypisany ten sam układ liczb. To zaś oznacza, że element $a$ należy do dokładnie tych samych zbiorów spośród $A_1,A_2,\ldots,A_k$ , co element $b$ .