Tübitak Lise 2. Aşama 2012 Soru 5

[Lokman Gökçe]

$x_i \in {1,2,\dots,20},(1\leq i\leq 2012)$, biçimindeki tüm $(x_1,x_2,\dots,x_{2012})$ $2012$-lilerinden oluşan kümeyi $P$ ile gösterelim.
Bir $S \subset P$ altkümesi, her $(x_1,x_2,\dots,x_{2012}) \in S$ için, $$y_i \leq x_i (1\leq i\leq 2012) \Rightarrow (y_1,y_2,\dots,y_{2012}) \in S$$
koşulunu sağlıyorsa, $S$ ye alçalan küme $$x_i \leq y_i (1\leq i\leq 2012) \Rightarrow (y_1,y_2,\dots,y_{2012}) \in S$$
koşulunu sağlıyorsa da, $S$ ye yükselen küme diyelim.
$A$ ve $B$ boş olmayan sırasıyla bir alçalan ve bir yükselen küme olmak üzere, $|A \cap B|/\left (|A|\cdot|B| \right )$ nin alabileceği en büyük değeri belirleyiniz.

(Azer Kerimov)

[geo]

Cevap, $\dfrac {1}{20^{2012}}$.

Daha genel halini $K=20$, $n=2012$ değişkenlerini kullanarak ispatlayalım.

$A=P$ veya $B=P$ olduğunda $|A \cap B|/\left (|A|\cdot |B| \right ) = \dfrac {1}{|P|} = \dfrac{1}{K^n}$ oluyor.

Herhangi $A$ alçalan, $B$ yükselen kümeleri için $|A \cap B|/\left (|A|\cdot |B| \right )  \leq \dfrac{1}{K^n}$ olduğunu tümevarımla gösterelim.

$n=1$ için, $A = \{x_1 \colon x_1 \in \mathbb {N},  1 \leq x_1 \leq a_1 \leq K \}$ ve $B = \{x_1 \colon x_1 \in \mathbb {N},  1 \leq b_1 \leq x_1 \leq K\}$ olsun.

İddia: $|A|\cdot |B| \geq K\cdot |A \cap B|$

İspat:
$$\begin{array}{rcl}
|A|\cdot |B| &\geq& K\cdot |A_1 \cap B_1| \\
a_1(K-b_1+1) &\geq& K(a_1-b_1+1) \\
K\cdot a_1 - a_1b_1 + a_1 &\geq& K\cdot a_1 - K\cdot b_1 + K \\
K\cdot b_1 - K - a_1b_1 + a_1 &\geq& 0 \\
(K-a_1)(b_1 - 1) &\geq& 0. \blacksquare
\end{array}$$

$n-1$ için eşitsizlik doğru olsun. Yani $n-1$-lilerden oluşan herhangi $A'$ alçalan ve $B'$ yükselen kümeleri için $|A' \cap B'|/\left (|A'|\cdot |B'| \right )  \leq \dfrac{1}{K^{n-1}}$ olsun.

$(x_1, x_2, \dots, x_n)$ çoklularından oluşan $A$ alçalan kümesini $x_n$ sayısına göre gruplandıralım. $A_i$ ile $x_n=i$ olan grubun son elemanın atılmasıyla oluşan $n-1$-liler kümesini gösterelim.
Öncelikle $|A| = \sum \limits_{i=1}^{K} | A_i |$ ve her $A_i$ nin alçalan olduğunu fark edelim.
$A_{i+1}$ in bir elemanı $(x_1, x_2, \dots, x_{n-1})$ olsun. $(x_1,x_2, \dots, x_{n-1}, i+1) \in A$ ise alçalanlık tanımından $(x_1,x_2, \dots, x_{n-1}, i) \in A$, dolayısıyla $(x_1, x_2, \dots, x_{n-1}) \in A_i$ olacak. Bu durumda $A_1 \supset A_2 \supset \cdots \supset A_K$ olur.

Benzer şekilde, $(x_1, x_2, \dots, x_n)$ çoklularından oluşan $B$ yükselen kümesini $x_n$ sayısına göre gruplandıralım. $B_i$ ile $x_n=i$ olan grubun son elemanın atılmasıyla oluşan $n-1$-liler kümesini gösterelim. Her $B_i$ yükselen ve $|B| = \sum \limits_{i=1}^{K} | B_i |$ olacaktır. Alçalan örneğine benzer şekilde $B_1\subset B_2 \subset \cdots \subset B_K$.

$n-1$-liler için doğru kabul ettiğimiz eşitlikten $$|A \cap B| = \sum\limits_{i=1}^K |A_i \cap B_i| \leq \dfrac{1}{K^{n-1}} \sum \limits_{i=1}^K |A_i|\cdot |B_i| \tag{1}$$ elde edilir.

$|A_1| \geq |A_2| \geq \cdots \geq |A_K|$ ve $|B_1| \leq |B_2| \leq \cdots \leq |B_K|$ olduğu için Chebyshev Eşitsizliğinden $$\sum \limits_{i=1}^K |A_i| \cdot |B_i| \leq \dfrac 1{K} \cdot \left ( \sum \limits_{i=1}^K |A_i| \right ) \cdot \left ( \sum \limits_{i=1}^K |B_i| \right ) = \dfrac 1{K} \cdot |A| \cdot |B| \tag{2}$$ elde ederiz.
$(1)$ ile $(2)$ yi birleştirirsek $$|A \cap B| \leq \dfrac{1}{K^n} \cdot |A| \cdot |B|$$ sonucuna ulaşırız. $\blacksquare$

Kaynak:
Turkish Mathematical Olympiad 2012 Kitapçığı
Kleitman's Lemma