一個裁紙計數問題的解決

2021-01-12 09:04:36朱玉揚

數學通報 2020年12期

朱玉揚

(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的證明，可以用數學歸納法證明有如下結果：