一道2010年清華大學自主招生題的探究

●

(育才中學 上海 201801)

一道2010年清華大學自主招生題的探究

●龔新平

(育才中學 上海 201801)

2010年五校自主招生聯考清華大學特色考試試題中出現了如下的離散最值問題(見文獻[1]).本文將對該問題提供3種解答,并在此基礎上應用逆推法與逐步調整法深入地加以探究,構造提出一個近似估計的求解方案，同時將原問題進行一些變式推廣.現筆者將過程整理出來,與讀者共同探討.

問題長度為l(l為整數)的木棒可以鋸成長為整數的2段,要求任何時刻所有木棒中的最長者長度嚴格小于最短者長度的2倍.試問:長度為30的木棒至多可以鋸成多少段?

1問題簡解

解法1只需羅列出滿足條件的所有鋸木棒方法,過程如下:

30→15,15

由此可知,長度為30的木棒至多可以鋸成6段,具體鋸棒過程為:

30→12,18→12,8,10→6,6,8,10→6,6,8,5,5→4,4,5,5,6,6.

解法2最多能鋸成6段,構造如下:

30→12,18→12,8,10→6,6,8,10→6,6,8,5,5→4,4,5,5,6,6.

若能鋸成7段,設為x1,x2,…,x7,(x1≤x2…≤x7),則顯然x7gt;4.若x7≥7,則x1≥4,而4×6+7=31≥30,產生矛盾,故x7=5或x7=6.

當x7=6時,只能是6,4,4,4,4,4,4,逆推得6,8,4,4,4,4,矛盾;

當x7=5時,只能是5,5,4,4,4,4,4或5,5,5,4,4,4,3或5,5,5,5,4,3,3,以上逆推均得出矛盾,故無法鋸成7段.從而7段以上也不能鋸出!

2初步探究

探究1最小長度至多2段.

若最小長度至少3段,則任兩段之和不小于最小長度的2倍,矛盾!

探究2當lgt;2時,最小長度大于1.

若最小長度等于1,由最大長度小于2知,所有長度均為1,而lgt;2,故至少有3個1,矛盾!

探究3非最小長度至多3段.

若某長度至少4段,則一段和比其小的長度由其和長度鋸成,剩下該長度的3段中必有2段由其和長度鋸成,而此和為第3段的2倍,矛盾!

探究4某長度出現2段后,該長度不能再鋸.

若該長度某段再被鋸成2段,則其短者之2倍必不大于該長度的另一段,矛盾!

探究5木棒每次被鋸時,將長度a鋸成b,c(b≥c),則

(1)a是被鋸前的最大者;

(2)c是被鋸后的最短者.

若存在a′≥a=b+c≥2c,矛盾;若存在c′≤c≤b,則2c′≤c+b=a,矛盾.

3構造探究

由前面的探究,可知欲使定長l鋸成最多段數,則小段長度應盡量多。由此得如下構造:

構造1長度為k,k,k+1,k+1,…,2k-1,2k-1或k,k+1,k+1,…,2k-2,2k-2,2k-1,2k-1,2k-1的2k段木棒逆推可合成一根木棒,且滿足條件.

證明對k,k,k+1,k+1,…,2k-1,2k-1,由探究5將整個鋸棒過程逆推可得:

k,k,k+1,k+1,…,2k-1,2k-1← 2k,k+1,k+1,…,2k-1,2k-1←…←

2k,2k+2,…,4k-2←4k+2,…,

易見以上各步中任何時刻所有木棒最長者均小于最短者長度的2倍.同理可得,對k,k+1,k+1,…,2k-2,2k-2,2k-1,2k-1,2k-1,由探究5將整個鋸棒過程逆推可得:

k,k+1,k+1,…,2k-2,2k-2,2k-1,2k-1,2k-1←2k+1,…,←

2k+1,2k+3,…,4k-2←4k+4,….

以上各步任何時刻所有木棒最長者也小于最短者長度的2倍!

探究6最小長度為k時,至多可以鋸成的段數n≤2k.

由前面的構造1,可知長度為l的木棒當最小長度為k時,至多可以鋸成如下2k段,即

l→k,k,k+1,k+1,…,2k-1,2k-1,

或

l→k,k+1,k+1,…,2k-2,2k-2,2k-1,2k-1,2k-1,

及其各種部分片段,故n≤2k.

構造2木棒長度為l=k(3k-1)+i,對每個i=1,2,3,…,k-1時,均至多可以鋸成2k段.

證明對2k段木棒k,k,k+1,k+1,…,2k-1,2k-1中從左至右的偶數位置上(最后一個2k-1除外)的數從左至右依次將一個數加1,或將2個數加1,或將3個數加1,…,或將i個數加1后,得到的長度k,k+1,k+1,k+2,…,k+i-1,k+i,k+i,…,2k-1,2k-1仍滿足條件.此時,木棒長度為

