Clearly $f(x,y)<f(x,y+1)$ and $f(x,y)<f(x+1,y)$,otherwise $f(x,y)>f(x,y+1)>f(x,y+2)\cdots$,contradiction. Now notice that for each pair of $(a,b)$, the sign of $f(x+a,y+b)-f(x,y)$(if well defined) are all equal(they are equal to the smallest such vector). We call $(a,b)$ good if that sign is positive. We claim that the good $(a,b)$s are exactly those within a half-plane. Otherwise three vectors with the origin in the convex hull will force a cycle in the graph where we add an directed edge for each $(x+a,y+b)\to (x,y)$ with $(a,b)$ good. This implies that we simply sort these points by $ux+vy$ for some $u,v$(and consider $x$ or $y$ coordinate if draw), and $f(x_0,y_0)(0 \le x_0,y_0 \le 100)$ is just the lattice points under the line $vx-uy=vx_0-uy_0$, if we slightly change $u,v$ without affecting all the $f$ with $0\le x,y \le 100$. Now we have $f(x,y)+f(x+1,y+1)-f(x,y+1)-f(x+1,y)=1$ by the following graph. The red parts and the green parts contain the same number of lattice points, and there are exactly one in the blue one. By this we get the upper bound $7500$ and lower bound $2500$. By choosing $u=-1,v=100.5+\epsilon$ and $u=-1,v=101+\epsilon$ they are achieved.

thevictor wrote: Clearly $f(x,y)<f(x,y+1)$ and $f(x,y)<f(x+1,y)$,otherwise $f(x,y)>f(x,y+1)>f(x,y+2)\cdots$,contradiction. Now notice that for each pair of $(a,b)$, the sign of $f(x+a,y+b)-f(x,y)$(if well defined) are all equal(they are equal to the smallest such vector). We call $(a,b)$ good if that sign is positive. We claim that the good $(a,b)$s are exactly those within a half-plane. Otherwise three vectors with the origin in the convex hull will force a cycle in the graph where we add an directed edge for each $(x+a,y+b)\to (x,y)$ with $(a,b)$ good. This implies that we simply sort these points by $ux+vy$ for some $u,v$(and consider $x$ or $y$ coordinate if draw), and $f(x_0,y_0)(0 \le x_0,y_0 \le 100)$ is just the lattice points under the line $ux+vy=ux_0+vy_0$, if we slightly change $u,v$ without affecting all the $f$ with $0\le x,y \le 100$. Now we have $f(x,y)+f(x+1,y+1)-f(x,y+1)-f(x+1,y)=1$ by the following graph. The red parts and the green parts contain the same number of lattice points, and there are exactly one in the blue one. By this we get the upper bound $7500$ and lower bound $2500$. By choosing $u=0,v=100+\epsilon$ and $u=0,v=101+\epsilon$ they are achieved. We achieve the lower bound by $u=-1,v=\frac{201}{2}+\varepsilon$ and the upper bound for $u=-1,v=101+\varepsilon$.

pi_quadrat_sechstel wrote: thevictor wrote: Clearly $f(x,y)<f(x,y+1)$ and $f(x,y)<f(x+1,y)$,otherwise $f(x,y)>f(x,y+1)>f(x,y+2)\cdots$,contradiction. Now notice that for each pair of $(a,b)$, the sign of $f(x+a,y+b)-f(x,y)$(if well defined) are all equal(they are equal to the smallest such vector). We call $(a,b)$ good if that sign is positive. We claim that the good $(a,b)$s are exactly those within a half-plane. Otherwise three vectors with the origin in the convex hull will force a cycle in the graph where we add an directed edge for each $(x+a,y+b)\to (x,y)$ with $(a,b)$ good. This implies that we simply sort these points by $ux+vy$ for some $u,v$(and consider $x$ or $y$ coordinate if draw), and $f(x_0,y_0)(0 \le x_0,y_0 \le 100)$ is just the lattice points under the line $ux+vy=ux_0+vy_0$, if we slightly change $u,v$ without affecting all the $f$ with $0\le x,y \le 100$. Now we have $f(x,y)+f(x+1,y+1)-f(x,y+1)-f(x+1,y)=1$ by the following graph. The red parts and the green parts contain the same number of lattice points, and there are exactly one in the blue one. By this we get the upper bound $7500$ and lower bound $2500$. By choosing $u=0,v=100+\epsilon$ and $u=0,v=101+\epsilon$ they are achieved. We achieve the lower bound by $u=-1,v=\frac{201}{2}+\varepsilon$ and the upper bound for $u=-1,v=101+\varepsilon$. Sorry for the mistake.

