2022 年广西预赛

解答

先证每个 $f(n)$ 都是正整数且为 $3$ 的倍数。初始项满足；加 $3$ 分支显然保持。若 $f(n)=s^2$ 且 $3\mid f(n)$，则 $3\mid s$，所以开平方分支也保持。

取 $M=9a^2=(3a{)}^2$。初始时 $a\le M$。若 $f(n)$ 是完全平方数，则

若 $f(n)$ 不是完全平方数，由于 $f(n)$ 与 $M$ 都是 $3$ 的倍数，而 $M$ 自身是完全平方数，必有

故 $f(n+1)=f(n)+3\le M$。归纳完成。