NOT: Her bir sorunun en az bir kız ve en az bir erkek tarafından çözüldüğünü varsayalım. Aksi halde bu soruları silelim. Sildiğimiz sorular kızlarla erkeklerin ortaklaşa çözdüğü sorulardan olmadığı için aradığımız soru değil. Bu durumda yarışmacılar hala en fazla altı soru çözmüş olacaklar. Aşağıda bir soru kümesinden bahsederken sadece en az bir kız ve bir erkek tarafından çözülen soruları ele alıyor olacağız.
$G$ ile kızların kümesini, $B$ ile erkeklerin kümesini, $P$ ile soruların kümesini, $P(g)$ ile $g \in G$ kızının çözdüğü soruların kümesini, $P(b)$ ile $b \in B$ erkeğinin çözdüğü soruların kümesini, $G(p)$ ile $p \in P$ sorusunu çözen kızların kümesini, $B(p)$ ile $p \in P$ sorusunu çözen erkeklerin kümesini gösterelim.
Soruda verilenleri küme sembolleri ile gösterelim:
$$|G| = |B| = 21$$ $$| P(g) | \leq 6, | P(b) | \leq 6$$ $$P(g) \cap P(b) \neq \emptyset$$
Bizden istenen $|G(p)| \geq 3$ ve $|B(p)| \geq 3$ şartlarını sağlayan en az bir $p \in P$ sorusunun varlığını göstermemiz.
Hiçbir $p \in P$ sorusu için hem $|G(p)| \geq 3$ hem de $|B(p)| \geq 3$ ün birlikte sağlanmadığını varsayacağız. Sonunda bir çelişki elde edeceğiz. Bu da en az bir $p \in P$ sorusu için hem $|G(p)| \geq 3$ hem de $|B(p)| \geq 3$ ün birlikte sağlandığı anlamına gelecek.
Soru, kız ve erkek üçlülerini $(p,g,b)$ ile gösterelim. Bu üçlülerin kümesi $T = \{(p,g,b)\ :\ p \in P(g) \cap P(b) \}$ olsun. Her $(g,b)$ çifti en az bir soruyu ortaklaşa çözdüğü için en az $(g,b)$ çifti sayısı kadar $(p,g,b)$ üçlüsü vardır. Daha resmi bir dille $$|T| = \sum\limits_{g \in G}\sum\limits_{b \in B} | P(g) \cap P(b) | \geq |G|\cdot|B| = 21^2 = 441 \tag {1}$$
Benzer şekilde $T$ nin elemanları $$|T| = \sum\limits_{p \in P} |G(p)| \cdot |B(p)|$$ şeklinde de sayılabilir.
$P$ kümesini iki ayrık kümeye ayıralım: $P_+ = \{p \in P : |G(p)| \geq 3\}$ ve $P_- = \{p \in P : |G(p)| \leq 2\}$
Yani bir soru $2$ den fazla kız tarafından çözüldüyse $P_+$ kümesine ait, $3$ ten az kız tarafından çözüldüyse $P_-$ kümesine ait olacak.
$$\begin{array}{lcl}
|T| &=& \sum\limits_{p \in P} |G(p)| \cdot |B(p)| \\
&=& \sum\limits_{p \in P_+} |G(p)| \cdot |B(p)| + \sum\limits_{p \in P_-} |G(p)| \cdot |B(p)|
\end{array}$$
Varsayımımız üzerine, $p \in P_+$ sorusu için $|B(p)| \leq 2$ olmalı. $P_-$ kümesinin tanımı gereği de $p \in P_-$ sorusu için $|G(p)| \leq 2$. Bu değerleri yukarıdaki ifade de tekrar yazarsak
$$\begin{array}{lcl}
|T| &=& \sum\limits_{p \in P_+} |G(p)| \cdot |B(p)| + \sum\limits_{p \in P_-} |G(p)| \cdot |B(p)| \\
& \leq & \sum\limits_{p \in P_+} |G(p)| \cdot 2 + \sum\limits_{p \in P_-} 2 \cdot |B(p)| \\
& = & 2 \sum\limits_{p \in P_+} |G(p)| + 2\sum\limits_{p \in P_-}|B(p)|
\end{array} \tag{2}$$
Her kız en fazla $6$ soru çözdüğü için $(p,g)$ çiftlerinin sayısı $$\sum\limits_{p\in P} |G(p)| \leq 6|G| \tag {3}$$
$g$ kızı en fazla $6$ soru çözdüğü için, $b_1, b_2, \dots ,b_{21} \in B$ erkekleri ile çözdüğü sorulardan en az birini $\lceil 21/6\rceil = 4$ erkekle birlikte çözmüştür. Bu soruya $p$ dersek $|B(p)| \geq 4$ olacaktır. Bu durumda $p \in P_-$ olmalı.
Bu da her $g$ kızının $p \in P_-$ olan en az bir soru çözdüğü gösterir. O halde $$\sum\limits_{p \in P_-} |G(p)| \geq |G| \tag{4}$$
$(3)$ ile $(4)$ ü birleştirsek $$\sum\limits_{p \in P_+} |G(p)| \leq 5|G| \tag{5}$$
Her erkek en fazla $6$ soru çözdüğü için $(p,b)$ çiftlerinin sayısı $$\sum\limits_{p\in P} |B(p)| \leq 6|B| \tag {6}$$
Benzer şekilde her $b$ erkeği $\lceil 21/6\rceil = 4$ kızla birlikte bir soru çözmüştür. Bu soru için $|G(p)| \geq 4$ olduğu için bu soru $P_+$ kümesine aittir. Bu da her $b$ erkeğinin $p \in P_+$ olan en az bir soru çözdüğünü gösterir. O halde $$\sum\limits_{p \in P_+} |B(p)| \geq |B| \tag{7}$$
$(6)$ ile $(7)$ yı birleştirsek $$\sum\limits_{p \in P_-} |B(p)| \leq 5|B| \tag{8}$$
$(5)$ ve $( 8 )$ deki bulgularımızı $(2)$ de yerine yazarsak
$$\begin{array}{lcl}
|T| & \leq & 2 \sum\limits_{p \in P_+} |G(p)| + 2\sum\limits_{p \in P_-}|B(p)| \\
& \leq & 2\cdot 5 \cdot |G| + 2\cdot 5 \cdot |B| \\
& = & 420
\end{array} \tag{9}$$
$(1)$ ve $(9)$ çeliştiği için varsayımımız yanlıştır. Dolasıyla en az bir $p$ için $|G(p)| \geq 3$ ve $|B(p)| \geq 3$ tür.
Kaynak:
IMO Shortlist 2001
