Tübitak Lise 2. Aşama 1991 Soru 2

[Lokman Gökçe]

Her terimi $A= \{1,2,3,4,5,6,7,8 \}$ kümesinin bir alt kümesine eşit olan ve aşağıdaki koşulları sağlayan $B_1,\dots,B_K$ dizisi oluşturuyoruz.

• $i \neq j \Rightarrow B_i \neq B_j$
• Her $i,j\in\{1,\dots, K \}$ için $B_i \cap B_j \neq \emptyset$.

$K$ nın alabileceği en büyük değeri bulunuz.

[Lokman Gökçe]

(Lokman GÖKÇE)

Şöyle basit bir çözüm verebiliriz:

$A$ kümesinin $1$ i içeren alt kümelerinin sayısını bulalım. $\{2,3,4,5,6,7,8 \}$ kümesinin $2^7=128$ tane alt kümesi vardır. Bu alt kümelerin her birinin içine $1$ i eleman olarak eklersek, içinde $1$ olan $128$ farklı alt küme elde etmiş oluruz. Bu kümelerin hangi ikisini alırsak alalım kesişimlerinin boş kümeden farklı olacağı açıktır. Dolayısıyla $K = 128 $ durumuna örnek bulmuş olduk.

Şimdi de daima $K \leq 128$ olacağını gösterelim. $A$ kümesinin $2^8 = 256$ alt kümesi vardır. Herhangi bir $B$ alt kümesini ve $B$ nin tümleyeni olan $ \overline{B} = A - B $ kümesini göz önüne alalım. Bu iki kümenin kesişimi boş küme olduğundan, $B$ ile $ \overline{B} $ kümelerinden en fazla biri $B_1, \dots ,B_K$ dizisinde görülebilir. Örneğin $B = \{1,2,3\} $ kümesi $B_i$ listesindeyse $ \overline{B} = \{4,5,6,7,8\}$ kümesi bu listede bulunmamalıdır. Dolayısıyla $K \leq \dfrac {256}{2}=128$ dir.

Sonuç olarak, $K$ nın en büyük değerinin 128 olabileceğini anlarız.