一试训练题

解答

记 $d=b-a>0$，令 $I=\{c-a+1,\dots ,c-a+d\}$。这是含 $d$ 个正整数的区间，每个模 $d$ 余数恰有一个代表。设 $r(n)$ 是 $I$ 中满足 $r(n)\equiv n-a(\mathrm{mod}d)$ 的唯一整数，考虑候选

先验证递归。若 $n\le c<n+b$，则 $F(n+b)=n+d$。若 $n+d\le c$，由余数不变有 $F(n+d)=r(n)$；若 $n+d>c$，整数 $n+d-a$ 位于 $I$ 且同余于 $n-a$，所以仍有 $F(n+d)=r(n)$。

若 $n+b\le c$，令 $z=r(n+b)\in I$，则 $z\equiv n(\mathrm{mod}d)$。当 $z\le c$ 时，$F(z)=r(z)=r(n)$；当 $z>c$ 时，$z-a\ge c-a+1$，且 $z-a\le c-a+d$，故 $z-a\in I$ 并同余于 $n-a$，于是 $F(z)=z-a=r(n)$。两种大类都证明 $F(F(n+b))=F(n)$，候选确为正整数值解。

再证唯一性。高于 $c$ 的值已确定，从 $c$ 到1作向下归纳，假设大于 $n$ 的函数值均等于候选。内层输入 $n+b>n$，其值若按高端分支算，是 $n+d>n$；若按余数分支算，因 $n\le c-b<c-a$，其值至少 $c-a+1>n$。所以外层也只调用已知的较大输入，归纳唯一确定 $f(n)=F(n)$。

高端 $n>c$ 不可能为不动点。低端不动点必须属于 $I$，且由 $r(n)\equiv n-a$ 知必须有 $d\mid a$。若不整除则没有；若整除，$d\le a$，从而 $I$ 上端 $c-a+d\le c$，$I$ 的每个元素均满足 $r(n)=n$。故不动点数为

任给正整数 $h$，取 $(a,b,c)=(h,2h,2h+1)$ 得 $h$ 个；取 $(1,3,4)$ 得0个。因此参数变化时所有非负整数个数均可能。