Let \(\mathbb Z_{\ge 0}\) be the set of non-negative integers, and let \(f:\mathbb Z_{\ge 0}\times \mathbb Z_{\ge 0} \to \mathbb Z_{\ge 0}\) be a bijection such that whenever \(f(x_1,y_1) > f(x_2, y_2)\), we have
\[f(x_1+1, y_1) > f(x_2 + 1, y_2)\;\;\text{and}\;\;f(x_1, y_1+1) > f(x_2, y_2+1).\]
Let \(N\) be the number of pairs of integers \((x,y)\) with \(0\le x,y<100\), such that \(f(x,y)\) is odd. Find the smallest and largest possible values 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 \(k_{1} / l_{1}\[A = \left\{(x, y) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid x<100, y<100\right\}.\]
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)= \\ \#\left\{(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\right\}= \\ \#\left\{(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\right\}+ \\ \#\left\{(a, 0) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid(x+1)+y \alpha \leqslant a<(x+1)+(y+1) \alpha\right\}= \\ \#\left\{(a, b) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid x+y \alpha \leqslant a+b \alpha<(x+1)+y \alpha\right\}+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)=\#\left\{(x, y) \in \mathbb{Z}_{\geqslant 0} \times \mathbb{Z}_{\geqslant 0} \mid x+y \alpha<a+b \alpha\right\}\]
**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 \quad \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 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\). **Claim:** 1. \(f(n, 0)=n\) for \(0 \leqslant n \leqslant 100\). 2. \(f(0, k) \equiv 0 \quad \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 \(\bmod 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.  The numbers mod 2 in the construction for 7500. ### Common remarks - In the proposer's solution, an exact formula is proved in the case where \(\alpha\) is irrational. Let \(\mu=\frac{1}{\alpha}\) and \(\nu=\alpha\). Then\[f(a, b)=a b+(\lceil 1 \mu\rceil+\cdots+\lceil\mu\rceil)+(\lceil 1 \nu\rceil+\cdots+\lceil\nu\rceil)\]
They even suggested that this could be the source of a fun olympiad problem: it is not easy to see that \(f\) is a bijection. - (On the choice of statement, by the proposer). As seen in the solution, such functions have various properties, and it was not clear what statement to choose. I decided to go with the present statement since I believe it requires a good understanding of the setup and the functions involved. The key property is used in order to establish the bounds, and the formula is used to develop constructions and easily verify they work. While choosing a different statement (e.g. just prove the key property) may make the problem less bulky, I believe that doing so runs the risk of introducing unintended solutions which don't "see the full picture." In fact, the present statement probably runs admits such solutions as well, likely through proving the key property via simply examining valid locations for \(n+1\) given the locations of \(0, \ldots, n\), and using induction. Unfortunately, I'm not sure how else to improve the statement. One person I've shown this problem to suggests removing one half of the problem, by only asking for the smallest or only the largest possible value of \(N\). Their rationale is that the two parts are mostly the same. I sympathize with them, but am reluctant to break the symmetry. - (PSC) The real difficulty of this problem is that one should understand the whole picture, and in particular how the function \(f\) works, and how that quadrant can behave. In this solution we characterised all such functions \(f\), before even talking about parity, while the problem only asks the number of odd numbers.