Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: MATSEVER 27 - Ocak 03, 2016, 07:20:09 ös
-
$n \ge 2$ olmak üzere $A=$$\{1,2,...,n \}$ olsun. $S_1,S_2,...,S_m$ kümeleri $A$ kümesinin farklı öyle altkümeleridir ki $\forall$ $1 \le i < j \le m$ için $|S_i \cap S_j|=1$ şartını sağlar. Buna göre $ m \le n$ olduğunu gösteriniz.
-
Öncelikle eşitlik durumunun sağlanabileceğini gösterelim. $S_1=\{ 1\}, S_2=\{ 1,2 \}, \ldots ,S_n=\{ 1,n\}$ durumu $m=n$ için örnektir. Şimdi biraz analitik bir çözüm yapacağız ancak farklı bir çözümü de bulunabilir. $i=1,2, \ldots ,n$ için $S_i$ kümeleri bu şartı sağlayan kümeler olsun. Her $S_j$ için $n$ boyutlu $v^j= \{a_1^j,a_2^j, \ldots ,a_n^j \}$ uzayı tanımlayalım. Öyle ki $a_i^j$ için $i \in S_j$ ise $1$ $i \in S_j$ değilse $0$ işlemi tanımlı olsun. $S_i$ nin eleman sayısı $|S_i|$ olsun.
$$\sum_{i=2}^m \alpha_i v^i = v^1 \ldots(1)$$
olduğunu varsayalım. Bir $j \neq 1$ indisi alalım. $(1)$ in her tarafını $v^j$ ile skaler olarak çarpalım.
$$1=\sum_{i=1,2,\ldots,m ; i \neq j} \alpha_i+\alpha_j|S_j|=\sum_{i=2} \alpha_i+\alpha_j|S_j|-\alpha_j \ldots(2)$$
bulunur. $(1)$ in her tarafını skaler olarak $v^1$ le çarpalım.
$$\sum_{i=2} \alpha_i=|S_1| \ldots(3)$$
elde edilir. $(2)$ ve $(3)$ ten dolayı $1=\alpha_j|S_j-1|+|S_1|$ elde ederiz. $|S_j|=1$ ise $m \le n$ olmak zorundadır. Diğer durumda $0 \ge \alpha_j$ olur. Bu da her $j \neq 1$ için $(1)$ le çelişiyor. O halde $m \le n$ olduğu kanıtlanmış olur.