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)

About motivation.

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<M\le 2. Fix some \varepsilon>0 and let (x_0,y_0) satisfies M-\varepsilon <g(x_0,y_0)\le M. 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 >>

[1] Bulgarian Mathematical Competitions, 2003 – 2006, P. Boyvalenkov, O. Mushkarov, E. Kolev, N. Nikolov. GIL Publishing House 2007.

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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