Maths Olympiad Prep

Library / /31 of 37

Algebra Difficulty 8.3 Shortlist Find the answer

Consider pairs (f,g)(f,g) of functions from the set of nonnegative integers to itself such that
[list]
[*]f(0)f(1)f(2)f(300)0f(0) \geq f(1) \geq f(2) \geq \dots \geq f(300) \geq 0
[*]f(0)+f(1)+f(2)++f(300)300f(0)+f(1)+f(2)+\dots+f(300) \leq 300
[*]for any 20 nonnegative integers n1,n2,,n20n_1, n_2, \dots, n_{20}, not necessarily distinct, we have g(n1+n2++n20)f(n1)+f(n2)++f(n20).g(n_1+n_2+\dots+n_{20}) \leq f(n_1)+f(n_2)+\dots+f(n_{20}).
[/list]
Determine the maximum possible value of g(0)+g(1)++g(6000)g(0)+g(1)+\dots+g(6000) over all such pairs of functions.

[i]Sean Li[/i]

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

Solution

Consider pairs (f,g)(f, g) of functions from the set of nonnegative integers to itself such that:
- f(0)f(1)f(2)f(300)0f(0) \geq f(1) \geq f(2) \geq \dots \geq f(300) \geq 0,
- f(0)+f(1)+f(2)++f(300)300f(0) + f(1) + f(2) + \dots + f(300) \leq 300,
- for any 20 nonnegative integers n1,n2,,n20n_1, n_2, \dots, n_{20}, not necessarily distinct, we have g(n1+n2++n20)f(n1)+f(n2)++f(n20)g(n_1 + n_2 + \dots + n_{20}) \leq f(n_1) + f(n_2) + \dots + f(n_{20}).

We aim to determine the maximum possible value of g(0)+g(1)++g(6000)g(0) + g(1) + \dots + g(6000) over all such pairs of functions.

The answer is 115440\boxed{115440}. The construction achieving this maximum is given by:
f(x)=max(24x,0) f(x) = \max(24 - x, 0)
and
g(x)=max(480x,0). g(x) = \max(480 - x, 0).

This construction satisfies all the given conditions and achieves the maximum sum for g(0)+g(1)++g(6000)g(0) + g(1) + \dots + g(6000).

The answer is 115440\boxed{115440}.

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.