Let $f:\mathbb{Z}^2\rightarrow\mathbb{Z}$ be a function satisfying \[f(x+1,y)+f(x,y+1)+1=f(x,y)+f(x+1,y+1)\]for all integers $x$ and $y$. Can it happen that $|f(x,y)|\leq 2024$ for all $x,y\in\mathbb{Z}$?
Problem
Source: Philippine Mathematical Olympiad 2024 P1
Tags: algebra, functional equation
25.02.2024 05:38
25.02.2024 05:42
Is the lattice grid interpretation helpful in any way?
06.03.2024 22:41
navier3072 wrote: Is the lattice grid interpretation helpful in any way? It seems to make it easier to prove things, but the claims can be phrased with induction also. For example, for any $a < b, c < d$, the expression $f(a, c) + f(b, d) - f(a, d) - f(b, c)$ is the area of the rectangle with vertices $(a, c), (b,d), (a, d), (b, c)$. This can be shown by inducting, but also by tiling the rectangle with unit squares and summing $f(x, y) + f(x+1, y+1) - f(x, y+1) - f(x+1, y)$ across all $a \leq x < b, c \leq y < d$.
19.10.2024 05:22
Solution from Twitch Solves ISL: No, it can't happen. Observing that $f(x,y) = xy$ happens to work, let $g(x,y) = f(x,y) - xy$. Then the given condition on $f$ implies that \[ g(x+1,y) + g(x,y+1) = g(x,y) + g(x+1, y+1). \]It turns out we can classify all the functions $g$ satisfying this equation. Claim: If $g(x,y)$ satisfies the above equation, then in fact \[ g(x,y) = g(x,0) + g(0,y) - g(0,0). \]Proof. For $x,y \ge 0$ it follows easily by induction on $|x|+|y|$. The proof for the other quadrants is the same. $\blacksquare$ Translating back, this implies \[ f(x,y) = xy + f(x,0) + f(0,y) - f(0,0). \]So it's obvious $f$ can't be bounded by $2024$. Remark: In fact, this basically classifies all the functions $f$.
31.12.2024 21:54
Woah. Got this solution while watching the New Year's fireworks. Assume that $|f(x, y)| \le 2024 \forall x, y, \in \mathbb{Z}$. Take the obvious lattice grid interpretation (i. e. $(x, y)$ is the point $(x, y)$), and let $f(A)$ stand for the function evaluated at point $A$. Claim: For all $k\ge 0$, in a $2^k \times 2^k $ square with sides parallel to the axes and vertices $ABCD$ such that $A$ is at the bottom-left, we have $$f(A)+f(C) = f(B)+f(D) + 4^{k-1}.$$Proof: Induction on $k$. Base case: $k = 0$ is literally just the statement of the problem. Inductive step: Assume the statement holds for $k$, we prove it for $k+1$. Mark the centre of the $2^{k+1}\times 2^{k+1}$ square, call it $E$. Let the midpoints of $AB, BC, CD, DA$ be $P, Q, R, S$ respectively. Then we have $$f(A) + f(C) = (f(A) + f(E)) + (f(E) + f(C)) - 2f(E)$$$$ = (f(P) + f(S) + 4^{k-1}) + (f(Q) + f(R) + 4^{k-1}) - 2f(E)$$$$ = (f(P) + f(Q)) + (f(R) + f(S)) + 2 \times 4^{k-1} - 2f(E)$$$$ = (f(B) + f(E) + 4^{k-1}) + (f(D) + f(E) + 4^{k-1}) + 2 \times 4^{k-1} - 2f(E) = f(B) + f(D) + 4^k.$$$\square$ Now consider a $2^m \times 2^m $ square with sides parallel to the axes such that $4^{m-1} > 4 \times 2024$. Then we have for the vertices $W, X, Y, Z$ with $W$ the bottom-left corner that $f(W) + f(Y) - f(Z) - f(X) = 4^{m-1}$, a contradiction as $|f(T)| \le 2024 \forall T$. Therefore, the answer is indeed $\boxed{no}$.