l=2[k+(k+1)+…+(2k-1)]+i=k3k-1+i,

即木棒長度l=k(3k-1)+i,(i=1,2,3，…,k-1)時,至多可鋸成2k段.

探究7最小長度k應滿足3k2-1≥l.

由構造2,易得

l≤2[k+(k+1)+…+(2k-1)]+(k-1)=3k2-1.

同理由構造2,可得

探究8當最小長度為k,木棒長度l=k(3k-1)+i(i=0,1,2,…,k-1)時,至多可鋸成2k段.

4問題新解

由前面的探究,可得到原問題的如下解法3:

解法3由最小長度k應滿足3k2-1≥30,可得k≥4,而至多可以鋸成2k段的木棒最短長度

l=4+4+5+5+6+6+7+7=44.

在此基礎上去掉個數最少而和為14的若干段的最佳方案是去掉2個7,于是長度為30的木棒至多可以鋸成6段:4，4，5，5，6，6,逆推得具體過程為:

4，4，5，5，6，6←8,5,5,6,6←8,10,6,6←8,10,12←18,12←30.

5變式探究

探究9設木棒長度為l=k(3k-1)-i.

(1)當i=k,k+1,…2k-1時,由于k,k,k+1,k+1,…,2k-1,2k-1中每個數不能減少(否則不符合題意),因此直接去掉一個i,從而至多可以鋸成2k-1段;

(2)當i=2k,2k+1,2k+2,…,2(2k-1)時,由于每個i均可表示成k,k,k+1,…,2k-1,2k-1中的2個數之和,因此至多可鋸成2k-2段.

變式1長為l(l為整數)的木棒可以鋸成長為整數的2段,要求任何時刻所有木棒中的最長者長度嚴格小于最短者長度的2倍.試問:長度為40的木棒至多可以鋸成多少段?

解由最小長度k應滿足3k2-1≥40,可得k≥4,而至多可以鋸成2k段的木棒最短長度

l=4+4+5+5+6+6+7+7=44.

在此基礎上去掉個數最少而剩下數和為40的最佳方案直接去掉一個4,即長為40的木棒至多可以鋸成如下7段:4,5,5,6，6，7，7，由逆推可得其具體鋸法過程為:

4，5，5，6，6，7，7←9,5,6,6,7,7←9,11,6,7,7←9,11,13,7←16,11,13←16,24←40.

變式2長為l(l為整數)的木棒可以鋸成長為整數的2段,要求任何時刻所有木棒中的最長者長度嚴格小于最短者長度的2倍.試問:長度為18的木棒至多可以鋸成多少段?

解由最小長度k應滿足3k2-1≥18,可得k≥3,而至多可以鋸成2k段的木棒最短長度為

l=3+3+4+4+5+5=24.

在此基礎上去掉個數最少而剩下數和為18的最佳方案是去掉2個3或去掉1個3與1個4而將剩下1個4變為5,于是長為18的木棒至多可以鋸成4段:4,4,5,5或3,5,5,5,逆推得具體鋸法為:

4,4,5,5←8,5,5←8,10←18或3,5,5,5←8,5,5←8,10←18.

對長度為l=k(3k-1)-i(i=1,2,3,4,5,…,k-1)的木棒至多可以鋸成多少段的問題,在具體問題中應用逐步調整法總可以得到最佳答案!下面來看具體的變式問題:

變式3長為l(l為整數)的木棒可以鋸成長為整數的2段,要求任何時刻所有木棒中的最長者長度嚴格小于最短者長度的2倍.試問:長度為23的木棒至多可以鋸成多少段?

解由最小長度k應滿足3k2-1≥23,可得k≥3,而至多可以鋸成2k段的木棒最短長度為

l=3+3+4+4+5+5=24.

在此基礎上去掉個數最少而剩下數和為23的最佳方案是將其中4個數變為2個而和減少1,于是長為23的木棒至多可以鋸成4段:5,5,6,7或4,5,7,7或4,6,6,7,逆推得具體鋸法為:

5,5,6,7←10,6,7←10,13←23或4,5,7,7←9,7,7←9,14←23或4,6,6,7←10,6,7←10,13←23.

在前面的變式探究中,當木棒的長度l=3k(3k-1)-i(i=1,2,…,2k-1)時,筆者應用逐步調整法給出了一個較好的求解方法來探求最佳答案.除此之外,是否還有更直接而簡潔的方法呢?期待與大家共同探討!

[1] 范端喜.名牌大學自主招生高效備考[M].上海:華東師范大學出版社，2010.