上述操作是否可以可以进行无限次

192557

已知a，b为正整数，开始时数轴的整点上一共有有限枚棋子。对任一整数k，若在k处有至少两枚棋子，则可从后处取走两枚棋子，再在k+a处和k-b处各放置一枚棋子，以上称为一次操作。

上述操作是否可以可以进行无限次？

198210

显然，对任意k，其后的棋子是否在同一整数不影响操作。
①当存在某整数k上有2枚棋子，k处后只有2个棋子m,n (m≤n＜k且为整数)时，操作1次，变为，k-b(1) ,k(2), k+a(1)，无法继续操作。故存在整数k上有2枚棋子，k处后只有2个棋子m,n 仅能操作1次。
②当k处后有3个棋子m,n, p (m≤n≤p＜k且为整数)
操作1次，变为m, k-b(1),k(2),k+a(1); 操作2次，即k-b(1), k(2), k+a(2)，
操作2次后，已存在对于（k+a）处有两个棋子，（k+a）处后有3个棋子，使其能进行同②操作2次，其后同理。故当k处后有3个棋子m,n, p (m≤n≤p＜k且为整数)，可以无限操作。k处后有3个以上棋子显然可以无限操作。
综上，当k处后棋子数≤2时，仅能操作1次；当k处后棋子数≥3时，可以无限操作

22568

鉴于lz题目(似乎)有笔误,先澄清下我理解的题意:

1. 一次操作,表示从某k处取走两枚棋子,分别放在k+a处和k-b处.

复制代码

下面回到原题.
先考虑一个小结论:

1. 对于任何一个初态,通过进行任意多次操作并不能使棋子延伸出无限的距离.

复制代码

确切地,考虑任何一个初态,记所有棋子坐标的最小最大值分别为m和M,那么存在一个上界L,使得无论如何进行若干次操作后,所有棋子都永远不能超出范围m-L~M+L.

显然,如果这个上界L存在,那这个L一定与棋子数k相关,也一定与a和b相关.
事实上,我们希望这个上界L仅与k,a,b相关,而与具体初态无关.
换句话说,我们希望证明存在一个函数L[k,a,b],使得对任意一个由k枚棋子组成的初态(记其所有棋子的坐标的最小最大值分别为m和M),无论如何进行若干次操作后,都不可能有棋子超出范围m-L[k,a,b]~M+L[k,a,b].
(本题中的a,b是定值,故为方便表述,以下提及函数L时将省略参数a,b.)

下面我们用归纳法证明引理:

1. 存在一个递增正整数列{L[k]},使得命题P[k]对所以正整数k都成立.

复制代码

其中命题P[k]为

1. 对任意一个由k枚棋子组成的初态(记其所有棋子坐标的最小最大值分别为m和M),无论如何进行若干次操作后,都不可能有棋子超出范围m-L[k]~M+L[k].

复制代码

奠基显然.
下设对某正整数k>1,对所有正整数i<k,命题P[i]都成立.考虑命题P[k].

对任意一个由k枚棋子组成的初态,记A=(k-1)(2L[k-1]+1),考虑棋子是否能超出范围m-A~M+A.
若对所有初态,棋子都不能超出,那么L[k]=A=(k-1)(2L[k-1]+1)即为所求;
否则,假设对于某个初态,若经过若干次操作后棋子能超出该范围.

注意到,局面在经过操作时,"所有棋子坐标最小值"不增,"所有棋子坐标最大值"不减;
故此时所有棋子坐标的最大值和最小值之差必超过A+(M-m).
于是,必有两个相邻棋子的距离超过A/(k-1)>=2L[k-1]+1.
也就是说,此时棋子被一段长度>=2L[k-1]+1的空白分成两部分.
由引理,两边都最多延伸出L[k-1],它们无法跨越该空白区域或在空白区域中相遇,两部分已无法再相互影响.
综上,L[k]=A+L[k-1]=(2k-1)L[k-1]+k-1即满足要求.引理得证.


下面再次回到原题.
假设存在某个初态,由其开始可进行无限次操作.
由引理,存在上下界,使得棋子无法超出这个范围.
由于"所有棋子坐标最小值"不增,"所有棋子坐标最大值"不减,故最终棋子坐标的最大最小值将不再改变.
换句话说,最左最右棋子均不再参与操作,将之去掉后仅考虑剩下的棋子,也应当可以继续进行无限次操作.
显然这是不可能的.(最小性/无穷递降即可)

故对于原题,对任何a,b,从任何初态开始,都不可能进行无限次操作.

208251

不可以