BdMO 2021 problem: Find smallest $f(25)$ such that $f(m)+f(n)>\max(m^2,n^2)$ and $f(1)+f(2)+\cdots+f(30)$ is minimized

Question

Here is a problem from BdMO 2021 (From Higher Secondary):

A function $g:\mathbb{Z}\to\mathbb{Z}$ is called adjective if $g(m)+g(n)>\max{(m^2,n^2)}$ for any pair of integers $m$ and $n$. Let $f$ be an adjective function such that the value of $f(1)+f(2)+f(3)+\cdots+f(30)$ is minimized.
1. How many $f$s are there? (Assume $f:[1,30]\rightarrow\mathbb{Z}$)
2. Find the smallest possible value of $f(25)$.

My approach:
1. There are infinitely many $f$s (for $f:\mathbb{Z}\rightarrow\mathbb{Z})$.
2. $$f(0)+f(30)>\max(0,30^2)\implies{f(0)+f(30)>900}$$ Since $f(1)+f(2)+f(3)+\cdots+f(30)$ is minimized, we have $f(30)=901$ and $f(k)=k^2+1$ for all $k\in{\mathbb{Z}}$. So, we have $$f(25)=25^2+1=\boxed{626}.$$

---

I think there is nothing wrong in my process. But the problem is the last problem from a National Olympiad. And I believe the problem would not be so easy.
So, is my solution correct?

Answer 1

Let $G(g) = \sum_{i=1}^{30} g(i)$.
Clearly $ G(g) = \sum_{i=16}^{30} g(i) + g(31-i) \geq \sum_{i=16}^{30} (i^2 + 1)$ gives a lower bound.
Define this value as $ F$.
Since $g(n) = \begin{cases} 113 & n \in [1, 15] \\ n^2 - 112 & n \in [16, 30 ] \\ \end{cases}$ has this sum, thus $F$ is indeed the minimum.

Now, let's count the number of functions where $G(g) = F$.
Let $A = \min_{j \in [1, 15] } g(j) $ and $B = \min_{i \in [16, 30 ]} g(i) - i^2 $.
Then, by the conditions, $ A + B \geq 1.$
Notice that $ G = \sum_{i=16}^{30} g(i) + g(30-i) \geq B + i^2 + A = F$.
Hence, we need equality to hold throughout, which means

• $ g(1) = g(2) = \ldots = g(15) = k $
• $g(i) = i^2 - k+1 $.

In addition, to satisfy the adjective conditions of $g(x)$, we also require

• $f(j_1) + f(j_2) \geq \max(j_1, j_2)^2 + 1 , j_1, j_2 \in [1, 15 ] \Rightarrow f(1) + f(15) \geq 15^2 + 1 \Rightarrow k \geq 113$
• $f(i_1) + f(i_2) \geq \max(i_1, i_2)^2 + 1 , i_1, i_2 \in [16, 30 ] \Rightarrow f(16) + f(16) \geq 16^2 + 1 \Rightarrow k \leq 128 $
• $f(i) + f(j) \geq j^2 + 1, i \in [16, 30], j \in [1, 15] $ is satisfied by construction.

Conversely, for any $ 113 \leq k \leq 128$, verify that the function $f_k(n) = \begin{cases} k & n \in [1, 15] \\ n^2 - k +1& n \in [16, 30 ] \\ \end{cases}$ satisfies the conditions.
Hence, there are $128-113+1=16$ such functions which minimize $F$.

The minimum value of $f(25)$ is thus $ 25^2 - 128+1 = 498$.

---

(With regards to the original phrasing. Edits have since been made.)

The question is poorly phrased for the following reasons.
I suspect it's a transcription error, and have explained the minor edit to the question that I'm making:

1. [OP edited question to be about $f$ instead, so this is fixed.]
   There are infinitely many $g$, like $g(n) = n^2 + k, k \geq 0$.
   Thus, for part 1, I will instead be counting the number of functions $f$ where the sum is minimized.

2. [OP edited question to fix this] There are infinitely many $g:\mathbb{Z} \rightarrow \mathbb{Z}$ that minimize $ \sum_{n=1}^{30} f(n)$, because we can set any value for $f(31)$. Hence, I will restrict the function to $ g: [1, 30] \rightarrow \mathbb{Z}$.

3. [I was wrong here. The function I defined isn't adjective.] There are infinitely many $g:[1, 30] \rightarrow \mathbb{Z}$ that minimize $ \sum_{n=1}^{30} f(n)$, like extend $f_k$ defined below to $f_k(-n) = f_k(n)$ for $ k \in \mathbb{Z}$.
   Thus, I will be solving for $ g:[1, 30] \rightarrow \mathbb{Z}^+$ instead.