上述操作是否可以可以進(jìn)行無(wú)限次

192557

已知a，b為正整數(shù)，開(kāi)始時(shí)數(shù)軸的整點(diǎn)上一共有有限枚棋子。對(duì)任一整數(shù)k，若在k處有至少兩枚棋子，則可從后處取走兩枚棋子，再在k+a處和k-b處各放置一枚棋子，以上稱(chēng)為一次操作。

上述操作是否可以可以進(jìn)行無(wú)限次？

22568

鑒于lz題目(似乎)有筆誤,先澄清下我理解的題意:

1. 一次操作,表示從某k處取走兩枚棋子,分別放在k+a處和k-b處.

復(fù)制代碼

下面回到原題.
先考慮一個(gè)小結(jié)論:

1. 對(duì)于任何一個(gè)初態(tài),通過(guò)進(jìn)行任意多次操作并不能使棋子延伸出無(wú)限的距離.

復(fù)制代碼

確切地,考慮任何一個(gè)初態(tài),記所有棋子坐標(biāo)的最小最大值分別為m和M,那么存在一個(gè)上界L,使得無(wú)論如何進(jìn)行若干次操作后,所有棋子都永遠(yuǎn)不能超出范圍m-L~M+L.

顯然,如果這個(gè)上界L存在,那這個(gè)L一定與棋子數(shù)k相關(guān),也一定與a和b相關(guān).
事實(shí)上,我們希望這個(gè)上界L僅與k,a,b相關(guān),而與具體初態(tài)無(wú)關(guān).
換句話(huà)說(shuō),我們希望證明存在一個(gè)函數(shù)L[k,a,b],使得對(duì)任意一個(gè)由k枚棋子組成的初態(tài)(記其所有棋子的坐標(biāo)的最小最大值分別為m和M),無(wú)論如何進(jìn)行若干次操作后,都不可能有棋子超出范圍m-L[k,a,b]~M+L[k,a,b].
(本題中的a,b是定值,故為方便表述,以下提及函數(shù)L時(shí)將省略參數(shù)a,b.)

下面我們用歸納法證明引理:

1. 存在一個(gè)遞增正整數(shù)列{L[k]},使得命題P[k]對(duì)所以正整數(shù)k都成立.

復(fù)制代碼

其中命題P[k]為

1. 對(duì)任意一個(gè)由k枚棋子組成的初態(tài)(記其所有棋子坐標(biāo)的最小最大值分別為m和M),無(wú)論如何進(jìn)行若干次操作后,都不可能有棋子超出范圍m-L[k]~M+L[k].

復(fù)制代碼

奠基顯然.
下設(shè)對(duì)某正整數(shù)k>1,對(duì)所有正整數(shù)i<k,命題P[i]都成立.考慮命題P[k].

對(duì)任意一個(gè)由k枚棋子組成的初態(tài),記A=(k-1)(2L[k-1]+1),考慮棋子是否能超出范圍m-A~M+A.
若對(duì)所有初態(tài),棋子都不能超出,那么L[k]=A=(k-1)(2L[k-1]+1)即為所求;
否則,假設(shè)對(duì)于某個(gè)初態(tài),若經(jīng)過(guò)若干次操作后棋子能超出該范圍.

注意到,局面在經(jīng)過(guò)操作時(shí),"所有棋子坐標(biāo)最小值"不增,"所有棋子坐標(biāo)最大值"不減;
故此時(shí)所有棋子坐標(biāo)的最大值和最小值之差必超過(guò)A+(M-m).
于是,必有兩個(gè)相鄰棋子的距離超過(guò)A/(k-1)>=2L[k-1]+1.
也就是說(shuō),此時(shí)棋子被一段長(zhǎng)度>=2L[k-1]+1的空白分成兩部分.
由引理,兩邊都最多延伸出L[k-1],它們無(wú)法跨越該空白區(qū)域或在空白區(qū)域中相遇,兩部分已無(wú)法再相互影響.
綜上,L[k]=A+L[k-1]=(2k-1)L[k-1]+k-1即滿(mǎn)足要求.引理得證.


下面再次回到原題.
假設(shè)存在某個(gè)初態(tài),由其開(kāi)始可進(jìn)行無(wú)限次操作.
由引理,存在上下界,使得棋子無(wú)法超出這個(gè)范圍.
由于"所有棋子坐標(biāo)最小值"不增,"所有棋子坐標(biāo)最大值"不減,故最終棋子坐標(biāo)的最大最小值將不再改變.
換句話(huà)說(shuō),最左最右棋子均不再參與操作,將之去掉后僅考慮剩下的棋子,也應(yīng)當(dāng)可以繼續(xù)進(jìn)行無(wú)限次操作.
顯然這是不可能的.(最小性/無(wú)窮遞降即可)

故對(duì)于原題,對(duì)任何a,b,從任何初態(tài)開(kāi)始,都不可能進(jìn)行無(wú)限次操作.

198210

顯然，對(duì)任意k，其后的棋子是否在同一整數(shù)不影響操作。
①當(dāng)存在某整數(shù)k上有2枚棋子，k處后只有2個(gè)棋子m,n (m≤n＜k且為整數(shù))時(shí)，操作1次，變?yōu)椋琸-b(1) ,k(2), k+a(1)，無(wú)法繼續(xù)操作。故存在整數(shù)k上有2枚棋子，k處后只有2個(gè)棋子m,n 僅能操作1次。
②當(dāng)k處后有3個(gè)棋子m,n, p (m≤n≤p＜k且為整數(shù))
操作1次，變?yōu)閙, k-b(1),k(2),k+a(1); 操作2次，即k-b(1), k(2), k+a(2)，
操作2次后，已存在對(duì)于（k+a）處有兩個(gè)棋子，（k+a）處后有3個(gè)棋子，使其能進(jìn)行同②操作2次，其后同理。故當(dāng)k處后有3個(gè)棋子m,n, p (m≤n≤p＜k且為整數(shù))，可以無(wú)限操作。k處后有3個(gè)以上棋子顯然可以無(wú)限操作。
綜上，當(dāng)k處后棋子數(shù)≤2時(shí)，僅能操作1次；當(dāng)k處后棋子數(shù)≥3時(shí)，可以無(wú)限操作

208251

不可以