Problem: Find all functions $f \colon \ZZ^2 \to [0,1]$
such that for any integers $x$ and $y$,
\[ f(x, y) = \frac{f(x-1, y) + f(x, y-1)}{2}. \]

Solution: We claim that the only functions $f$ are constant functions.
(It is easy to see that they work.)

\paragraph{First solution (hands-on).}
First, iterating the functional equation
relation to the $n$th level shows that
\[ f(x, y) = \frac{1}{2^n} \sum_{i=0}^n \binom{n}{i} f(x-i, y-(n-i)). \]
In particular,
\begin{align*}
  |f(x, y) - f(x-1, y+1)|
  &= \frac{1}{2^n} \left\lvert \sum_{i=0}^{n+1} f(x-i, y-(n-i)) \cdot
  \left(\binom{n}{i} - \binom{n}{i-1} \right) \right\rvert \\
  &\le \frac{1}{2^n} \sum_{i=0}^{n+1} \left\lvert
    \binom{n}{i} - \binom{n}{i-1} \right\rvert \\
  &= \frac{1}{2^n} \cdot 2\binom{n}{\lfloor n/2 \rfloor}
\end{align*}
where we define $\binom{n}{n+1} = \binom{n}{-1} = 0$ for convenience.
Since \[ \binom{n}{\lfloor n/2 \rfloor} = o(2^n) \]
it follows that $f$ must be constant.

\begin{remark*}
A very similar proof extends to $d$ dimensions.
\end{remark*}

\paragraph{Second solution (random walks, Mark Sellke).}
We show that if $x+y=x'+y'$ then $f(x,y)=f(x',y')$.
Let $Z_n$, $Z'_n$ be random walks starting at $(x,y)$
and $(x',y')$ and moving down/left.
Then $f(Z_n)$ is a martingale so we have
\[\mathbb E[f(Z_n)]=f(x,y), \qquad
  \mathbb E[f(Z'_n)]=f(x',y') .\]
We'll take $Z_n$, $Z'_n$ to be independent until they hit each other,
after which they will stay together.  Then
\[|\mathbb E[f(Z_n)-f(Z'_n)]| \leq \mathbb E[|f(Z_n)-f(Z'_n)|]
  \leq p_n\]
where $p_n$ is the probability that $Z_n$, $Z'_n$ never collide.
But the distance between $Z_n$, $Z'_n$
is essentially a $1$-dimensional random walk,
so they will collide with probability $1$, meaning $\lim_{n\to\infty} p_n=0$.
Hence
\[ |f(x,y)-f(x',y')| = |\mathbb E[f(Z_n)-f(Z'_n)]| = o(1)\]
as desired.

\begin{remark*}
If the problem were in $\ZZ^d$ for large $d$,
this solution wouldn't work as written
because the independent random walks wouldn't hit each other.
However, this isn't a serious problem
because $Z_n$, $Z'_n$ don't have to be independent
before hitting each other.
Indeed, if every time $Z_n,Z'_n$ agree on a new coordinate
we force them to agree on that coordinate forever,
we can make the two walks individually have the distribution
of a coordinate-decreasing random walk but make them intersect
eventually with probability $1$.
The difference in each coordinate will be a $1$-dimensional
random walk which gets stuck at $0$.
\end{remark*}


\paragraph{Third solution (martingales).}
Imagine starting at $(x, y)$
and taking a random walk down and to the left.
This is a martingale.
As $f$ is bounded, this martingale converges with probability $1$.
Let $X_1, X_2, \dots$ each be random variables
that represent either down moves or left moves with equal probability.
Note that by the Hewitt-Savage 0-1 law,
we have that for any real numbers $a < b$,
\[ \Pr\left[ \lim_{n \to \infty} f((x, y)+X_1+X_2+\dots + X_n)
  \in [a, b] \right] \in \{0,1\}. \]
Hence, there exists a single value $v$ such that with probability $1$,
\[ \Pr\left[\lim_{n \to \infty} f((x, y)+X_1+X_2+\dots + X_n)
  = v\right] = 1. \]
Obviously, this value $v$ must equal $f(x, y)$.
Now, we show this value $v$ is the same for all $(x, y)$.
Note that any two starting points have a positive chance of meeting.
Therefore, we are done.