Let $\mathbb{Z}_{\geqslant 0}$ be the set of non-negative integers, and let $f: \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \rightarrow \mathbb{Z}_{\geqslant 0}$ be a bijection such that whenever $f\left(x_{1}, y_{1}\right)>f\left(x_{2}, y_{2}\right)$, we have $f\left(x_{1}+1, y_{1}\right)>f\left(x_{2}+1, y_{2}\right)$ and $f\left(x_{1}, y_{1}+1\right)>f\left(x_{2}+1, y_{2}\right)$.  Let $N$ be the number of pairs of integers $(x, y)$, with $0 \leqslant x, y<100$, such that $f(x, y)$ is odd. Find the smallest and largest possible value of $N$.  Answer: The optimal bounds are $2500 \leqslant N \leqslant 7500$.
We defer the constructions to the end of the solution. Instead, we begin by characterizing all such functions \( f \), prove a formula and key property for such functions, and then solve the problem, providing constructions. 

Characterization
Suppose \( f \) satisfies the given relation. The condition can be written more strongly as
\[ \begin{aligned}
f\left(x_{1}, y_{1}\right) > f\left(x_{2}, y_{2}\right) & \Longleftrightarrow f\left(x_{1}+1, y_{1}\right) > f\left(x_{2}+1, y_{2}\right) \\
& \Longleftrightarrow f\left(x_{1}, y_{1}+1\right) > f\left(x_{2}, y_{2}+1\right).
\end{aligned} \]
In particular, this means for any \((k, l) \in \mathbb{Z}^{2}, f(x+k, y+l) - f(x, y)\) has the same sign for all \(x\) and \(y\).

Call a non-zero vector \((k, l) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0}\) a needle if \( f(x+k, y) - f(x, y+l) > 0 \) for all \(x\) and \(y\). It is not hard to see that needles and non-needles are both closed under addition, and thus under scalar division (whenever the quotient lives in \(\mathbb{Z}^{2}\)).

In addition, call a positive rational number \(\frac{k}{l}\) a grade if the vector \((k, l)\) is a needle. (Since needles are closed under scalar multiples and quotients, this is well-defined.)

Claim. Grades are closed upwards.
Proof. Consider positive rationals \(\frac{k_1}{l_1} < \frac{k_2}{l_2}\). We need to show that \(\frac{k_2}{l_2}\) is a grade. Since \(\frac{k_1}{l_1}\) is a grade, \((k_1, l_1)\) is a needle. Thus, \(f(x+k_1, y) - f(x, y+l_1) > 0\) for all \(x\) and \(y\). Since \(\frac{k_1}{l_1} < \frac{k_2}{l_2}\), there exists a positive integer \(n\) such that \(\frac{k_1}{l_1} < \frac{k_2}{l_2} < \frac{k_1 + n}{l_1}\). Therefore, \((k_2, l_2)\) is a needle, as wanted.

Claim. A grade exists.
Proof. If no positive integer \(n\) is a grade, then \(f(1, 0) > f(0, n)\) for all \(n\), which is impossible. Similarly, there is an \(n\) such that \(f(0, 1) > f(n, 0)\). Thus, a grade must exist.

Claim. If \(x_1 + y_1 \alpha > x_2 + y_2 \alpha\) then \(f(x_1, y_1) > f(x_2, y_2)\).
Proof. If both \(x_1 \geq x_2\) and \(y_1 \geq y_2\) this is clear. Suppose \(x_1 \geq x_2\) and \(y_1 < y_2\). Then \(x_1 + y_1 \alpha > x_2 + y_2 \alpha\) implies \(x_1 - x_2 > (y_2 - y_1) \alpha\). Since \(\alpha\) is a grade, \((x_1 - x_2, y_2 - y_1)\) is a needle. This gives \(f(x_1, y_1) > f(x_2, y_2)\). Suppose \(x_1 < x_2\) and \(y_1 \geq y_2\). Then \(x_1 + y_1 \alpha > x_2 + y_2 \alpha\) implies \((y_1 - y_2) \alpha > x_2 - x_1\). Since \(\alpha\) is a grade, \((x_2 - x_1, y_1 - y_2)\) is a needle. This gives \(f(x_1, y_1) > f(x_2, y_2)\).

From this claim, we immediately get that \(2500 \leq N \leq 7500\); now we show that those bounds are indeed sharp.

Remember that if \(\alpha\) is irrational then
\[ f(a, b) = \#\{(x, y) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid x + y \alpha < a + b \alpha\}. \]

Construction for 7500
Select \(\alpha \approx 199.999\).

Claim.
1. \(f(n, 0) = n\) for \(0 \leq n \leq 100\).
2. \(f(0, k) \equiv k \quad \bmod 2\) for \(0 \leq k \leq 100\).

Proof.
1. \(f(n, 0) = \#\{(x, y) \mid x + y \alpha < n\} = \#\{(x, y) \mid x + 199 y < n\} = n\).
2. 
\[ \begin{aligned}
& f(0, k) = \#\{(x, y) \mid x + y \alpha < k \alpha\} = \sum_{l=0}^{k-1} \#\{(x, l) \mid x + l \alpha < k \alpha\} \\
& = \sum_{l=0}^{k-1} \#\{x \mid x < (k - l) \alpha\} = \sum_{l=0}^{k-1} 200(k - l) - 1 = 200 A - k
\end{aligned} \]
for some integer \(A\).

From this claim, using the equality \(f(x, y) + f(x+1, y+1) = f(x+1, y) + f(x, y+1) + 1\), we can prove that mod 2 the region \(A\) looks like the following: in the rows \((- , 2y)\) the remainders modulo 2 alternate, while the rows \((- , 2y+1)\) contain only odd numbers.

![](https://cdn.mathpix.com/cropped/2024_11_18_86efb4389f14b52b08e1g-44.jpg?height=364&width=506&top_left_y=229&top_left_x=775)

The numbers mod 2 in the construction for 7500.

Construction for 2500
Select \(\alpha \approx 200.001\).