【附】为方便有需要者编辑,特附纯文本如后。另外,文末提供有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≤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):求出所有的正整数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。