设 $m$ 是正整数，$n=2^m -1$，$P_n =\{1,2,\ldots,n\}$ 为数轴上 $n$ 个点所成的集合．一个蚱蜢在这些点上跳跃，每步从一个点跳到与之相邻的点．求 $m$ 的最大值，使对任意 $x,y\in P_n$，从点 $x$ 跳 $2012$ 步到点 $y$ 的跳法种数为偶数（允许中途经过点 $x,y$）．
【难度】
【出处】
2012中国东南数学奥林匹克试题
【标注】
【答案】
略
【解析】
当 $m\geqslant 11$ 时，$n=2^m -1>2013$，由于从点 $1$ 跳 $2012$ 步而到达点 $2013$ 的跳法只有一种，矛盾!所以 $m\leqslant 10$．
下证 $m=10$ 满足题意．为此，我们对 $m$ 用数学归纳法证明一个更强的命题：
对任意 $k\geqslant n=2^m -1$ 及任意 $x,y\in P_n$，从点 $x$ 跳 $k$ 步到点 $y$ 的跳法种数为偶数．
当 $m=1$ 时，跳法种数必为 $0$，结论成立．
设 $m=l$ 时结论成立，对 $k\geqslant n=2^{l+1}-1$，将从点 $x$ 跳 $k$ 步到点 $y$ 的路径分成 $3$ 类，我们证明每种情况下的路径种数均为偶数即可．
（1）路径从不经过点 $2^{l}$．
此时，点 $x$ 和点 $y$ 位于点 $2^l$ 的同侧，由归纳假设知，路径有偶数种．
（2）路径经过点 $2^l$ 恰一次．
设第 $i$ 步跳到点 $2^l(i\in\{0,1,\ldots,k\}$，$i=0$ 表示点 $x$ 就是点 $2^l$，$i=k$ 表示点 $y$ 就是点 $2^l$），我们证明对任意 $i$，路径种数都是偶数．
设路径为 $x,a_1 ,\ldots,a_{i-1},2^l ,a_{i+1},\ldots,a_{k-1},y$，将其分为两条子路：从点 $x$ 到点 $a_{i-1}$，共 $i-1$ 步；从点 $a_{i+1}$ 到点 $y$，共 $k-i-1$ 步（对 $i=0$ 或 $k$，只有一条子路，共 $k-1$ 步）．
因为 $k\geqslant n=2^{l+1}-1$，若 $i-1<2^l -1$ 且 $k-i-1<2^l -1$，则 $i-1\leqslant 2^l -2$ 且 $k-i-1\leqslant 2^l -2$，相加得：
$k\leqslant 2^{l+1}-2$，矛盾!所以 $i-1\geqslant 2^l-1$ 或 $k-i-1\geqslant 2^l -1$ 必有一个成立，由归纳假设，必有一条子路的路径种数为偶数，由乘法原理即知：第 $i$ 步跳到点 $2^l$ 的路径种数为偶数．
（3）路径经过点 $2^l$ 不少于两次．
此时将第一次与第二次到点 $2^l$ 之间的路径沿点 $2^l$ 作对称，则对（3）中的路径进行了两两配对，必为偶数种路径．
由数学归纳法，命题得证．
综上所述，$m$ 的最大值为 $10$．
下证 $m=10$ 满足题意．为此，我们对 $m$ 用数学归纳法证明一个更强的命题：
对任意 $k\geqslant n=2^m -1$ 及任意 $x,y\in P_n$，从点 $x$ 跳 $k$ 步到点 $y$ 的跳法种数为偶数．
当 $m=1$ 时，跳法种数必为 $0$，结论成立．
设 $m=l$ 时结论成立，对 $k\geqslant n=2^{l+1}-1$，将从点 $x$ 跳 $k$ 步到点 $y$ 的路径分成 $3$ 类，我们证明每种情况下的路径种数均为偶数即可．
（1）路径从不经过点 $2^{l}$．
此时，点 $x$ 和点 $y$ 位于点 $2^l$ 的同侧，由归纳假设知，路径有偶数种．
（2）路径经过点 $2^l$ 恰一次．
设第 $i$ 步跳到点 $2^l(i\in\{0,1,\ldots,k\}$，$i=0$ 表示点 $x$ 就是点 $2^l$，$i=k$ 表示点 $y$ 就是点 $2^l$），我们证明对任意 $i$，路径种数都是偶数．
设路径为 $x,a_1 ,\ldots,a_{i-1},2^l ,a_{i+1},\ldots,a_{k-1},y$，将其分为两条子路：从点 $x$ 到点 $a_{i-1}$，共 $i-1$ 步；从点 $a_{i+1}$ 到点 $y$，共 $k-i-1$ 步（对 $i=0$ 或 $k$，只有一条子路，共 $k-1$ 步）．
因为 $k\geqslant n=2^{l+1}-1$，若 $i-1<2^l -1$ 且 $k-i-1<2^l -1$，则 $i-1\leqslant 2^l -2$ 且 $k-i-1\leqslant 2^l -2$，相加得：
$k\leqslant 2^{l+1}-2$，矛盾!所以 $i-1\geqslant 2^l-1$ 或 $k-i-1\geqslant 2^l -1$ 必有一个成立，由归纳假设，必有一条子路的路径种数为偶数，由乘法原理即知：第 $i$ 步跳到点 $2^l$ 的路径种数为偶数．
（3）路径经过点 $2^l$ 不少于两次．
此时将第一次与第二次到点 $2^l$ 之间的路径沿点 $2^l$ 作对称，则对（3）中的路径进行了两两配对，必为偶数种路径．
由数学归纳法，命题得证．
综上所述，$m$ 的最大值为 $10$．
答案
解析
备注