The minimum and maximum values are 2500 and 7500 respectively. Proof of bounds: Note that \(f(x,y)<f(x+1,y)\) for all \(x\) and \(y\), else \[f(x,y)>f(x+1,y)>f(x+2,y)>\cdots\]which is absurd. Similarly \(f(x,y)<f(x,y+1)\). Consider the process of placing the elements of \(\mathbb Z_{\ge0}\) in the cells of \(\mathbb Z_{\ge0}^2\) in the order 0, 1, 2, \(\ldots\), so that \(n\) is placed in cell \((x,y)\) when \(f(x,y)=n\). In this process, when \(n\) is placed in \((x,y)\), then the cells \((x-1,y)\) and \((x,y-1)\) must already have been labeled, or they will be filled with a smaller number, contradicting the above. Hence the set of labeled cells will always form a ``chomp-like'' structure. Claim: Consider the moment cell \((x,y)\) is filled with \(f(x,y)=n\), and let \(f(x,y-1)=m\). In every other column with a positive number of labeled cells, exactly one cell was labeled between when \(m\) and \(n\) were labeled. Proof. We simply check that: If some nonempty column had no cell filled during this time, and its top cell is \(f(x',y')<m\), then the cell \((x',y'+1)\) must be filled eventually, so \(f(x',y'+1)>n\). This is a clear contradiction. If some nonempty column was filled twice, then its top two cells must satisfy \(m<f(x',y')<n\) and \(m<f(x',y'+1)<n\). This is again a clear contradiction. \(\blacksquare\) Analogously, we have the reflected version of the above claim. Claim: We always have \[f(x,y)+f(x+1,y+1)=f(x+1,y)+f(x,y+1)+1.\] Proof. Without loss of generality \(f(x,y+1)>f(x+1,y)\). By Claim 1, \begin{align*} f(x,y+1)-f(x,y)&=\#\text{ nonempty columns when } f(x,y+1)\text{ placed}\\ \text{and}\quad f(x+1,y+1)-f(x+1,y) &=\#\text{ nonempty columns when }f(x+1,y+1)\text{ placed}. \end{align*}Hence it suffices to show that between when \(f(x,y+1)\) and \(f(x+1,y+1)\) are placed, the number of nonempty columns increases by exactly once. But by the reflected version of Claim 1, we note that the bottom row increases by exactly one square between when \(f(x,y+1)\) and \(f(x+1,y+1)\) are placed. Since the cells form a chomp-like structure, this proves the claim. \(\blacksquare\) Hence in any \(2\times2\) square, there is either 1 or 3 odd terms. This readily establishes the bounds of 2500 and 7500. Constructions: We show: Claim: Where \(r<n\) below, the function \[f(qn+r,y)=[1+2+\cdots+(q+y)]n+q+(q+y+1)r\]works. Proof. It is clear \(f\) is a bijection: for each \(m\), we may find a unique value of \(s\ge0\) with \[m=(1+2+\cdots+s)n+R,\quad\text{where }R<(s+1)n,\]and pick \(q\equiv R\pmod{s+1}\) with \(0\le q\le s\), \(y=s-q\), and \(r=\lfloor\frac R{s+1}\rfloor<n\). Then we may check that \begin{align*} f(qn+r,y+1)-f(qn+r,y)&=(q+y+1)n+r\\ &=(s+1)n+\left\lfloor\frac R{s+1}\right\rfloor\\ \quad\text{and}\quad f(qn+r+1,y)-f(qn+r,y) &=\begin{cases}q+y+1&\text{if }r\le n-2\\ q+y+2&\text{if }r=n-1\end{cases}\\ &=\begin{cases} s+1&\text{if }R<(n-1)(s+1)\\ s+2&\text{if }R\ge(n-1)(s+1) \end{cases} \end{align*}are increasing functions in \(m\), which is sufficiently to verify the requested condition on \(f\). \(\blacksquare\) Claim: Where \(r<n\) below, the function \[f(qn+r,y)=[1+2+\cdots+(q+y)]n+y+(q+y+1)r\]works. Proof. The proof is analogous to the above, where instead we verify \begin{align*} f(qn+r,y+1)-f(qn+r,y) &=(q+y+1)n+r+1\\ &=(s+1)n+\left\lfloor\frac R{n+1}\right\rfloor+1\\ \text{and}\quad f(qn+r+1,y)-f(qn+r,y) &=q+y+1=s+1 \end{align*}are increasing. \(\blacksquare\) Now taking \(n\gg100\) even in Claim 3 gives \(f(x,y)\equiv x(y+1)\pmod2\) and \(n\gg100\) even in Claim 4 gives \(f(x,y)\equiv(x-1)(y-1)-1\pmod2\). The former is odd 2500 times and the latter is odd 7500 times.

