上述操作是否可以可以進行無限次

192557

已知a，b為正整數，開始時數軸的整點上一共有有限枚棋子。對任一整數k，若在k處有至少兩枚棋子，則可從后處取走兩枚棋子，再在k+a處和k-b處各放置一枚棋子，以上稱為一次操作。

上述操作是否可以可以進行無限次？

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,從任何初態開始,都不可能進行無限次操作.

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時，可以無限操作

208251

不可以