## T-1

Let $\mathbb{Z}$ denote the set of all integers and $\mathbb{Z}_{>0}$ denote the set of all positive integers.

(a) A function $f: \mathbb{Z} \rightarrow \mathbb{Z}$ is called $\mathbb{Z}$-good if it satisfies $f\left(a^{2}+b\right)=f\left(b^{2}+a\right)$ for all $a, b \in \mathbb{Z}$. Determine the largest possible number of distinct values that can occur among $f(1), f(2), \ldots, f(2023)$, where $f$ is a $\mathbb{Z}$-good function.

(b) A function $f: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$ is called $\mathbb{Z}_{>0}$ good if it satisfies $f\left(a^{2}+b\right)=f\left(b^{2}+a\right)$ for all $a, b \in \mathbb{Z}_{>0}$. Determine the largest possible number of distinct values that can occur among $f(1), f(2), \ldots, f(2023)$, where $f$ is a $\mathbb{Z}_{>0^{0}}$ good function.


Solution. The answer is (a) 2 and (b) 1077.

(a) Note that

$$
f\left(a^{2}+b\right)=f\left(b^{2}+a\right)=f\left((-b)^{2}+a\right)=f\left(a^{2}-b\right)
$$

In particular, by setting $a \in\{0,1\}$ we get $f(b)=f(-b)$ and $f(1+b)=f(1-b)$. This then yields

$$
f(2+b)=f(1+(1+b))=f(1-(1+b))=f(-b)=f(b)
$$

hence by induction the function must be constant on even integers and (separately) on odd integers. On the other hand, a function $f(n)=n(\bmod 2)$ satisfies the requirements and attains 2 distinct values on $\{1, \ldots, 2023\}$.

(b) Given two positive integers $mb>0$. Then either $n=a, k=b$ (in which case we obtain a parent $k^{2}+na$, a contradiction.

(d) For any $n \geq 2$, the $n+2$ numbers in $B_{n}=\left\{n^{2}+n, \ldots, n^{2}+2 n+1\right\}$ do not have a parent: Let $n \leq k \leq 2 n+1$ and assume that $n^{2}+k=a^{2}+b$ with $a>b>0$. Since $n^{2}+k<(n+1)^{2}+1$, we must have $a \leq n$ but then $b \geq k \geq n \geq a$, a contradiction.

Note that as $n \in \mathbb{N}$ varies, the sets $A_{n}, B_{n}$ form a partition of $\mathbb{N} \backslash S$, hence each positive integer has at most one parent. In other words, if we process the positive integers in increasing order, for any currently processed integer $n$ there will always be at most one parent, and thus at most one requirement on which value to assign to $f(n)$. Therefore, as we process the integers, to any
integer $n$ without a parent we can always safely assign any value $f(n)$. (Clearly, when $n$ has a parent $m$, we must assign $f(n)=f(m)$.) The answer is the number of integers $n \in\{1, \ldots, 2023\}$ with no parent. Since $2023=44^{2}+87$, this is

$$
|S|+\left(\sum_{i=2}^{43}(i+2)\right)+(87-44+1)=1077
$$

Comment. It is possible to ask only for the answer to the part (b).