Let $S$ be the set of all vectors $(x_1-x_2,y_1-y_2)$ for some $x_1$, $x_2$, $y_1$, $y_2$ satisfying $f(x_1,y_1)>f(x_2,y_2)$. For all $a\geq x_1$ and $b\geq y_1$, we have $f(a,b)>f(a+x_2-x_1,b+y_2-y_1)$, so $f(a,b)>f(c,d)$ if and only if $(a-c,b-d)\in S$. If $(a,b)\neq(0,0)$, then $(a,b)\in S$ if and only if $(-a,-b)\not\in S$. Therefore, $S$ is closed under addition and no linear combination of elements in $S$ add to $(0,0)$. Since $f(0,i)$ gets arbitrarily large, there exists $i$ such that $f(0,i)>f(0,0)$, so $(i,0)\in S$. If $(-1,0)\in S$, then a sum of elements of $S$ add to $(0,0)$, contradiction. Therefore, $(1,0)\in S$. Similarly, $(0,1)\in S$, so $(a,b)\in S$ for any $a,b>0$. Now, we claim $f(x+1,y+1)-f(x,y+1)-f(x+1,y)+f(x,y)=1$. We have \begin{align*} &f(x+1,y+1)-f(x,y+1)-f(x+1,y)+f(x,y)\\=&\sum_{(x+1-i,y+1-j)\in S}1-\sum_{(x-i,y+1-j)\in S}1-\sum_{(x+1-i,y-j)\in S}1+\sum_{(x-i,y-j)\in S}1\\ =&\sum_{(x+1-i,y+1-j)\in S}1-\sum_{\substack{(x+1-i,y+1-j)\in S\\i\geq1}}1-\sum_{(x+1-i,y-j)\in S}1+\sum_{\substack{(x+1-i,y-j)\in S\\i\geq1}}1\\ =&\sum_{(x+1,y+1-j)\in S}1-\sum_{(x+1,y-j)\in S}1\\ =&\sum_{(x+1,y+1-j)\in S}1-\sum_{\substack{(x+1,y+1-j)\in S\\j\geq1}}\\ =&\sum_{(x+1,y+1)\in S}1\\ =&1. \end{align*} Therefore, there is at least one odd number and one even number in $f(2x+1,2y+1)$, $f(2x,2y+1)$, $f(2x+1,2y)$, and $f(2x,2y)$, so there are between $2500$ and $7500$ pairs $(x,y)$ where $f(x,y)$ is odd. The constructions are $S=\{(x,y)\mid x+(100\pm\varepsilon)y\geq0\}$.

