一個(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，即……