# Kind of Harmonic function. USA TST, 2018. Part I.

I plan in two post to comment on a type of problems, given at some IMO level competitions. We have a function $f : \mathbb{Z}^2\to \mathbb{R}$ defined on the lattice points of the plane. The value of $f$ at any lattice point is the average of its values taken at all or some of the neighbouring points. For example

$\displaystyle f(x, y) = \frac{f(x - 1, y) + f(x+1,y)+ f(x, y - 1)+f(x,y+1)}{4}\quad (1)$

Such kind of functions we call harmonic. Of course, there exist plenty of such functions, for example constant ones. We also can define $f$ at three neighbouring points and spread out the values of the function complying to the condition. An interesting fact is that if we impose $f$ to be bounded, the only possibility is it to be constant. Moreover, if $f$ is lower (or upper) bounded, the same is also true. Two methods will be presented. The first one – using elementary math, the second one is the fastest one but uses a convex analysis fact – the Krein-Milman theorem.

### Problem 1

(USA TST #1 IMO 2018. p2.) Find all functions $f: \mathbb{Z}^2 \to [0, 1]$ such that for any integers $x$ and $y$,

$\displaystyle f(x, y) = \frac{f(x - 1, y) + f(x, y - 1)}{2}\quad (2)$

One may skip this rather long explanation and jump directly to the solution in the next section, which starts from a scratch.
So, we have a bounded function on the set of lattice points. The value of $f$ at any point $(x,y)$ is the average of the values at its bottom neighbour $(x,y-1)$ and its left one $(x-1,y)$. To see roughly why $f$ should be a constant, suppose $f$ takes only finite number of values. Then, $f$ takes its maximal value $M$ at some point $(x_0,y_0)$. By $(2)$ we get $f(x_0-1,y_0)=f(x_0,y_0-1)=M$ and in the same way $f(x,y)=M, \forall (x,y)\in D=\{(x,y): x\le x_0,y\le y_0\}.$ Now, we take again the maximal value of $f$ on $\mathbb{Z}^2\setminus D$ and repeating it infinitely many times obtain $f$ is constant on entire $\mathbb{Z}^2$.
It seems, an argument like that may help in the continuous case. Oh, not at all! This problem is indeed difficult. For example the problem presented at the beginning (see $(1)$) was given at a Bulgarian TST for BMO 2003 (see [1]). As far as I know, no one solved it. Nevertheless, let’s try it.
Suppose, $f,g$ satisfy $(2)$. Then any linear combination $af(x,y)+bg(x,y)$ also satisfy $(2)$. Any translation of $f\,,\, f(x-a,y-b)$ where $a,b\in \mathbb{R}$ also comply to that condition. Particularly $g(x,y):=f(x+1,y)-f(x,y)$ also satisfies $(2)$. $g(x,y)$ may be interpret as the velocity of changing of $f$. Now, we cannot take the maximal value of $f$, but we may take a value as close to the $M:=\sup_{(x,y)\in\mathbb{Z}^2}f(x,y)$ as we want. Let $f(x_0,y_0)=M-\varepsilon$. Using $(2)$, it follows $f(x_0-1,y_0)\geq M-2\varepsilon$. Applying it again several times, we get

$f(x_0-n,y_0)\geq M-2^n\varepsilon$

It means, for any fixed $n$, taking $\varepsilon$ small enough we can ensure $f(x_0-i,y_0), i=1,2,\dots,n$ be also close to $M$. It is of little help, but applying the same argument to $g(x,y)$ we could ensure the velocity of changing of $f$ is not too small for as long interval as we want. But it would mean $f$ can deviate a large amplitude, which is not allowed since $f$ is bounded.

### Solution of Problem 1.

Seeking for contradiction, suppose there exists $f:\mathbb{Z}^2\to [-1,1]$ satisfying $(2)$ which is not constant. Then, there exists a point $(x_0,y_0)\in \mathbb{Z}^2$ for which either $f(x_0+1,y_0)\ne f(x_0,y_0)$ or $f(x_0,y_0+1)\ne f(x_0,y_0)$. WLOG, suppose the former holds (otherwise we can flip $x$ and $y$). We also can assume $f(x_0+1,y_0)-f(x_0,y_0)>0$, otherwise we consider $-f$. Let $g(x,y):=f(x+1,y)-f(x,y)$. Clearly, $g$ also satisfies $(2)$ and it is bounded. Denote $M:=\sup g(x,y)$, hence $0. Fix some $\varepsilon>0$ and let $(x_0,y_0)$ satisfies $M-\varepsilon . Condition $(2)$ gives us $g(x_0-1,y_0)\geq M-2\varepsilon$. Applying it again several times, we get

$\displaystyle g(x_0-i,y_0)\geq M-2^n\varepsilon, i=1,2,\dots$

It follows

$\displaystyle g(x_0-i,y_0)\geq \frac{M}{2},i=1,2,\dots n$

where $n=\left\lfloor\log (M/2\varepsilon)\right\rfloor.$ Finally, we have

$\displaystyle f(x_0,y_0)-f(x_0-n,y_0)=\sum_{i=1}^n g(x_0-i,y_0)>\frac{nM}{2}$

The LHS is bounded, but we can make the RHS as large as we want by taking sufficiently small $\varepsilon$ (thus $n$ as large as we want), contradiction.

To the next part >>

References:
[1] Bulgarian Mathematical Competitions, 2003 – 2006, P. Boyvalenkov, O. Mushkarov, E. Kolev, N. Nikolov. GIL Publishing House 2007.
[2] https://artofproblemsolving.com/community/c6h1558131

## 3 thoughts on “Kind of Harmonic function. USA TST, 2018. Part I.”

1. silouanb says:

Are you going to post the solution using Krein-Milman? Thanks

This site uses Akismet to reduce spam. Learn how your comment data is processed.