Lovely problem! Is it just me or are irrational number FEs getting popular? First, let $S$ be the set of positive irrational numbers, and positive rational numbers plus or minus epsilon. $S$ can be described as the set of positive constructs that are either strictly greater than or strictly less than each positive rational number in a way that is well-defined. First, we establish some basic tools. Imagine $f(x, y)$ as the cell with coordinate $(x, y)$ in an infinite upper right quadrant of a cartesian grid. By induction, $f(x_1, y_1) > f(x_2, y_2)$ implies $f(x_1+a, y_1+b) > f(x_2+a, y_2+b)$ for $a, b \in \mathbb{Z}_{\geq 0}$. Next, if $f(x_1, y_1) > f(x_2, y_2)$ and $x_2 \geq x_1, y_2, \geq y_1$, then we can use the above claim with induction to show that $f(x_1 + \infty \cdot (x_2 - x_1), y_1 + \infty \cdot (y_2 - y_1))$ is negative, giving contradiction, so any square to the weak upper right of another square must have bigger number inside. I claim that if we order every point in the grid by their intrinsic value of $x + sy$ for some fixed $s \in S$, we obtain a valid bijection by taking the $n$th largest point to $n - 1$. This is quite simple to verify: adding numbers to both sides of a strict inequality maintains their relative order. Now I claim that every valid function as described in the problem must be a bijection of this form. To show this, notice that every bijection is completely defined by a infinite list of "commands", pairs of points $(x_1, y_1)$ and $(x_2, y_2)$ together with a strict comparison between their numbers. Assuming such an $s$ exists, each command requires that if $f(x_1, y_1) > f(x_2, y_2)$ then $x_1 + sy_1 > x_2 + sy_2$. First, we show that if we assume such an $s$ exists, no two commands can contradict one another. Suppose two commands contradict one another, then there exists two negative slope line segments in the plane with the following property: the more negative slope segment has its higher point have smaller number and the less negative slope segment has its lower point with a smaller number. If both segments have equal slope then by Bezout's theorem, we can shift them up far enough using our first basic tool with repeated application to show that a point is greater than itself, giving contradiction. Otherwise, there exists a slope $m$ which lies between the two segments. The two segments give rays such that if you travel upon then the number must increase: but both rays lie on strictly one side of the line with slope $m$, so the cone of the two rays must contain the entire bottom left quadrant. This means a sufficiently large integer linear combination of the two rays lies in the bottom left quadrant (created using repeatedly traveling along rays), however, this violates our second basic tool, giving contradiction. This means that no two commands contradict one another. Each command says that $s < q$ or $s > q$ for some rational number. Since comparing $f(a, 0)$ and $f(0, b)$ for all $a, b$ tells you the result of the comparison for the rational number $q = \frac{a}{b}$, we obtain a well-defined space of comparisons for all positive rational numbers, so $s$ is of the desired form but can additionally be equal to $\epsilon$ or $\infty$. However, neither of these give proper bijections, so we can eliminate them, so $s$ must lie in the set $S$ as desired. Hence, we have restricted $f$ to be a function which maps $(x, y)$ with the $n$th smallest value of $x+sy$ to the number $n - 1$ for exactly those $s \in S$. Now, I claim that the four points $(a, b), (a, b+1), (a+1, b), (a+1, b+1)$ cannot all map to numbers of the same parity. By symmetry around $y = x$, we may assume $s > 1$. Now, if we shift every point onto the line $y = b$, then every number between $(a, b)$ and $(a+1, b)$ can be shifted up to a number between the images of $(a, b+1)$ and $(a+1, b+1)$, while every number between the latter two can be shifted down to a number between the former two with the exception of a number originating from the bottom row of the viable quadrant. There must be exactly one of these such numbers, as because $s$ is not rational, the image of the interval $(a, b+1), (a+1, b+1)$ on the bottom row is an interval of size $1$ whose endpoints are not integers, so there is exactly one extra integer point form the bottom row contributing the a number between the original images of $(a, b+1)$ and $(a+1, b+1)$. This means that the parity difference between $(a, b+1)$ and $(a+1, b+1)$ is the opposite of the parity difference between $(a, b)$ and $(a+1, b)$, finishing. This implies that in every two by two square, there are at most $3$ and at least $1$ odd point. This gives upper and lower bounds of $7500$ and $2500$ respectively. This can be constructed by taking $s = 10000000+\epsilon$ for the $7500$ and $s = 10000000 - \epsilon$ for the $2500$ respectively, finishing.

to hard for imo

