一个裁纸计数问题的解决

朱玉扬

(1.亳州学院电子与信息工程系 236800；2.合肥学院人工智能与大数据学院 230601)

将一张矩形的纸张对折n次后，用刀沿着折痕裁它，每次裁后不准将其重叠再裁，即每次裁后不准改变纸张的位置，那么，至少要裁多少刀才可以将纸张裁成2n张小纸片？为解决这一问题，先看下表：

表1 裁纸张数分布表

定理1将一张矩形的纸张对折n次后，用刀沿着折痕裁它，每次裁后不准改变纸张的位置，将其裁成2n张小纸片，那么最少要裁的刀数为

证明记对折n次后需裁得刀数为f(n). 我们知道，对折n次，最后一道折痕即是最厚的一道折痕，它所对应的一边需裁1刀，倒数第二道折痕即是次厚的折痕，它所对应的一边需裁2刀.

不妨令折痕最厚的边为“下边”，折痕次厚的边为“右边”，故“下边”需裁1刀，“右边”需裁2刀，而所折纸块的另两边即“上边”与“左边”所需裁的最少刀数分别设为an-2与bn-2，所以f(n)等于各边最少刀数之和，即f(n)=1+2+an-2+bn-2.

下面我们来考虑数列{an}与{bn}之间的关系.

当n=k+2(k∈N+)时，由上面所设知“上边”所需裁的最少刀数为ak，“左边”所需裁的最少刀数为bk，而“下边”所需裁的最少刀数为1刀，“右边”所需裁的最少刀数为2刀(见图1(i)).

当n=k+3时，我们可逆向考虑. 如图1(ii)，将原先所折纸张沿着虚线L对折，则图1(i)变为图1(ii)：

图1(i)

图1(ii)

即有ak+1=2(ak-1+1). (1)

因a0=0,a1=2，由(1)式易证a2k-1=a2k(k∈N+). 事实上k=1时，a0=0,a1=2，由(1)式得a2=2(a0+1)=2，即k=1时，有a2k-1=a2k. 假设k=s(s≥1,s∈N+)时有a2s-1=a2s，那么k=s+1时，有

(2)

由假设知a2s-1=a2s，由(2)两式即得a2(s+1)-1=a2(s+1)，由数学归纳法原理即知a2k-1=a2k(k∈N+).

再令tk=a2k-1=a2k(k∈N+)，由(1)式得tk+1=2(tk+1)，即得tk+1+2=2(tk+2)，因此递归得tk+1+2=2(tk+2)=22(tk-1+2)

=…=2k(t1+2)，

而t1=a1=2，因此

tk+1+2=2k(t1+2)=2k+2⟹tk+1=2k+2-2.

故当n≥3时，f(n)=3+an-2+bn-2

=3+an-2+2an-3，

而tk=a2k-1=a2k，

所以当n为奇数时

当n为偶数时

f(n)=3+an-2+2an-3

故当n≥3时有

另一方面，当n=1,2时，因f(1)=1，f(2)=3，即上式也成了，故对一切自然数n(n≥1)，上式皆成立. 证毕.

实际上，我们有如下统一的公式.

定理1′将一张矩形的纸张对折n次后，用刀沿着折痕裁它，每次裁后不准改变纸张的位置，将其裁成2n张小纸片，那么最少要裁的刀数为

(n=1,2,3,…)

证明由递归关系(1)知

ak+1=2(ak-1+1)，即ak+1-2ak-1-2=0，

此是一个常系数线性非齐次的递归关系，非齐次项为-2，所以有特解[1]f(n)=a，

代入递归关系ak+1-2ak-1-2=0得

a-2a-2=0，即a=-2.

而齐次项对应的递归关系是ak+1-2ak-1=0，

对应的特征方程为x2-2=0，

从而递归关系(1)的通解为齐次的通解加特解，即

由于a0=0,a1=2，因此有

由前面定理的证明知bk+1=2ak，

即bn=2an-1，故

再根据定理的证明知

对于等腰直角三角形每次沿着底边上的高对折，用刀沿着折痕裁它，每次裁后不准改变纸张的位置，将其裁成2n张小纸片，那么最少要裁的刀数是什么？用类似的方法，我们有下面的结论：

定理2将一张等腰直角三角形的纸张每次沿着底边上的高对折n次后，用刀沿着折痕裁它，每次裁后不准改变纸张的位置，将其裁成2n张小纸片，那么最少要裁的刀数为

证明对于一个等腰直角三角形，每次沿着底边上的高对折n次后，得到2n个重叠在一起的小等腰直角三角形，每次裁都不改变它们原来的位置，设其底部需裁的最少刀数为Bn，左边需裁的最少刀数为Ln，右边需裁的最少刀数为Rn. 由于每次对折后总有一直角边只需裁一刀即可(即是最厚的一道折痕)，设这个直角边总为左边，故Ln=1. 另一方面，每次都是沿着底边上的高对折，因此折痕沿原三角形的底边的中点，从而原三角形底边从中点对折重叠形成新等腰直角三角形，新的等腰直角三角形的一个直角边即是原三角形底边重叠形成的，这个直角边即是新的等腰直角三角形的右边，因此，由所设知Rn+1=2Bn.又因为原等腰直角三角形沿底边上的高对折，故对折后原等腰直角三角形的两直角边重叠成为新等腰直角三角形的底边，因此有

Bn+1=Ln+Rn=1+Rn.

故总有如下递归关系

(3)

由此递归关系，仿照定理1的证明，可以用数学归纳法证明有如下结果：

由f(n)=Ln+Rn+Bn，定理获证.

同样的，我们有如下统一的公式.

定理2′将一张等腰直角三角形的纸张每次沿着底边上的高对折n次后，用刀沿着折痕裁它，每次裁后不准改变纸张的位置，将其裁成2n张小纸片，那么最少要裁的刀数为

-2.(n=1,2,…).

证明由递归关系(3)知

Bn+1=1+Rn，Rn+1=2Bn，

即Bn+1=1+Rn=1+2Bn-1，

于是Bn+1-2Bn-1-1=0，

此是一个常系数线性非齐次的递归关系，非齐次项为-1，所以有特解[1]f(n)=a，

代入递归关系Bk+1-2Bk-1-1=0,

得a-2a-1=0，即a=-1.

而齐次项对应的递归关系是Bk+1-2Bk-1=0，

对应的特征方程为x2-2=0，

从而递归关系(3)的通解为齐次的通解加特解，

由于B1=0,B2=1，

由前面定理2的证明知Rn+1=2Bn，

即Rn=2Bn-1，故

再根据f(n)=Ln+Rn+Bn知