Problem 1575

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.

!

The numbers mod 2 in the construction for 7500.

Construction for 2500
Select $\alpha \approx 200.001$.