Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 1998 => Konuyu başlatan: geo - Nisan 26, 2014, 04:12:55 ös
-
$10$ elemanlı bir kümenin, hiçbiri bir diğerinin altkümesi olmayacak şekilde en çok kaç altkümesi bulunur?
$
\textbf{a)}\ 126
\qquad\textbf{b)}\ 210
\qquad\textbf{c)}\ 252
\qquad\textbf{d)}\ 420
\qquad\textbf{e)}\ 1024
$
-
Yanıt: $\boxed{C}$
Test mantığı ile hareket edeceğiz. Eksik çözüm yapıp, en azından soruyu belirli bir aşamaya getireceğiz.
$$\binom{10}{0} = \binom{10}{10} < \binom{10}{1} = \binom{10}{9} < \binom{10}{2} = \binom{10}{8} < \binom{10}{3} = \binom{10}{7} < \binom{10}{4} = \binom{10}{6} < \binom{10}{5} = 252$$
Görüldüğü gibi $k$-elemanlı altkümelerin sayısı en büyük değerini $k=5$ olduğunda alıyor. $k$-elemanlı altkümelerden hiçbiri bir diğerini içermez, içerseydi altkümelerin ikisi de $k$ elemanlı olduğu için altkümeler aynı olurdu.
Ya bazısı $3$-elemanlı, bazısı $4$-elemanlı, bazısı $5$-elemanlı, bazısı da $6$-elemanlı altkümelerin birleşimden elde edilen altküme kümesi daha çok elemanlı ise? Buna karar vermek test içinde o kadar kolay değil. En azından, bu çözüm için bu iddianın doğru olmadığını ispatlamayacağız. Önsezilerimizle, $C$ şıkkını işaretleyeceğiz.
-
Çözüm 1'in aksine burada matematiksel bir çözüm yapalım. Açıkçası söz konusu problem bir Kombinatorik konusu olan Sperner Teoremi'ni doğrudan soruyor. Biraz da bu teoremin ispatını bilerek bir çözüm yapacağız. Böyle bir çözümün bir test süresinde düşünülüp yapılmasını çok mümkün görmüyoruz. Yine de;
$S$ ile birbirinin altkümesi olmayan kümeleri içeren bir kümeyi gösterelim.
En basit mantığıyla, $S = \{ \{1\}, \{2\}, \{3\}, \dots \{10\} \}$ bu şekilde bir küme olacak. $S_i$ ile $S$ kümesinin $i$ elemanlı kümelerden oluşan elemanları içeren kümeyi gösterelim. Buna göre yukarıda verdiğimiz basit örnek için $|S_5|=0$ iken $|S_1|=10$ dur.
$S = \{x: |x|=5 \land x \subset \{1,2, \dots , 10\} \}$ şeklinde bir $S$ kümesi alalım. $|S|=\binom{10}{5} = 252$ ve $S$'deki elemanlardan hiçbiri bir diğerinin altkümesi değil. Bu durumda örneğin $|S_0| = |S_3| = |S_9| = 0$ iken $|S_5|=252$ dir.
Bu tanımlamaları yaptıktan sonra, asıl sorunun çözümüne gelelim.
$S$ içerisinden $k$ elemanlı bir eleman alıp (unutmayalım, $S$ nin elemanları birer kümeydi!), Bu elemanları $k!$ şekilde sıralayalım. Sonra da $\{1,2,\dots, 10\}$ kümesinin kullanmadığımız $10-k$ elamanını $(10-k)!$ şekilde sıralayalım. $k$ elemanlı elemanların kümesi $S_k$ olacağından toplamda $|S_k|\cdot k! \cdot (10-k)!$ şekilde $(1,2,\dots 10)$ sayılarının bir permütasyonunu elde etmiş olduk.
Son yaptığımızı her $0\leq k \leq 10$ sayısı için yaparsak toplamda $$\displaystyle\sum_{k=0}^{10} |S_k|\cdot k! \cdot (10-k)!$$
permütasyon elde ederiz. Toplamda elde ettiğimiz bu permüstasyonlar arasında aynı permütasyonlar var mı? Yoksa bu permütasyon sayısı $$\displaystyle\sum_{k=0}^{10} |S_k|\cdot k! \cdot (10-k)! \leq 10!$$ olmalı; çünkü $10$ elemanlı bir kümenin $10!$ permütasyonu vardır. Toplamda elde ettiğimiz permütasyonlar arasında aynı olanlar varsa, o zaman dükkanı kapatma vakti gelmiş. Çünkü yapacak bir şeyimiz kalmadı demektir. Dua edelim, böyle bir şey olmasın.
$S$ nin herhangi iki elemanını ele alalım. Bunlardan biri $x$ elemanlı $X$, diğeri $y$ elemanlı $Y$ olsun; genellemeyi bozmadan $x \leq y$ kabul edelim. $X$ i kullanarak yukarıda anlatıldığı gibi $10$ elemanlı bir permütasyon üretelim. Sonra da $Y$ yi kullaranak bir permütasyon üretelim. Bu iki permütasyonun ilk $x$ basamağına bakalım. $X \not\subset Y $ olduğu için, bu basamaklar aynı olamaz. Bu durumda üretilen tüm permütasyonlar farklı, bunların toplam sayısı da $10!$ den küçük ya da $10!$ e eşittir. Biraz düzenleme yaparsak:
$$\displaystyle\sum_{k=0}^{10} |S_k|\cdot k! \cdot (10-k)! \leq 10! \Rightarrow \displaystyle\sum_{k=0}^{10} {\dfrac{|S_k|}{\dfrac{10!}{k! \cdot (10-k)!}}} \leq 1 \Rightarrow \displaystyle\sum_{k=0}^{10} \dfrac{|S_k|}{{10 \choose k}} \leq 1 $$ elde ederiz. Şimdi de $${10 \choose k} \leq {10 \choose 5} \Rightarrow \dfrac{|S_k|}{{10 \choose 5}} \leq \dfrac{|S_k|}{{10 \choose k}}$$ özdeşliğini kullanarak
$$\displaystyle\sum_{k=0}^{10} \dfrac{|S_k|}{{10 \choose 5}} \leq \displaystyle\sum_{k=0}^{10} \dfrac{|S_k|}{{10 \choose k}} \leq 1 $$ ve $$\dfrac 1{{10 \choose 5}} \cdot \displaystyle\sum_{k=0}^{10} |S_k| \leq 1 \Rightarrow \displaystyle\sum_{k=0}^{10} |S_k| = |S| \leq {10 \choose 5}$$ elde ederiz. Son eşitsizlik bize hiçbiri bir diğerinin altkümesi olmayan kümelerin toplam sayısının en fazla ${10 \choose 5}$ olacağını söylüyor. Anlaşılır kılmak için, biraz uzattık; yoksa internetteki kaynaklarda sadece yukarıdaki cebirsel ifadeler verilerek ispat yapılıyor.
-
İlk çözümdeki, daha doğrusu eksik çözümdeki, eksik parçayı tamamlayalım.
En büyük dağılımlardan biri $S$ olsun. Bu altkümelerden en fazla eleman içeren $S_a$ kümesinin eleman sayısı $a$, en az eleman içeren $S_b$ kümesinin eleman sayısı $b$ olsun.
$a \neq b$ olduğunu varsayalım.
$b$ elemanlı $S_b$ altkümesine $a-b$ sayıda eleman ekleyerek $a$ elemanlı $X_{a_i}$ kümelerini elde edelim. $S_b \not \subset S_a$ ve $S_b \subset X_{a_i}$ olduğu için $X_{a_i} \not \subset S_a$ olacaktır. $S_b$ yi dağılımdan çıkarıp $X_{a_i}$ kümelerini dağılıma ekleyelim. Bu durumda yeni dağılımın eleman sayısı $S$ den fazla olacaktır. Bu da $S$ nin en fazla altkümeye sahip olduğu varsayımı ile çelişir. O halde $a=b$, yani $S$ nin tüm elemanları aynı sayıda elemana sahip altkümelerdir.
$k$-elemanlı altkümelerin sayısı en büyük değerini $k = 5$ iken alacağı için aradığımız yanıt, $\binom{10}{5} = 252$ dir.