What does $s(X)$ mean? Is it the sum of the elements of X ?

It means number of elements

There is an official correction for the problem statement. See my next post:

Let $f(x,y)$ and $g(x,y)$ be defined for every $x,y\in \{1,2,\dots, 2000\}$ and take different values for at most $n$ ordered pairs of $(x,y)$. For every function pairs $f(x,y), g(x,y)$, when $x\notin X$ and $y\notin Y$, it is always possible to find $1000-$element sets $X,Y \subset \{1,2,\dots, 2000\}$ such that $f(x,y) = g(x,y)$. Determine the largest integer that $n$ can take.

I asked an analogous version of the problem at http://mathoverflow.net/questions/124232/square-submatrix and http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=524322 According to Mathoverflow, the problem is a special case for Zarankiewicz Problem. A mathlinker ninjaturtle has made a beautiful solution. I have adapted ninjaturtle's solution. Here is: Definition Let $h(x,y)$ be defined such that $f(x,y) = g(x,y) \Rightarrow h(x,y) = 1$. $f(x,y) \neq g(x,y) \Rightarrow h(x,y) = 0$. Let $S_i$ be solution set for given $x_i$ and unknown $y$ such that $h(x_i, y) = 1$. Let $2000 \geq |S_1| \geq |S_2| \geq \dots \geq |S_{2000}| \geq 0$. An Observation Let's make an observation if $|S_1 \cap S_2 \cap \dots \cap S_{1000}| \geq 1000$. Let $y_1, y_2, \dots, y_{1000}$ be any $1000$ elements of $S_1 \cap S_2 \cap \dots \cap S_{1000}$. Choose $X,Y$ such that $X=\{x_{1001}, x_{1002}, \dots, x_{2000}\}$ and $Y=\{y_{1001}, y_{1002}, \dots, y_{2000}\}$. "When $x\notin X$ and $y\notin Y$" means $x\in \{x_1,x_2,\dots, x_{1000}\}$ and $y\in \{y_1, y_2, \dots, y_{1000}\}$. For any such $(x,y)$, $h(x_i, y_j) = 1$ where $1\leq i,j \leq 1000$. So if $|S_1 \cap S_2 \cap \dots \cap S_{1000}| \geq 1000$, it is possible to find the sets $X$ and $Y$. A case that works always Let $n=3000$. Is it always possible to find the sets $X$ and $Y$? Let $S_i' = \{1,2,\dots, 2000\} - S_i$. According to above assumption $2000 \geq |S_1| \geq |S_2| \geq \dots \geq |S_{2000}| \geq 0$, we have $0 \leq |S_1'| \leq |S_2'| \leq \dots \leq |S_{2000}'| $. And $y \in S_i' \Rightarrow h(x_i, y) = 0 \Rightarrow |S'_1| + |S'_2| + \dots + |S'_{2000}| \leq n = 3000$. If $|S_{1000}'| > 2$, then $0 \leq |S_1'| \leq |S_2'| \leq \dots \leq 2 < |S'_{1000}| \leq \dots \leq |S_{2000}'| $. So the sum will be $|S'_{1000}| + |S'_{1001}| + \dots + |S'_{2000}| \geq 3\cdot 1000 + 3 > 3000$. But it shouldn't. So $|S'_{1000}| \leq 2$. In that case $|S'_1| + |S'_2| + \dots + |S'_{1000}| \leq 1000$. So the set $S'_1 \cup S'_2 \cup \dots \cup S'_{1000}$ contains at most $1000$ elements. In other words, there are at least $1000$ elements $a_1, a_2, \dots, a_{1000}$ which are not elements of $S'_1 \cup S'_2 \cup \dots \cup S'_{1000}$. Take one of them: $a_i$. $S_1$ should containt $a_i$ because $a_i \notin S'_1$. So all these $1000$ elements are contained by $S_1, S_2, \dots, S_{1000}$. This means $|S_1 \cap S_2 \cap \dots \cap S_{1000}| \geq 1000$. For that case, we have proved that it is always possible to find the sets $X$ and $Y$. A function which fails Let $n=3001$. Is it always possible to find the sets $X$ and $Y$? Let $h(a,a) = 0$ for all $a \in \{1,2, \dots, 2000\}$. And also $h(1,2) = h(2,3) = h(3,4) = \dots = h(1000, 1001) = h(1001,1) = 0$. So for $2000 + 1001 = 3001$ pairs, $h(x,y) = 0$. Let $X' = \{1,2,\dots, 2000\} - X$ and $Y' = \{1,2,\dots, 2000\} - Y$. We have $|X'|=|Y'|=1000$. If $a \in X'$, $a \notin Y'$. Otherwise $a \in X'$ and $a \in Y'$ implies $h(a,a) = 1$. So $X'$ and $Y'$ are disjoint. And because $|X'|=|Y'|=1000$, $X' \cup Y' = \{1,2,\dots, 2000\}$. Suppose $1 \in X'$. Since $h(1,2) = 0$; $2 \notin Y'$. So $2 \in X'$. If we go further, $1000 \notin Y' \Rightarrow 1000 \in X'$. If $1000 \in X'$, $1001 \notin Y' \Rightarrow 1001 \in X'$. This is not possible because $|X'| = 1000$. Suppose $1 \in Y'$. Since $h(1001, 1) = 0$; $1001 \notin X'$. So $1001 \in Y'$. If we go further, $3 \notin X' \Rightarrow 3 \in Y'$. If $3 \in Y'$, $2 \notin X' \Rightarrow 2 \in Y'$. This is not possible because $|Y'|=1000$. So one could not find such sets $X$ and $Y$ for above $h(x,y)$. Conclusion $n$ can be at most $3000$. $\blacksquare$