Problem 1947

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 $k_{1} / l_{1}<k_{2} / l_{2}$ with $k_{1} / l_{1}$ a grade. Then:
- $\left(k_{1}, l_{1}\right)$ is a needle
- so $\left(k_{1} l_{2}, l_{1} l_{2}\right)$ is a needle,
- so $\left(k_{2} l_{1}, l_{1} l_{2}\right)$ is a needle (as $k_{2} l_{1}-k_{1} l_{2}>0$ and $(1,0)$ is a needle).
Thus ( $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 $1 / n$ is not a grade for some large $n$. That means that small positive rational values are not grades, then there is a switch, and after that all values are grades. Call the place of that switch $\alpha$. Here $\alpha$ is the infimum of the grades.

Claim (Key property). If $x_{1}+y_{1} \alpha>x_{2}+y_{2} \alpha$ then $f\left(x_{1}, y_{1}\right)>f\left(x_{2}, y_{2}\right)$.
Proof. If both $x_{1} \geqslant x_{2}$ and $y_{1} \geqslant y_{2}$ this is clear.
Suppose $x_{1} \geqslant x_{2}$ and $y_{1}<y_{2}$. Then $\frac{x_{1}-x_{2}}{y_{2}-y_{1}}>\alpha$ is a grade. This gives $f\left(x_{1}, y_{1}\right)>f\left(x_{2}, y_{2}\right)$. Suppose $x_{1}<x_{2}$ and $y_{1} \geqslant y_{2}$. Then $\frac{x_{2}-x_{1}}{u_{1}-u_{2}}<\alpha$ is not a grade. This gives $f\left(x_{2}, y_{2}\right)<f\left(x_{1}, y_{1}\right)$.

From those observations we get the following claim.
Claim. The function $f$ orders pairs $(x, y)$ based on the value of $x+y \alpha$. If $\alpha$ is rational, tiebreaking is done by larger $x$ - or $y$-coordinate (depending on whether $\alpha$ is a grade).

We can imagine this the following way: take a line with slope $-\frac{1}{\alpha}$ under the first quadrant of the plane. And we start to move this line upward (but it stays parallel to the original line). First it hits $(0,0)$, so $f(0,0)=0$. And each time the line hits a point $p, f(p)$ is the number of points hit before. If $\alpha \in \mathbb{Q}$, it is possible that the line hits multiple points. Then those points are ordered the same way as their $x$ or $y$ coordinates, depending on whether $\alpha$ is a grade.

We understood the behaviour of $f$, now we need to focus on the region of $A=\{(x, y) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid x<100, y<100\}$. First, we can assume that $\alpha$ is irrational. If we change it a little bit in the right direction, the behaviour and values of the $f$ function does not change in $A$.

Claim.
$$f(x, y)+f(x+1, y+1)=f(x+1, y)+f(x, y+1)+1$$
Proof.
$$\begin{gathered} f(x+1, y+1)-f(x, y+1)= \\ \#\{(a, b) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid x+(y+1) \alpha \leqslant a+b \alpha<(x+1)+(y+1) \alpha\}= \\ \#\{(a, b) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{>0} \mid x+(y+1) \alpha \leqslant a+b \alpha<(x+1)+(y+1) \alpha\}+ \\ \#\{(a, 0) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid(x+1)+y \alpha \leqslant a<(x+1)+(y+1) \alpha\}= \\ \#\{(a, b) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid x+y \alpha \leqslant a+b \alpha<(x+1)+y \alpha\}+1=f(x+1, y)-f(x, y) . \end{gathered}$$

From this claim we immediately get that $2500 \leqslant N \leqslant 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 \leqslant n \leqslant 100$.
2. $f(0, k) \equiv k \bmod 2$ for $0 \leqslant k \leqslant 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\} \\ & \quad=\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 $\bmod 2$ the region $A$ looks like the following: in the rows $(-, 2 y)$ the remainders modulo 2 alternate, while the rows $(-, 2 y+1)$ contain only odd numbers.

Construction for 2500 Select $\alpha \approx 200.001$.
Claim.
1. $f(n, 0)=n$ for $0 \leqslant n \leqslant 100$.
2. $f(0, k) \equiv 0 \bmod 2$ for $0 \leqslant k \leqslant 100$.
Proof.
1. As above.
2. Similarly to the above:
$$\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)=200 A \end{aligned}$$
for some integer $A$.

Similarly to the above, we can prove that mod 2 the region $A$ looks like the following: in the rows $(-, 2 y)$ the remainder modulo 2 alternate, while the rows $(-, 2 y+1)$ contain only even numbers.

Thus, the optimal bounds are $2500 \leqslant N \leqslant 7500$.