Tübitak Lise 1. Aşama 2006 Soru 32

[ERhan ERdoğan]

"$\left \{1, 2, \cdots , 9 \right \}$ kümesinin $5$ elemanlı hangi $6$ altkümesini alırsak alalım, bunlardan en az bir ortak elemana sahip $k$ tanesi bulunur" önermesinin doğru olmasını sağlayan en büyük $k$ tam sayısı nedir?

$
\textbf{a)}\ 1
\qquad\textbf{b)}\ 2
\qquad\textbf{c)}\ 3
\qquad\textbf{d)}\ 4
\qquad\textbf{e)}\ 5
$

[kombinatorist]

Yanıt: $\boxed{D}$

$5 \cdot 6=30$ eleman bulunur. Güvercin yuvası prensibine göre, $30:9>3$ olduğu için $k$ nın en büyük değeri $4$ olur.

[Lokman Gökçe]

Yanıt: $\boxed{D}$

$k=5$ tane alt küme için istenen koşulun gerçekleşmeyebileceğini gösterelim.

$\{2,3,4,5,6\}$, $\{1,3,4,5,6\}$, $\{1,2,4,5,6\}$, $\{1,2,3,5,6\}$, $\{1,2,3,4,6\}$, $\{1,2,3,4,5\}$ alt kümelerinden herhangi beşinin kesişimi boş kümedir. $k<5$ olmalıdır. $k_{\max} = 4$ olduğunu, önceki çözümde gösterildiği gibi kanıtlayabiliriz. $5$ elemanlı $6$ alt kümede toplam $6\cdot 5 = 30$ eleman vardır. Güvercin yuvası prensibi gereğince, en az $\left\lceil \dfrac{30}{9} \right\rceil = 4$ eleman aynı olmalıdır. Bu da kesişimi boş küme olmayan $4$ farklı alt kümenin seçilebileceğini gösterir.