Tanım: $$h(x,y) =
\begin{cases}
1, & f(x,y) = g(x,y) \\
0, & f(x,y) \neq g(x,y) \\
\end{cases}$$
olsun.
$x_i$ sayısı verildiğinde, $y$ bilinmeyeni için $h(x_i,y) = 1$ denkleminin çözüm kümesi $S_i$ olsun.
$x_1, x_2, \dots, x_{2000}$ dizisi; $\{1,2,\dots, 2000\}$ kümesinin $$2000\geq |S_1| \geq |S_2| \geq \cdots \geq |S_{2000}| \geq 0$$ şeklinde bir permütasyonu olsun.
Gözlem:$$\left |\bigcap_{i=1}^{1000}S_i \right | \geq 1000$$ olduğunda, $\bigcap\limits_{i=1}^{1000}S_i$ kümesinin herhangi $1000$ elemanı, $y_1, y_2, \dots, y_{1000}$ olsun.
$X=\{x_{1001}, x_{1002}, \dots, x_{2000}\}$ ve $Y=\{y_{1001}, y_{1002}, \dots, y_{2000}\}$ olarak seçildiğinde, $x \not\in X$ ve $y\not\in Y$ iken, yani $x \in \{x_1, x_2, \dots, x_{10000}\}$ ve $y\in \{y_1, y_2, \dots, y_{1000}\}$ iken, $1 \leq i,j\leq 1000$ olmak üzere; her $(x_i, y_i)$ çifti için $h(x_i, y_i) = 1$ olacağı tanımda belirtilmişti.
Demek ki, $\left |\bigcap\limits_{i=1}^{1000}S_i \right | \geq 1000$ olduğunda, her $h(x,y)$ için, her biri $1000$ er elemanlı $X,Y \subset \{1,2,\dots, 2000\}$ kümeleri bulunabiliyor.
İddia 1:$n=3000$ olduğunda, herhangi bir $h(x,y)$ için bahsedilen şekilde $X$ ve $Y$ kümeleri bulunabilir.
İspat:$S'_i = \{1,2,\dots, 2000\} - S_i$ olsun.
Tanım gereği, $$2000\geq |S_1| \geq |S_2| \geq \cdots \geq |S_{2000}| \geq 0$$ olduğu için, $$0\leq |S'_1| \leq |S'_2| \leq \cdots \leq |S'_{2000}| \leq 2000$$ olacaktır.
$y\in S'_i$ ise $h(x_i, y) = 0$ olacağı tanımda verilmişti. Bu durumda $h(x,y) = 0$ olan ikililerin sayısı $n=3000$ olduğu için, $$\sum_{i=1}^{2000}|S'_i| \leq n=3000$$ dir. $|S'_{1000}| > 2$ olsaydı, $$n=3000 \geq \sum_{i=1}^{999}|S'_i| + \sum_{i=1000}^{2000}|S'_i| \geq \sum_{i=1}^{999}|S'_i| + 3 \cdot 1001 \geq 3003$$ olacaktı. Demek ki, $|S'_{1000}| \leq 2$.
$|S'_{1000}|=2$ olduğunda, $$n=3000 = \sum_{i=1}^{1000}|S'_i| + \sum_{i=1001}^{2000}|S'_i| \geq \sum_{i=1}^{1000}|S'_i| + 2 \cdot 1000 \Rightarrow \sum_{i=1}^{1000}|S'_i| \leq 1000$$ olacaktır. $|S'_{1000}|<2$ olduğunda, $0\leq |S'_i| \leq |S'_2| \leq \cdot \leq |S'_{1000}| \leq 1$ olduğu için, yine $$\sum_{i=1}^{1000}|S'_i| \leq 1000$$ olacaktır.
Her iki durumda da $\sum\limits_{i=1}^{1000}|S'_i| \leq 1000$ olduğu için, $\bigcup\limits_{i=1}^{1000}|S'_i|$ kümesi en fazla $1000$ elemanlı olabilir. Diğer bir deyişle, $\bigcup\limits_{i=1}^{1000}|S'_i|$ kümesinin elemanı olmayan en az $1000$ tane $a_k\in{1,2,\dots2000}$ elemanı bulunabilir. $a_k$ elemanı $\bigcup\limits_{i=1}^{1000}|S'_i|$ kümesinin dışında olduğu için, $a_k \not \in S'_i$, yani $a_k \in S_i$ dir. Demek oluyor ki, bu en az $1000$ eleman $S_1,S_2,\dots,S_{1000} $ kümelerinin hepsi tarafından içeriliyor. Yani $$\left |\bigcap\limits_{i=1}^{1000} S_i \right |\geq 1000$$ dir. Bu şart sağlandığında, her $h(x,y)$ için, her biri $1000$ er elemanlı $X,Y \subset \{1,2,\dots,2000\}$ kümeleri bulunabildiğini gözlem bölümünde göstermiştik. $\blacksquare$
İddia 2:$3001$ $(x,y)$ çifti için $0$ değeri alan aşağıdaki $h(x,y)$ fonksiyonu için, bahsedilen şekilde $X$ ve $Y$ kümelerini bulmak mümkün değildir.
Her $a \in \{1,2,\dots,2000\}$ için $h(a,a)=0$,
$h(1,2)=h(2,3)=\cdots=h(1000,1001)=h(1001,1)=0$,
aksi takdirde $h(x,y)=1$.
İspat:$X$ ve $Y$ kümelerinin bulunabildiğini varsayalım.
$X'=\{1,2,\dots,2000\}-X$ ve $Y'=\{1,2,\dots,2000\}-Y$ olsun. $|X'|=|Y'|=1000$ dir.
Herhangi $a \in \{1,2,\dots,2000\}$ sayısı için, $a \in X'$ ise, $a \in Y'$ olmak zorunda. Aksi takdirde, $a\in X'$ ve $a\in Y'$ iken $h(a,a)=1$ olması gerekecek ki, bu da $h(x,y)$ fonksiyonunun tanımına aykırı.
Demek ki $X'$ ve $Y'$ kümeleri ayrık. $|X'|=|Y'|=1000$ olduğu için de $X'\in Y'=\{1,2,\dots,2000\}$ dir.
$1\in X'$ olduğunu varsayalım. $h(1,2)=0$ olduğu için, $2\not \in Y'$ olmalı. Bu durumda $2 \in X'$ dür.
Bunu böyle devam ettirirsek, $1000 \in X' \Rightarrow 1001 \not \in Y' \Rightarrow 1001 \in X'$ elde edilir. Halbu ki, $|X'|=1000$ elemanlı, $1001$ elemanlı değil.
Benzer şekilde, $1\in Y'$ olduğunu varsayalım. $h(1001,1)=0$ olduğu için, $1001 \not \in X'$ olmalı. Bu durumda $1001 \in Y'$ dür.
Bunu böyle devam ettirirsek, $3 \in Y' \Rightarrow 2 \not \in X' \Rightarrow 2 \in Y'$ elde edilir. Halbu ki, $|Y'|=1000$ elemanlı, $1001$ elemanlı değil.
Demek ki, $n=3001$ olduğunda, soruda bahsedilen şekilde $X$ ve $Y$ kümeleri bulmak her zaman mümkün olmayabiliyor. $\blacksquare$
Sonuç:$n$ tam sayısı en çok $3000$ olabilir. $\blacksquare$
Not:Bu soru aşağıdaki soruyla özdeştir.
$2m\times 2m$ bir matrisin $n$ elemanı $0$, diğerleri $1$ dir. Bu şekilde herhangi bir matrisin tam olarak $m$ satırını ve $m$ sütununu sildiğimizde tüm elemanları $1$ olan $m\times m$ bir matris elde edilebiliyorsa, $n$ nin alabileceği en büyük değerin $3m$ olduğunu gösteriniz.
Bu problemin genel hali literatürde
Zarankiewicz problemi olarak geçiyor. Bizim sorumuzdaki özel hali için
On the Half-Half Case of the Zarankiewicz Problem makalesine müracaat edebilirsiniz.
