Maths Olympiad Prep

Library / /9 of 37

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

Find all functions f ⁣:Z2[0,1]f\colon \mathbb{Z}^2 \to [0, 1] such that for any integers xx and yy,
f(x,y)=f(x1,y)+f(x,y1)2.f(x, y) = \frac{f(x - 1, y) + f(x, y - 1)}{2}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let f ⁣:Z2[0,1] f \colon \mathbb{Z}^2 \to [0, 1] be a function such that for any integers x x and y y ,
f(x,y)=f(x1,y)+f(x,y1)2. f(x, y) = \frac{f(x - 1, y) + f(x, y - 1)}{2}.

We will prove that the only functions satisfying this condition are constant functions.

First, we use induction on n n to show that
f(x,y)=f(xn,y)+(n1)f(xn+1,y1)++(n1)f(x1,yn+1)+f(x,yn)2n. f(x, y) = \frac{f(x - n, y) + \binom{n}{1} f(x - n + 1, y - 1) + \cdots + \binom{n}{1} f(x - 1, y - n + 1) + f(x, y - n)}{2^n}.

Next, consider the function f(x1,y+1) f(x - 1, y + 1) :
f(x1,y+1)=f(x1n,y+1)+(n1)f(xn,y)++(n1)f(x2,yn+2)+f(x1,y+1n)2n. f(x - 1, y + 1) = \frac{f(x - 1 - n, y + 1) + \binom{n}{1} f(x - n, y) + \cdots + \binom{n}{1} f(x - 2, y - n + 2) + f(x - 1, y + 1 - n)}{2^n}.

Subtracting these two expressions, we get:
2n(f(x,y)f(x1,y+1))=f(x1n,y+1)+(1(n1))f(xn,y)+((n1)(n2))f(xn+1,y1)++((n1)1)f(x1,y+1n)+f(x,yn). 2^n \left( f(x, y) - f(x - 1, y + 1) \right) = f(x - 1 - n, y + 1) + \left( 1 - \binom{n}{1} \right) f(x - n, y) + \left( \binom{n}{1} - \binom{n}{2} \right) f(x - n + 1, y - 1) + \cdots + \left( \binom{n}{1} - 1 \right) f(x - 1, y + 1 - n) + f(x, y - n).

Since f(x,y)[0,1] f(x, y) \in [0, 1] , the right-hand side is bounded by (nn2) \binom{n}{\left\lfloor \frac{n}{2} \right\rfloor} . Thus,
2n(f(x,y)f(x1,y+1))(nn2). 2^n \left( f(x, y) - f(x - 1, y + 1) \right) \leq \binom{n}{\left\lfloor \frac{n}{2} \right\rfloor}.

For large n n , this inequality becomes impossible because 2n 2^n grows exponentially while (nn2) \binom{n}{\left\lfloor \frac{n}{2} \right\rfloor} grows polynomially. Therefore, we must have f(x,y)=f(x1,y+1) f(x, y) = f(x - 1, y + 1) .

From the initial equation, it follows that f(x,y)=f(xn,y)=f(x,yn) f(x, y) = f(x - n, y) = f(x, y - n) for all n n . Hence, f(x,y) f(x, y) must be constant for all (x,y)Z2 (x, y) \in \mathbb{Z}^2 .

Thus, the only functions f ⁣:Z2[0,1] f \colon \mathbb{Z}^2 \to [0, 1] that satisfy the given condition are constant functions. Therefore, the answer is:
f(x,y)=C for some constant C[0,1]. \boxed{f(x, y) = C \text{ for some constant } C \in [0, 1]}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.