Maths Olympiad Prep

Track / Stage 8 / 4 of 180 #1704 of 1964

Problem 1704

IMO Shortlist mid-range; USAMO P2/P5
Algebra Difficulty 8.0 Prove it Auswahlwettbewerb Zur IMO · Germany · 2002

Let PP be the set of all ordered pairs (p,q)(p, q) of nonnegative integers. Determine all functions f:PIRf: P \rightarrow \mathrm{IR} with the property
f(p,q)={0 if pq=01+12f(p+1,q1)+12f(p1,q+1) otherwise . f(p, q)=\left\{\begin{array}{c} 0 \quad \text{ if } p q=0 \\ 1+\frac{1}{2} f(p+1, q-1)+\frac{1}{2} f(p-1, q+1) \text{ otherwise } \end{array} .\right.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Solution:

The only such function is f(p,q)=pqf(p, q)=p \cdot q.
This function obviously satisfies the first condition for p=0p=0 or q=0q=0. For pq0p q \neq 0 we have
1+12f(p+1,q1)+12f(p1,q+1)=1+12(p+1)(q1)+12(p1)(q+1)=pq, 1+\frac{1}{2} f(p+1, q-1)+\frac{1}{2} f(p-1, q+1)=1+\frac{1}{2}(p+1)(q-1)+\frac{1}{2}(p-1)(q+1)=p q,
so that the second condition is also satisfied.

It remains to be shown that there is no other function with these properties. To do this, we set f(p,q)=pq+g(p,q)f(p, q)=p q+g(p, q). For pq0p q \neq 0 the second condition gives
pq+g(p,q)=1+12((p+1)(q1)+g(p+1,q1)+(p1)(q+1)+g(p1,q+1)), p q+g(p, q)=1+\frac{1}{2}((p+1)(q-1)+g(p+1, q-1)+(p-1)(q+1)+g(p-1, q+1)),
that is
g(p,q)=12(g(p+1,q1)+g(p1,q+1)). g(p, q)=\frac{1}{2}(g(p+1, q-1)+g(p-1, q+1)).
Hence the numbers g(0,p+q)g(0, p+q), g(1,p+q1),g(2,p+q2),,g(p+q1,1),g(p+q,0)g(1, p+q-1), g(2, p+q-2), \ldots, g(p+q-1,1), g(p+q, 0) form an arithmetic sequence. Since its outer terms g(0,p+q)g(0, p+q) and g(p+q,0)g(p+q, 0) are equal to zero, every term of the sequence has the value zero. Consequently g(p,q)=0g(p, q)=0 for all nonnegative integers, and therefore f(p,q)=pqf(p, q)=p \cdot q is the only solution.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from de; metadata (topic, difficulty, ordering) added by this project.