Maths Olympiad Prep

Library / /14 of 17

Algebra Difficulty 6.6 National olympiad Prove it Croatia

Denote by N\mathbb{N} the set of all positive integers. Find all functions f:N×NNf: \mathbb{N} \times \mathbb{N} \to \mathbb{N} that satisfy the following conditions:
* f(a,b)+a+b=f(a,1)+f(1,b)+abf(a, b) + a + b = f(a, 1) + f(1, b) + ab holds for all positive integers aa and bb.
* If any number among a+ba + b and a+b1a + b - 1 is divisible by prime number p>2p > 2, then f(a,b)f(a, b) is divisible by pp as well. (Ivan Krijan)

Solution

Plugging (a,b)(1,1)(a, b) \leftarrow (1, 1) into the first given condition, we get f(1,1)=1f(1, 1) = 1.

On the other hand, by plugging (a,b)(a,b+1)(a, b) \leftarrow (a, b+1) we get
f(a,b+1)+a+b+1=f(a,1)+f(1,b+1)+ab+a. f(a, b + 1) + a + b + 1 = f(a, 1) + f(1, b + 1) + ab + a.
Using the first given condition in its original form, it follows that
f(a,b+1)f(a,b)=f(1,b+1)f(1,b)+a1. f(a, b + 1) - f(a, b) = f(1, b + 1) - f(1, b) + a - 1.
Let p>2p > 2 be a fixed prime number such that pa+bp \mid a+b, meaning that pf(a,b)p \mid f(a,b). Since pa+(b+1)1p \mid a+(b+1)-1, we also have pf(a,b+1)p \mid f(a,b+1). Therefore, pf(1,b+1)f(1,b)+a1p \mid f(1,b+1)-f(1,b)+a-1 and
pf(1,b+1)f(1,b)b1() p \mid f(1, b + 1) - f(1, b) - b - 1 \quad (*)
for all positive integers aa and bb, and primes p>2p > 2 such that pa+bp \mid a+b.
Note that the right-hand side in ()(*) does not depend on aa, hence fixing bb and varying aa would yield infinitely many odd prime divisors of f(1,b+1)f(1,b)b1f(1, b+1) - f(1, b) - b - 1, which is possible only if the latter equals 0, i.e.
f(1,b+1)=f(1,b)+b+1 f(1, b + 1) = f(1, b) + b + 1
for every positive integer bb.
Therefore, f(1,2)=f(1,1)+2=1+2f(1, 2) = f(1, 1) + 2 = 1 + 2, f(1,3)=f(1,2)+3=1+2+3f(1, 3) = f(1, 2) + 3 = 1 + 2 + 3, i.e. f(1,n)=1++n=n(n+1)2f(1, n) = 1 + \cdots + n = \frac{n(n+1)}{2} (by mathematical induction).
In a similar fashion, starting with (a,b)(a+1,b)(a, b) \leftarrow (a+1, b), we infer that f(n,1)=n(n+1)2f(n, 1) = \frac{n(n+1)}{2}.
Finally, from
f(a,b)+a+b=f(a,1)+f(1,b)+ab=a(a+1)2+b(b+1)2+ab, \begin{aligned} f(a, b) + a + b &= f(a, 1) + f(1, b) + ab \\ &= \frac{a(a + 1)}{2} + \frac{b(b + 1)}{2} + ab, \end{aligned}
it follows that f(a,b)=(a+b2)f(a, b) = \binom{a+b}{2}. This function clearly satisfies the second given condition, hence it is the only solution.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.