查看数据源：59b73411b049650008cb66fb
设数列 $\{a_n\}$ 定义为 $a_1=1$，$$a_{n+1}=\begin{cases}a_n+n,&a_n\leqslant n,\\a_n-n,&a_n>n,\end{cases}n=1,2,\cdots.$$求满足 $a_r<r\leqslant3^{2017}$ 的正整数 $r$ 的个数．
【难度】
【出处】
2017年全国高中数学联赛A卷（二试）
【标注】
  • 数学竞赛
    >
    数列
    >
    数列不等式
  • 方法
    >
    思考方式
    >
    归纳
  • 方法
    >
    论述方式
    >
    数学归纳法
    >
    第一数学归纳法
  • 知识点
    >
    数列
    >
    数列的通项公式
    >
    求数列通项的不动点法
  • 方法
    >
    思考方式
    >
    递推与递归
【答案】
$\dfrac{3^{2017}-2019}2$
【解析】
先计算数列的前几项：\[\begin{array}{c|cccccccccccccccc} \hline
n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline
a_n&1&2&4&1&5&10&4&11&3&12&2&13&1&14&28&13 \\ \hline
& = & = & > & < & = & > &< &> &< &> &< &> &<&=&>&< \\ \hline
\end{array}\]归纳出
引理若 $a_r=r$，则对 $k=1,2,\cdots,r-1$，有\[\begin{split}a_{r+2k-1}&=2r+k-1>r+2k-1,\\ a_{r+2k}&=r-k<r+2k.\end{split}\]对 $k$ 进行归纳证明．
归纳基础当 $k=1$ 时，由于 $a_r=r\leqslant r$，根据定义，有\[\begin{split}a_{r+1}&=a_r+r=2r>r+1,\\
a_{r+2}&=a_{r+1}-(r+1)=r-1<r+2,\end{split}\]命题成立．
递推证明假设对某个 $k$（$1\leqslant k<r-1$）成立，则由定义\[\begin{split}a_{r+2k+1}&=a_{r+2k}+(r+2k)=2r+k>r+2k+1,\\
a_{r+2k+2}&=a_{r+2k+1}-(r+2k+1)=r-k-1<r+2k+2,\end{split}\]于是命题对 $k+1$ 也成立．
综上所述，引理得证．
根据引理，将所有满足 $a_r=r$ 的正整数 $r$ 从小到大排列为\[r_1,r_2,\cdots,r_n,\cdots,\]则有\[r_{n+1}=3r_n-1,n=1,2,\cdots.\]利用不动点法容易求得\[r_n=\dfrac 12\cdot 3^{n-1}+\dfrac 12,n\in\mathbb N^*.\]由于\[r_{2018}=\dfrac{3^{2017}+1}2<3^{2017}<\dfrac{3^{2018}+1}2=r_{2019},\]于是不超过 $3^{2017}$ 的正整数被如下分段\[r_1,r_2,\cdots,r_3,\cdots,r_4,\cdots,\cdots,\cdots,r_{2017},\cdots,r_{2018},\cdots,3^{2017},\]其中在 $r_k$ 和 $r_{k+1}$ 之间的数恰有一半满足 $a_r<r$，在 $r_{2018}$（这是一个偶数）到 $3^{2017}$ 中所有的偶数 $r$ 均满足 $a_r<r$，所有奇数 $r$ 均满足 $a_r>r$．因此满足条件的正整数 $r$ 的个数为\[\dfrac 12\left(3^{2017}-2018-1\right)=\dfrac{3^{2017}-2019}2.\]
答案 解析 备注
0.107827s