$\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.