C9 is not so intimidating after all Call $(a,b)$ an increasing vector if $a, b \neq 0$ are of different signs and there exists some $(x_0,y_0)$ such that $f(x_0+a,y_0+b)>f(x_0,y_0)$. then the problem condition implies that $f(x+a,y+b)>f(x,y)$ for all $x \geq x_0, y \geq y_0$. Also, say that an increasing vector $(a,b)$ is $\nwarrow$-facing if $a < 0, b > 0$, and $\searrow$-facing if $a > 0, b < 0$. In such cases, define its slope $m_{(a,b)}$ as the value of $b/a$. Claim 1. If $v_1, v_2$ are $\nwarrow$-facing increasing vectors and $u$ is a $\searrow$-facing increasing vector, then $m_{v_1} < m_u < m_{v_2}$ is impossible. The similar result holds if $\searrow$-facing and $\nwarrow$-facing are swapped. Proof. Otherwise, one can construct $\Delta OPQ$ in the xy-plane such that $\overrightarrow{OP}$ is a positive rational multiple of $v_1$, $\overrightarrow{PQ}$ is a positive rational multiple of $v_2$, while $\overrightarrow{QO}$ is a positive rational multiple of $u$. By scaling up appropriately, we have constructed three vectors $k_1v_1,k_2v_2,ku (k_1,k_2,k \in \mathbb{Z})$ whose sum is zero. But this implies $f(x,y) < f((x,y)+k_1v_1) < f((x,y)+k_1v_1 + k_2v_2) < f(x,y)$ for some sufficiently large $x,y$, contradiction. $\square$ This implies that there exists a negative constant $c$ such that all $\nwarrow$-facing increasing vectors have slopes $\in ( -\infty, c]$, and $\nearrow$-facing increasing vectors have slopes $\in [c , 0)$, and only one type of such vectors have slope $=c$ (if $c$ is rational). (the other case such the intervals swapped is impossible, as one can use it to construct $f(x_1,y_1)>f(x_1+x,y_1+y)$ with $x, y \geq 0$, and extend to get a infinite sequence of decreasing outputs of f). Main claim. There exists a function $g(x,y)=\lambda x + y$, $\lambda \in \mathbb{R}_{> 0}$ such that $g(x_0,y_0)$ is the $(f(x_0,y_0)+1)$-th term to appear when listing $\{ g(x,y) \mid (x,y) \in \mathbb Z_{\ge 0}\times \mathbb Z_{\ge 0} \}$ in ascending order (where if $\lambda$ is rational and there are cases where $g(x_1,y_1) = g(x_2,y_2)$ for distinct $(x_1,y_1),(x_2,y_2)$, we decide to either always list the pair with larger $x$-coordinate first or always list the pair with larger $y$-coordinate first). The geometric interpretation is to slide a line with negative slope starting at the origin, and listing points as they are hit by the line. Proof. Just let $\lambda = -c$ as in the previous part. It is also apparent that all such functions work. $\square$ Now that we have characterized all functions $f$, we move on to evaluting the answer. It is $2500 \leq N \leq 7500$. For the construction of lower and upper bounds, let $\lambda = 1/100$ and always list the pairs with larger $y$- and $x$-coordinate first respectively. For the optimality, divide the $10000$ points $(x,y)$ into $2500$ sets of the form $\{ (x,y),(x+1,y),(x,y+1),(x+1,y+1) \}$ in the obivous way. We prove that the $4$ points in any such set cannot all have the same parity. In fact, we may assume $\lambda$ is irrational (for convenience) by shifting it by a sufficiently small amount such that the first $f(100,100)$ terms of the sequence are not affected, and then note that $f(x,y)= \# ((x_0,y_0) \in \mathbb{Z}_{\geq 0}^2 \mid \lambda x_0+y_0 < \lambda x + y)$, so \begin{align*} &(f(x+1,y+1)-f(x+1,y))-(f(x,y+1)-f(x,y)) \\ &= \# ((x_0,y_0) \in \mathbb{Z}_{\geq 0}^2 \mid \lambda x + \lambda + y < \lambda x_0+y_0 < \lambda x + \lambda + y + 1) \\ &- \# ((x_0,y_0) \in \mathbb{Z}_{\geq 0}^2 \mid \lambda x + y < \lambda x_0+y_0 < \lambda x + y + 1) \\ &= \# ((x_0,y_0) \in \mathbb{Z}_{\geq 0}^2 \mid \lambda x + \lambda + y < \lambda x_0+y_0 < \lambda x + \lambda + y + 1) \\ &- \# ((x_0,y_0) \in \mathbb{Z}_{\geq 0}^2 \mid \lambda x + \lambda + y < \lambda (x_0+1)+y_0 < \lambda x + \lambda + y + 1) \\ &= \# (y_0 \in \mathbb{Z}_{\geq 0} \mid \lambda + y < y_0 < \lambda + y + 1) \\ &= 1 \end{align*}which proves our desired claim. Hence $N \in \left[10000 \cdot \frac 14, 10000 \cdot \frac 34 \right] = [2500,7500]$, as desired.

Cool Problem, although easy for C9? (solved in 20 min) Bounds: We view the problem as a grid labelling of cells. Claim 1: $f(x,y) < f(x+1,y)$ and $f(x,y) < f(x,y+1)$ Proof: Clear from condition, if not then we get infinite decreasing chain of non-negative integers, which is an obvious contradiction. $\blacksquare$ Now, notice due to the above claim the structure of the problem "feels" like chomp, motivated by this observation we think of the problem as a number filling process in the grid starting with $0$ in increasing order, when we fill in the cell $(x,y)$ its left and down neighbours must be already filled in, now the above motivates the following claim and the characterization of the function $f$. Claim 2: Let $f(x,y)=p_1$ and $f(x,y-1)=p_2$ then exactly one number $p \in (p_1,p_2)$ has been marked in every column (with number of elements marked in it greater than or equal to $0$ ofcourse). Proof: More or less clear. Now, we move on to the main claim and the crux of the problem, that is to characterize $f$. Claim 3:[The crux] \[f(x+1,y+1)+f(x,y)=f(x,y+1)+f(x+1,y)+1\]Proof: Here, the key is to use a reflected version of Claim 2, along with a similar counting argument, and the claim follows. Now, for the bounds, notice by the crux claim, each $2 \times 2$ subgrid has either $1$ or $3$ odd terms and so, $\min = 2500$ and $\max = 7500$. Construction: The construction is to order every point by value of $x+\alpha y$ for some irrational fixed $\alpha$, now we prove this works, clearly this is an bijection, then it is immediate to deduce the increasing condition in row/column by taking finite difference in one variable and its easy finish.