一個(gè)裁紙計(jì)數(shù)問題的解決

朱玉揚(yáng)

(1.亳州學(xué)院電子與信息工程系 236800；2.合肥學(xué)院人工智能與大數(shù)據(jù)學(xué)院 230601)

將一張矩形的紙張對(duì)折n次后，用刀沿著折痕裁它，每次裁后不準(zhǔn)將其重疊再裁，即每次裁后不準(zhǔn)改變紙張的位置，那么，至少要裁多少刀才可以將紙張裁成2n張小紙片？為解決這一問題，先看下表：

表1 裁紙張數(shù)分布表

定理1將一張矩形的紙張對(duì)折n次后，用刀沿著折痕裁它，每次裁后不準(zhǔn)改變紙張的位置，將其裁成2n張小紙片，那么最少要裁的刀數(shù)為

證明記對(duì)折n次后需裁得刀數(shù)為f(n). 我們知道，對(duì)折n次，最后一道折痕即是最厚的一道折痕，它所對(duì)應(yīng)的一邊需裁1刀，倒數(shù)第二道折痕即是次厚的折痕，它所對(duì)應(yīng)的一邊需裁2刀.

不妨令折痕最厚的邊為“下邊”，折痕次厚的邊為“右邊”，故“下邊”需裁1刀，“右邊”需裁2刀，而所折紙塊的另兩邊即“上邊”與“左邊”所需裁的最少刀數(shù)分別設(shè)為an-2與bn-2，所以f(n)等于各邊最少刀數(shù)之和，即f(n)=1+2+an-2+bn-2.

下面我們來考慮數(shù)列{an}與{bn}之間的關(guān)系.

當(dāng)n=k+2(k∈N+)時(shí)，由上面所設(shè)知“上邊”所需裁的最少刀數(shù)為ak，“左邊”所需裁的最少刀數(shù)為bk，而“下邊”所需裁的最少刀數(shù)為1刀，“右邊”所需裁的最少刀數(shù)為2刀(見圖1(i)).

當(dāng)n=k+3時(shí)，我們可逆向考慮. 如圖1(ii)，將原先所折紙張沿著虛線L對(duì)折，則圖1(i)變?yōu)閳D1(ii)：

圖1(i)

圖1(ii)

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

因a0=0,a1=2，由(1)式易證a2k-1=a2k(k∈N+). 事實(shí)上k=1時(shí)，a0=0,a1=2，由(1)式得a2=2(a0+1)=2，即k=1時(shí)，有a2k-1=a2k. 假設(shè)k=s(s≥1,s∈N+)時(shí)有a2s-1=a2s，那么k=s+1時(shí)，有

(2)

由假設(shè)知a2s-1=a2s，由(2)兩式即得a2(s+1)-1=a2(s+1)，由數(shù)學(xué)歸納法原理即知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.

故當(dāng)n≥3時(shí)，f(n)=3+an-2+bn-2

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

而tk=a2k-1=a2k，

所以當(dāng)n為奇數(shù)時(shí)

當(dāng)n為偶數(shù)時(shí)

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

故當(dāng)n≥3時(shí)有

另一方面，當(dāng)n=1,2時(shí)，因f(1)=1，f(2)=3，即上式也成了，故對(duì)一切自然數(shù)n(n≥1)，上式皆成立. 證畢.

實(shí)際上，我們有如下統(tǒng)一的公式.

定理1′將一張矩形的紙張對(duì)折n次后，用刀沿著折痕裁它，每次裁后不準(zhǔn)改變紙張的位置，將其裁成2n張小紙片，那么最少要裁的刀數(shù)為

(n=1,2,3,…)

證明由遞歸關(guān)系(1)知

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

此是一個(gè)常系數(shù)線性非齊次的遞歸關(guān)系，非齊次項(xiàng)為-2，所以有特解[1]f(n)=a，

代入遞歸關(guān)系ak+1-2ak-1-2=0得

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

而齊次項(xiàng)對(duì)應(yīng)的遞歸關(guān)系是ak+1-2ak-1=0，

對(duì)應(yīng)的特征方程為x2-2=0，

從而遞歸關(guān)系(1)的通解為齊次的通解加特解，即

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

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

即bn=2an-1，故

再根據(jù)定理的證明知

對(duì)于等腰直角三角形每次沿著底邊上的高對(duì)折，用刀沿著折痕裁它，每次裁后不準(zhǔn)改變紙張的位置，將其裁成2n張小紙片，那么最少要裁的刀數(shù)是什么？用類似的方法，我們有下面的結(jié)論：

定理2將一張等腰直角三角形的紙張每次沿著底邊上的高對(duì)折n次后，用刀沿著折痕裁它，每次裁后不準(zhǔn)改變紙張的位置，將其裁成2n張小紙片，那么最少要裁的刀數(shù)為

證明對(duì)于一個(gè)等腰直角三角形，每次沿著底邊上的高對(duì)折n次后，得到2n個(gè)重疊在一起的小等腰直角三角形，每次裁都不改變它們?cè)瓉淼奈恢?，設(shè)其底部需裁的最少刀數(shù)為Bn，左邊需裁的最少刀數(shù)為L(zhǎng)n，右邊需裁的最少刀數(shù)為Rn. 由于每次對(duì)折后總有一直角邊只需裁一刀即可(即是最厚的一道折痕)，設(shè)這個(gè)直角邊總為左邊，故Ln=1. 另一方面，每次都是沿著底邊上的高對(duì)折，因此折痕沿原三角形的底邊的中點(diǎn)，從而原三角形底邊從中點(diǎn)對(duì)折重疊形成新等腰直角三角形，新的等腰直角三角形的一個(gè)直角邊即是原三角形底邊重疊形成的，這個(gè)直角邊即是新的等腰直角三角形的右邊，因此，由所設(shè)知Rn+1=2Bn.又因?yàn)樵妊苯侨切窝氐走吷系母邔?duì)折，故對(duì)折后原等腰直角三角形的兩直角邊重疊成為新等腰直角三角形的底邊，因此有

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

故總有如下遞歸關(guān)系

(3)

由此遞歸關(guān)系，仿照定理1的證明，可以用數(shù)學(xué)歸納法證明有如下結(jié)果：

由f(n)=Ln+Rn+Bn，定理獲證.

同樣的，我們有如下統(tǒng)一的公式.

定理2′將一張等腰直角三角形的紙張每次沿著底邊上的高對(duì)折n次后，用刀沿著折痕裁它，每次裁后不準(zhǔn)改變紙張的位置，將其裁成2n張小紙片，那么最少要裁的刀數(shù)為

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

證明由遞歸關(guān)系(3)知

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

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

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

此是一個(gè)常系數(shù)線性非齊次的遞歸關(guān)系，非齊次項(xiàng)為-1，所以有特解[1]f(n)=a，

代入遞歸關(guān)系Bk+1-2Bk-1-1=0,

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

而齊次項(xiàng)對(duì)應(yīng)的遞歸關(guān)系是Bk+1-2Bk-1=0，

對(duì)應(yīng)的特征方程為x2-2=0，

從而遞歸關(guān)系(3)的通解為齊次的通解加特解，

由于B1=0,B2=1，

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

即Rn=2Bn-1，故

再根據(jù)f(n)=Ln+Rn+Bn知