【附】为方便有需要者编辑,特附纯文本如后。另外,文末提供有PPT照片版。


【代数6-3】有n只棋子被分成若干堆,今对状态进行如下操作:从每一堆中各取出一只棋,然后将取出的棋合在一起组成一个新的堆。每次操作后,各堆棋的棋子数按由大到小的顺序排成的数列称为n只棋的一种分布状态。如果存在r个不同的分布状态A1,A2,…,Ar,其中状态Ai操作一次之后变成状态Ai+1(i=1,2,…,r,规定Ar+1=A1),则称这r个状态构成一个循环圈,记为:A1→A2→…→Ar→A1,其中r称为该循环圈的长度。

对n只棋的所有不同的初始状态,记操作中出现的所有不同循环圈的个数为g(n)。

(1)求出所有的正整数n,使g(n)=1。

(2)求出所有的正整数n,使g(n)=2。(原创题)

【题感】先将问题转化为方格模型,由“代数6-2”的结论可知(称为“引理”),当n=

+q(0≤q

由此可见,只需考虑第k+1条对角线上q只棋的各种分布即可。

对于问题(1),要求使g(n)=1的n,属于循环圈的唯一性问题,宜从反面入手:去掉那些至少有两个循环圈的情形即可。

此外,为了将n表成“n=+q(0≤q

【划分序列】对给定的正整数n,必存在正整数k,使≤n<,设n=+q,其中0≤q

由“代数6-2”的结论,不论q(0≤q

由题意,g(n)=1,即循环圈的唯一存在。这等价于操作进入循环圈后,第k+1条对角线上的q只棋在第k+1条对角线上本质上只有唯一的放法。

从极端考虑,不难发现:当q很小或很大的时候,q只棋在第k+1条对角线上本质上只有唯一的放法。

【极端思考】q最小可取0,此外q=1也很小;当q取最大时,q=k,下面证明这三种情形都合乎要求。

(1)当q=0时,所有棋子布满了前k条对角线,而第k+1条对角线上没有棋。此时,只存在长为1的循环圈(1,2,…,k)→(1,2,…,k)→…,n显然合乎要求;

(2)当q=1时,虽然第k+1条对角线上的1只棋有k+1种放法,但每一种放法都可以由第一种放法轮换得到,从而本质上只有唯一的放法,n合乎要求;

(3)当q=k时,可采用“补集思考”:在第k+1条对角线上放k只棋,等价于在第k+1条对角线上放一个空格,由上一种情形可知,n合乎要求。

下面考虑2≤q

【反面剔除】当2≤q

进一步,可从“补集思考”:用“空格”将棋子段隔开,存在两种不同隔开方式即可。

为此,先估计第k+1条对角线上空格的个数(便于用它进行分隔)。

(4)当2≤qq≥2,从而k≥3,于是,第k+1条对角线上有k+1≥4个方格,其中至多放k-1只棋,于是至少有2个空格。

现在用这两个空格进行不同的分隔,这是很简单的。

方案1:将q只棋放在第k+1条对角线的连续q个方格中;

方案2:将q-1只棋放在第k+1条对角线上最前面的连续q-1个方格中,第q个方格不放棋,而第q+1个方格放棋。

这两种放法得到的循环圈显然不同,于是g(n)≥2,此时n不合乎要求。

【结论】所有合乎要求的n为,+1,+k(k∈N)。

下面考虑问题(2):求出所有的正整数n,使g(n)=2。

同样可从反面考虑,去掉g(n)=1及g(n)>2的情形。这并不是说“g(n)>2”包含的n少一些,而是它方便构造反例。

此外,为了利用前面的“引理”,同样先设n=+q(0≤q

【反面思考】设n=+q(0≤q

下面设n=+q(2≤q

【反面剔除】构造反例,找到适当的初始状态,使g(n)>2。

【补集思考】用“空格”将棋子段隔开,只需有3种不同隔开方式即可。

考察“空格”的位置,自然想到3种不同分布是:(i)空格连排;(ii)空格“1+多”分布;(iii)空格“2+多”分布,其中的“多”表示至少两个空格。

这就要求空格总数至少为4。由此想到,当q很小时(空格很多),构造是容易成的。

【极端入手】当q=2时,由于需要至少4个空格,从而第k+1条对角线上需要有至少6个方格,即k+1≥6,解得k≥5。此时,n≥+2=17。

这表明,n≤16时,需要另外讨论。

【优化假设】设n≥17,则+2≥17,解得k≥5。

此时,第k+1条对角线上至少6个方格,所以至少4个空格。

构造循环圈中第k+1条对角线上如下三种不同状态:

(i)(棋棋);(ii)(棋空棋);(iii)(棋空空棋)。

由于这三种状态中空格的分布不同,所以对应的循环圈不同,有g(n)≥3,所以n=

+2(k≥5)不合乎要求。

注意到q=3也较小,所以n=+3时,其构造与上类似。同样,为了保证至少4个空格,需要

+3≥17,解得k≥5。

构造循环圈中第k+1条对角线上如下三种不同状态:

(i)(棋棋棋);(ii)(棋棋空棋);(iii)(棋空棋棋)。

由于这三种状态中空格的分布不同,所以对应的循环圈不同,有g(n)≥3,所以n=

+3(k≥5)不合乎要求。

下面考虑q≥4的情形,此时第k+1条对角线上棋子很多。

但q

可以将这些空格分为固定的非空两段,用这两段将棋子分隔成不同形式即可。

当4≤q

(i)();(ii)(空棋);(iii)(空棋棋)。

由于这三种状态中棋子的分布不同,所以对应的循环圈不同,有g(n)≥3,所以n=

+q(k≥5,q≥4)不合乎要求。

下面讨论n≤16的情形,这采用穷举方法,剔除不合乎要求的即可。

比如,先剔除n=+q(q=0、1、k)的情形。

【穷举剔除】当n≤16时,由于2=1+1,3=1+2,4=(1+2)+1,5=(1+2+3)-1,6=1+2+3,7=(1+2+3)+1,9=(1+2+3+4)-1,10=1+2+3+4,11=(1+2+3+4)+1,14=(1+2+3+4+5)-1,15=1+2+3+4+5,16=(1+2+3+4+5)+1,由(1)的结论,都有g(n)=1,所以n不合乎要求。

最后还剩下三种情形:n=8、12、13。容易证明,它们都合乎要求,证明如下:

(1)当n=8时,因为8=(1+2+3)+2,当操作进入循环圈后,第4条对角线上有2只棋。

这2只棋在第4条对角线上本质上恰有2种放法:(棋棋空空),(棋空棋空),所以n=8合乎要求。

(2)当n=12时,因为12=(1+2+3+4)+2,当操作进入循环圈后,第5条对角线上有2只棋。

这2只棋在第5条对角线上本质上恰有2种放法:(棋棋空空空),(棋空棋空空),其中注意(棋空棋空空)可以轮换得到(棋空空棋空),所以n=12合乎要求。

(3)当n=13时,因为13=(1+2+3+4)+3,当操作进入循环圈后,第5条对角线上有3只棋。

这3只棋在第5条对角线上本质上恰有2种放法:(棋棋棋空空),(棋棋空棋空),其中注意(棋棋空棋空)可以轮换得到(棋空棋棋空),所以n=13合乎要求。

综上所述,合乎要求的n=8、12、13。

【未决问题】对给定的正整数k,求正整数n,使g(n)=k。

这个问题容量很大,期待大家能得出相关结论。

【新写】先将问题转化为方格模型,并设n=+q,其中0≤q

(1)当g(n)=1时,即循环圈的唯一存在。

当q=0时,只存在长为1的循环圈(1,2,…,k),n合乎要求;

当q=1时,第k+1条对角线上的1只棋本质上只有唯一的放法,n合乎要求;

当q=k时,第k+1条对角线上放一个空格,由上一种情形可知,n合乎要求。

当2≤q

方案1:将q只棋放在第k+1条对角线的连续q个方格中;

方案2:将q-1只棋放在第k+1条对角线上最前面的连续q-1个方格中,第q个方格不放棋,而第q+1个方格放棋。

这两种放法得到的循环圈显然不同,于是g(n)≥2,此时n不合乎要求。

所有合乎要求的n为,+1,+k(k∈N)。

(2)当g(n)=2时,同样设n=+q(0≤q

当n≥17时,k≥5。此时,第k+1条对角线上至少6个方格,至少4个空格。

当q=2时,构造循环圈中第k+1条对角线上如下三种不同状态:

(i)(棋棋);(ii)(棋空棋);(iii)(棋空空棋)。

当q=3时,构造循环圈中第k+1条对角线上如下三种不同状态:

(i)(棋棋棋);(ii)(棋棋空棋);(iii)(棋空棋棋)。

由于这样的三种状态中空格的分布不同,所以对应的循环圈不同,有g(n)≥3,所以n=

+q(k≥5、q=2、3)不合乎要求。

当4≤q

(i)();(ii)(空棋);(iii)(空棋棋)。

由于这三种状态中棋子的分布不同,所以对应的循环圈不同,有g(n)≥3,所以n=

+q(k≥5,q≥4)不合乎要求。

当n≤16时,由于2=1+1,3=1+2,4=(1+2)+1,5=(1+2)+2,6=1+2+3,7=(1+2+3)+1,9=(1+2+3)+3,10=1+2+3+4,11=(1+2+3+4)+1,14=(1+2+3+4)+4,15=1+2+3+4+5,16=(1+2+3+4+5)+1,由(1)的结论,都有g(n)=1,所以n的这些取值都不合乎要求。

当n=8时,因为8=(1+2+3)+2,当操作进入循环圈后,第4条对角线上有2只棋。

这2只棋在第4条对角线上本质上恰有2种放法:(棋棋空空),(棋空棋空),所以n=8合乎要求。

当n=12时,因为12=(1+2+3+4)+2,当操作进入循环圈后,第5条对角线上有2只棋。

这2只棋在第5条对角线上本质上恰有2种放法:(棋棋空空空),(棋空棋空空),其中注意(棋空棋空空)可以轮换得到(棋空空棋空),所以n=12合乎要求。

当n=13时,因为13=(1+2+3+4)+3,当操作进入循环圈后,第5条对角线上有3只棋。

这3只棋在第5条对角线上本质上恰有2种放法:(棋棋棋空空),(棋棋空棋空),其中注意(棋棋空棋空)可以轮换得到(棋空棋棋空),所以n=13合乎要求。

综上所述,合乎要求的n=8、12、13。