2025年上海预赛第11题的优雅三进制做法

解答：

（1）

若f(1)=1，则3=f(f(1))=f(1)=1，矛盾．

若f(1)≥3，则f(3)>f(1)≥3，3=f(f(1))≥f(3)>3，矛盾．

于是f(1)=2，f(2)=f(f(1))=3．

（2）

先给出一个满足题意的f(n)，在三进制下考虑：

• 若n的首位为1，则f(n)为将n的首位改为2所得的数；
• 若n的首位为2，则f(n)为将n的首位改为1，并在末尾加一个0所得的数．

容易验证这样的f(n)严格递增，且满足f(f(n))=3n，∀n∈N^(∗)．

（如果是填空题，我们已经可以不负责任地直接写出答案来了。）

注：由上可求得f(n)的一个通项公式

正片结束

严谨起见，我们再证明满足题意的f(n)至多只有一个：

由f(3n)=f(f(f(n)))=3f(n)．

若f(k)=n，f(k+1)=n+1，则

于是f(3k+1)=3n+1，f(3k+2)=3n+2．

即若f(k),f(k+1)为连续正整数，则f(3k),⋯,f(3k+3)也为连续正整数．

又由（1）知，f(1),f(2)为连续正整数，可以归纳证明，所有的f(k)均唯一确定．

事实上，写到这里，原题基本也就做出来了…所以单从考试角度来看，三进制这个方法是不必要的，但这并不影响方法本身的优雅。