Problem: Let $T=\{(p,q,r)\mid p,q,r \in \mathbb{Z}_{\geq0}\}$. Find all functions $f:T\to \mathbb{R}$ such that:
$$f(p,q,r)=\\
=\begin{cases}
0, & \text{ if } pqr = 0 \\
1 + \frac{1}{6}\left(f(p+1,q-1,r)+f(p+1,q,r-1)+f(p,q+1,r-1)+\\
\;\;\;\;\;\;
f(p,q-1,r+1)+f(p-1,q+1,r)+f(p-1,q,r+1)\right) & \text{ otherwise.}
\end{cases}$$
Progress so far: It's not hard to see that $f$ is symmetric in $p,q,r$, which is useful to know. From the recursive definition one can also infer that $f:T\to \Bbb{Q}^+$, so no trig functions or logs. That's all I could observe from the get-go. I've tried calculating some values of $f$ to have an idea on how the functions look like (if there are any) but having trouble calculating even small values of $f$, for example $f(1,2,3)$ or $f(2,2,2)$. All I know is that $f(0,a,b)=0$ and $f(1,1,1)=1$. I could guess a solution based on my initial observations but I can't see any obvious candidates.
Any help would be appreciated, thanks.
Answer
When I worked on this problem back in 2002, showing uniqueness was really easy through the "average of neighbors" observation (albeit on a slanted hexagonal board, instead of the regular chessboard).
Proof of uniqueness: Suppose we have 2 solutions $ f(p,q,r)$ and $ g(p,q,r)$. Let $ h(p,q,r) = f(p,q,r) - g(p,q,r)$. Then, we get that
$$ 6 h(p,q,r) = h(p+1, q-1, r) + h(p-1, q+1, r) + h( p, q+1, r-1) + h( p, q-1, r+1) + h( p+1, q, r-1) + h(p-1, q, r+1). $$
Consider the plane $ p+q+r = N$. Oberve that the neighbors of the cell $(p,q,r)$ are these 6 other cells with coordinates as given above. Hence, every cell is the average of it's neighbors. Through the standard argument (extremal principle), this implies that all cells on this finite board are equal.
We also have the boundary conditions that $h(p,q,r ) = 0$ for $pqr=0$, hence $h(p,q,r) = 0$. Thus, the function is unique $_\square$
Finding the solution was harder, but still motivated from the conditions.
Note: It is important to bear in mind that as an ('easy') Olympiad problem, it often has a nice solution that can be motivated.
Finding function: From the boundary condition that $pqr=0 \Rightarrow f(p,q,r) = 0$, we guess the initial function $ F( p,q,r) = pqr$.
Observe that since $ (p-1)(q+1) r + (p+1)(q-1)r = 2pqr - 2r$, so this guess gives us:
$ F(p,q,r) = \frac{ p+q+r} { 3} + \frac{1}{6} [ F(p-1, q+1, r) + F(p+1, q-1, r) + F(p, q-1, r+1), F(p, q+1, r-1) + F( p-1, q, r+1), F(p+1, q, r-1) ] $.
Observe that since $p+q+r$ is a constant for all of these 7 terms, we should look at
$$ f(p,q,r) = \frac{ F(p,q,r) } { \frac{p+q+r} {3} } = \frac{3 pqr} { p+q+r}.$$
Indeed, this works. $_\square$
Note: Had $F(p,q,r) = pqr$ not worked, the next guess would have been $ F(p,q,r) = p^2q^2r^2$
No comments:
Post a Comment