International Mathematical Olympiad

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{array}{rl}f\left(x_1,y_1\right)>f\left(x_2,y_2\right)& ⟺f\left(x_1+1,y_1\right)>f\left(x_2+1,y_2\right)\\ & ⟺f\left(x_1,y_1+1\right)>f\left(x_2,y_2+1\right)\end{array}$$ 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}}_{⩾0}\times {\mathbb{Z}}_{⩾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⩾x_2$ and $y_1⩾y_2$ this is clear. Suppose $x_1⩾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⩾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}}_{⩾0}\times {\mathbb{Z}}_{⩾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{array}{c}f(x+1,y+1)-f(x,y+1)=\\ \#\{(a,b)\in {\mathbb{Z}}_{⩾0}\times {\mathbb{Z}}_{⩾0}\mid x+(y+1)\alpha ⩽a+b\alpha <(x+1)+(y+1)\alpha \}=\\ \#\{(a,b)\in {\mathbb{Z}}_{⩾0}\times {\mathbb{Z}}_{>0}\mid x+(y+1)\alpha ⩽a+b\alpha <(x+1)+(y+1)\alpha \}+\\ \#\{(a,0)\in {\mathbb{Z}}_{⩾0}\times {\mathbb{Z}}_{⩾0}\mid (x+1)+y\alpha ⩽a<(x+1)+(y+1)\alpha \}=\\ \#\{(a,b)\in {\mathbb{Z}}_{⩾0}\times {\mathbb{Z}}_{⩾0}\mid x+y\alpha ⩽a+b\alpha <(x+1)+y\alpha \}+1=f(x+1,y)-f(x,y).\end{array}$$

From this claim we immediately get that $2500⩽N⩽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}}_{⩾0}\times {\mathbb{Z}}_{⩾0}\mid x+y\alpha <a+b\alpha \}$$

Construction for 7500 Select $\alpha \approx 199.999$. Claim. 1. $f(n,0)=n$ for $0⩽n⩽100$. 2. $f(0,k)\equiv k\mathrm{mod}2$ for $0⩽k⩽100$. Proof. 1. $f(n,0)=\#\{(x,y)\mid x+y\alpha <n\}=\#\{(x,y)\mid x+199y<n\}=n$. 2. $$\begin{array}{rl}& 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=200A-k\end{array}$$ 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 $\mathrm{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.

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

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

Thus, the optimal bounds are $2500⩽N⩽7500$.