$S_1, S_2,\cdots, S_m$ kumeleri $\{1,2,\cdots,n\}$ kumesinin her $i \ne j$ icin $|S_i \cap S_j| = 1$ sartini saglayan alt kumeleri olsun. $m \leq n$ oldugunu ispatlayiniz.

4 beğenilme 0 beğenilmeme
46 kez görüntülendi

$S_1, S_2,\cdots, S_m$ kumeleri  $\{1,2,\cdots,n\}$ kumesinin her $i \ne j$ icin $|S_i \cap S_j| = 1$  sartini saglayan alt kumeleri olsun. $m \leq n$ oldugunu ispatlayiniz.

10, Aralık, 2015 Lisans Matematik kategorisinde Sercan (22,394 puan) tarafından  soruldu

1 cevap

4 beğenilme 0 beğenilmeme
 
En İyi Cevap
$\def\RR{\mathbb{R}}$
Buyuk ihtimalle daha guzel bir cozum vardir. Ben saatlerdir ugrasiyorum, sonunda cozdum ama cok memnun degilim cunku liselilerin anlayabilecegi bir cozum olmadi. Bir de $S_i$'lerin birbirinden farkli olmasini istiyorsun, yoksa $\{1 \}$ kumesini istedigim kadar tekrar ederim.

Once cozumun adimlarini yaziyim, sonra teker teker her adim hakkinda konusayim.

Adim 1: Her $S_i$ icin $\RR^n$'de bir vektor tanimla.
Adim 2: Bu vektorlerin dogrusal bagimsiz oldugunu goster.

Adim 1: Her $S \subset \{ 1, \ldots, n\}$ icin, $s = (s_1, \ldots, s_n) \in \RR^n$ vektorunu soyle tanimlayalim:  Eger $i \in S$ ise $s_i = 1$ olsun. Aksi taktirde $s_i = 0$ olsun. Ornegin, $\{ 1, 2\}$ altkumesi $(1, 1, 0, \ldots, 0)$ vektoruyle ve $\{1 , 3\}$ altkumesi $(1, 0 , 1, 0, \ldots, 0)$ vektoruyle eslensin. 

Simdi elimizde $S, T$ altkumeleri olsun. Bunlara karsilik gelen $s, t$ vektorlerine, daha dogrusu bunlarin ic carpimlarina bakalim:
$$s \cdot t = s_1t_1 + \ldots +s_nt_n$$ Simdi bizim kosullarimiz altinda, $$i \in S \cap T \iff s_i = t_i = 1 \iff s_it_i =1$$ ve $$i \notin S \cap T \iff s_i t_i = 0$$
O halde, $$s \cdot t = |S \cap T|$$
Ote yandan, $s \cdot s = |S|$. 
Simdi, soruya geri donelim. Elimizde $S_1, \ldots, S_m$ kumeleri var. Bunlar bize $s_1, \ldots, s_m \in \RR^n$ vektorlerini veriyor. Bu vektorlerin ozelligi $s_i \cdot s_j = 1$ olmasi, eger $i \neq j$ ise.

Adim 2: Bu adimda $\{ s_1, \ldots , s_m\}$ kumesinin dogrusal bagimsiz oldugunu gosterecegiz. Yazmasi daha kolay olsun diye $|S_i|$ yerine $a_i$ yazacagim. $$c_1 s_1 + \ldots + c_m s_m = 0$$ olsun. Bu esitligin iki taraftan $s_i$ ile ic carpimini alalim:
$$0 = s_i \cdot ( c_1 s_1 + \ldots + c_ns_n ) = c_1 + \ldots + a_i c_i + \ldots c_m$$ Bunu her $s_i$ icin yaparsak elimizde $m$ bilinmeyenli $m$ denklem var. (Hatirlayalim, amacimiz $c_i$'lerin sifir olmak zorunda oldugunu gostermek.) Bu denklem sistemini matris esitligine donusturelim.

$$\begin{bmatrix} a_1 & 1 & \ldots & 1 \\ 1 & a_2 & \ldots & 1 \\ \vdots & \vdots & \vdots &\vdots \\ 1 & 1 & \ldots & a_m\end{bmatrix} \begin{bmatrix} c_1 \\ \vdots \\ \vdots \\ c_m\end{bmatrix} = 0$$ Simdi amacimiz bu denklemin tek cozumu oldugunu gostermek, yani $m\times m$ matrisimizin tersinin oldugunu gostermemiz soruyu bitirecek. Bunun icin de sunu yaptim:
$$\begin{bmatrix} a_1 & 1 & \ldots & 1 \\ 1 & a_2 & \ldots & 1 \\ \vdots & \vdots & \vdots &\vdots \\ 1 & 1 & \ldots & a_m\end{bmatrix} \rightarrow \begin{bmatrix} a_1 & 1 & \ldots & 1 \\ 0 & a_2a_1 - 1 & \ldots & a_1 - 1 \\ \vdots & \vdots & \vdots &\vdots \\ 0 & a_1 - 1 & \ldots & a_ma_1 - 1\end{bmatrix}$$ Simdi tumevarimla isi bitirebilirim. 
Kucuk bir sey soylemek lazim: Tumevarim kullanmam icin ikinci matristeki $(m-1) \times (m-1)$'lik altmatrisin kosegenindeki girdilerin sifirdan farkli oldugunu soylemem lazim. Ama bunu yapabilirim. Cunku $a_i$'lerin en fazla bir tanesi disinda hepsi $2$ ya da daha buyuk olmali. Eger bunlardan bi tanesi $1$ ise, onu $a_1$ olarak dusuneyim. O zaman $a_1a_i - 1$ sifirdan buyuk olacak $i \neq 1$ icin. Bu da tumevarim kullanabilecegimizi soyluyor.
12, Aralık, 2015 Ozgur (1,968 puan) tarafından  cevaplandı
20, Aralık, 2015 Sercan tarafından seçilmiş

Bu hos cozum bence, dusundugum buna benzerdi. 

Bence de cok hos! Ama baska turlu cozulemez mi?

Dusunmek lazim ama boyle $m \leq n$'li sorular da direk lineer cebir geliyor insanin aklina. Yani baska bir yontem varsa da cok karisik olurmus gibi geliyor isin acikcasi. (benzer olmamak sartiyla tabi).

İbadullah güzel bir soru ve cevabı olmuş.

...