L OM - I - Zadanie 8

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:

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

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

Komentarze

Dodaj nową odpowiedź