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

●

(育才中學 上海 201801)

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

●龔新平

(育才中學 上海 201801)

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

問題長度為l(l為整數(shù))的木棒可以鋸成長為整數(shù)的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某長度出現(xiàn)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鋸成最多段數(shù),則小段長度應盡量多。由此得如下構造:

構造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時,至多可以鋸成的段數(shù)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中從左至右的偶數(shù)位置上(最后一個2k-1除外)的數(shù)從左至右依次將一個數(shù)加1,或將2個數(shù)加1,或將3個數(shù)加1,…,或將i個數(shù)加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.

在此基礎上去掉個數(shù)最少而和為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中每個數(shù)不能減少(否則不符合題意),因此直接去掉一個i,從而至多可以鋸成2k-1段;

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

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

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

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

在此基礎上去掉個數(shù)最少而剩下數(shù)和為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為整數(shù))的木棒可以鋸成長為整數(shù)的2段,要求任何時刻所有木棒中的最長者長度嚴格小于最短者長度的2倍.試問:長度為18的木棒至多可以鋸成多少段?

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

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

在此基礎上去掉個數(shù)最少而剩下數(shù)和為18的最佳方案是去掉2個3或去掉1個3與1個4而將剩下1個4變?yōu)?,于是長為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為整數(shù))的木棒可以鋸成長為整數(shù)的2段,要求任何時刻所有木棒中的最長者長度嚴格小于最短者長度的2倍.試問:長度為23的木棒至多可以鋸成多少段?

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

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

在此基礎上去掉個數(shù)最少而剩下數(shù)和為23的最佳方案是將其中4個數(shù)變?yōu)?個而和減少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.