5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ $\displaystyle\;f(p,q,r) = \frac{3pqr}{p+q+r}\;$ is a solution. I believe this is the only solution but I can't prove it. $\endgroup$ – achille hui Jul 16 '14 at 19:56
  • $\begingroup$ How did you get this solution? $\endgroup$ – Deathkamp Drone Jul 16 '14 at 20:00
  • 4
    $\begingroup$ If you look at your equation, $(p,q,r)$ only connects to points with same $p+q+r$. This means you can look at each $p+q+r = \text{constant}$ layer separately. The intersection of $T$ with any such layer forms a triangular lattice. Your equation reduces to a discrete version of Poisson equation there. The boundary condition suggest the solution (at least in continuum limit) contains a factor proportional to $pqr$. Direct substitution shows that you can scale this to get a solution. Since we are dealing with some sort of "Poisson equation", that's why I suspect the solution is unique. $\endgroup$ – achille hui Jul 16 '14 at 20:09
  • $\begingroup$ This is an IMO 2001 shortlist problem. $\endgroup$ – Calvin Lin Jul 18 '14 at 22:57
  • $\begingroup$ Thank you, Calvin. I found this problem some lecture notes so I didn't know where it came from. Ironically, I looked up the solution on AoPS just to find out that they pulled out of nowhere the function Achille discovered and then proved that this is the only solution. $\endgroup$ – Deathkamp Drone Jul 19 '14 at 2:02
4
+50
$\begingroup$

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$

$\endgroup$
3
$\begingroup$

Achille Hui did the hardest part of the work by discovering the closed formula $\frac{3pqr}{p+q+r}$. The rest is a routine "maximum principle" argument that I explain below.

For a positive integer $k$, let $T_k$ be the finite set $\lbrace (p,q,r)\in T | p+q+r=k\rbrace$. For $x=(p,q,r)\in T$, define the neighborhood $N(x)$ of $x$ to be

$$ \begin{array}{lcl} N(p,q,r)&=&\lbrace (p+1,q-1,r);(p+1,q,r-1);(p,q+1,r-1); \\ & & (p,q-1,r+1);(p-1,q+1,r);(p-1,q,r+1)\rbrace \end{array} \tag{1} $$

and the strict neighborhood $N'(x)$ of $x$ to be $\lbrace (u,v,w)\in N(x) | uvw>0\rbrace$. We say that $x\in T_k$ is interior if $N’(x)=N(x)$, and extremal otherwise.

Let $g(p,q,r)=f(p,q,r)-\frac{3pqr}{p+q+r}$ for $(p,q,r)\in T$. Then $g$ satisfies $g(p,q,r)=0$ if $pqr=0$, and

$$ 6g(x)=\sum_{y\in N'(x)}g(y) \tag{2} $$

for any $x\in T_k$ (note that $N(x)$ and $N’(x)$ stay in $T_k$ when $x\in T_k$).

Now, let $M$ ($m$) be the maximum (minimum) value of $g$ on $T_k$. There is some $x_M\in T_k$ such that $g(x_M)=M$. We now apply (2) to $x=x_M$, and obtain a formula (2').

If $M > 0$, then (2') is only possible when $x_M$ is interior and $g(y)=M$ for all $y\in N(x_M)$. If we put $L=\lbrace x\in T_k | g(x)=M\rbrace$, we would deduce that $L$ consists only of interior points but also satisfies $N(x)\subseteq L$ for any $x\in L$, which is impossible because when we move away from the interior of $T_k$ we are always forced to eventually reach extremal points.

So $M\leq 0$. A similar argument (or if you please, you may reuse the result just shown on $-g$ instead of $g$) shows that $m\geq 0$.

So $M\leq 0 \leq m$, but on the other hand $m\leq M$. This forces $m=M=0$, so $g$ is identically zero.

To conclude, $\frac{3pqr}{p+q+r}$ is the unique solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.