●

(育才中學(xué) 上海 201801)

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

●龔新平

(育才中學(xué) 上海 201801)

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

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

1問(wèn)題簡(jiǎn)解

解法1只需羅列出滿(mǎn)足條件的所有鋸木棒方法,過(guò)程如下:

30→15,15

由此可知,長(zhǎng)度為30的木棒至多可以鋸成6段,具體鋸棒過(guò)程為:

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

解法2最多能鋸成6段,構(gòu)造如下:

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

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

當(dāng)x7=6時(shí),只能是6,4,4,4,4,4,4,逆推得6,8,4,4,4,4,矛盾;

當(dāng)x7=5時(shí),只能是5,5,4,4,4,4,4或5,5,5,4,4,4,3或5,5,5,5,4,3,3,以上逆推均得出矛盾,故無(wú)法鋸成7段.從而7段以上也不能鋸出!

2初步探究

探究1最小長(zhǎng)度至多2段.

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

探究2當(dāng)lgt;2時(shí),最小長(zhǎng)度大于1.

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

探究3非最小長(zhǎng)度至多3段.

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

探究4某長(zhǎng)度出現(xiàn)2段后,該長(zhǎng)度不能再鋸.

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

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

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

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

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

3構(gòu)造探究

由前面的探究,可知欲使定長(zhǎng)l鋸成最多段數(shù),則小段長(zhǎng)度應(yīng)盡量多。由此得如下構(gòu)造:

構(gòu)造1長(zhǎng)度為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段木棒逆推可合成一根木棒,且滿(mǎn)足條件.

證明對(duì)k,k,k+1,k+1,…,2k-1,2k-1,由探究5將整個(gè)鋸棒過(guò)程逆推可得:

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,…,

易見(jiàn)以上各步中任何時(shí)刻所有木棒最長(zhǎng)者均小于最短者長(zhǎng)度的2倍.同理可得,對(duì)k,k+1,k+1,…,2k-2,2k-2,2k-1,2k-1,2k-1,由探究5將整個(gè)鋸棒過(guò)程逆推可得:

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,….

以上各步任何時(shí)刻所有木棒最長(zhǎng)者也小于最短者長(zhǎng)度的2倍!

探究6最小長(zhǎng)度為k時(shí),至多可以鋸成的段數(shù)n≤2k.

由前面的構(gòu)造1,可知長(zhǎng)度為l的木棒當(dāng)最小長(zhǎng)度為k時(shí),至多可以鋸成如下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.

構(gòu)造2木棒長(zhǎng)度為l=k(3k-1)+i,對(duì)每個(gè)i=1,2,3,…,k-1時(shí),均至多可以鋸成2k段.

證明對(duì)2k段木棒k,k,k+1,k+1,…,2k-1,2k-1中從左至右的偶數(shù)位置上(最后一個(gè)2k-1除外)的數(shù)從左至右依次將一個(gè)數(shù)加1,或?qū)?個(gè)數(shù)加1,或?qū)?個(gè)數(shù)加1,…,或?qū)個(gè)數(shù)加1后,得到的長(zhǎng)度k,k+1,k+1,k+2,…,k+i-1,k+i,k+i,…,2k-1,2k-1仍滿(mǎn)足條件.此時(shí),木棒長(zhǎng)度為

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

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

探究7最小長(zhǎng)度k應(yīng)滿(mǎn)足3k2-1≥l.

由構(gòu)造2,易得

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

同理由構(gòu)造2,可得

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

4問(wèn)題新解

由前面的探究,可得到原問(wèn)題的如下解法3:

解法3由最小長(zhǎng)度k應(yīng)滿(mǎn)足3k2-1≥30,可得k≥4,而至多可以鋸成2k段的木棒最短長(zhǎng)度

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

在此基礎(chǔ)上去掉個(gè)數(shù)最少而和為14的若干段的最佳方案是去掉2個(gè)7,于是長(zhǎng)度為30的木棒至多可以鋸成6段:4，4，5，5，6，6,逆推得具體過(guò)程為:

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

5變式探究

探究9設(shè)木棒長(zhǎng)度為l=k(3k-1)-i.

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

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

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

解由最小長(zhǎng)度k應(yīng)滿(mǎn)足3k2-1≥40,可得k≥4,而至多可以鋸成2k段的木棒最短長(zhǎng)度

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

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

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長(zhǎng)為l(l為整數(shù))的木棒可以鋸成長(zhǎng)為整數(shù)的2段,要求任何時(shí)刻所有木棒中的最長(zhǎng)者長(zhǎng)度嚴(yán)格小于最短者長(zhǎng)度的2倍.試問(wèn):長(zhǎng)度為18的木棒至多可以鋸成多少段?

解由最小長(zhǎng)度k應(yīng)滿(mǎn)足3k2-1≥18,可得k≥3,而至多可以鋸成2k段的木棒最短長(zhǎng)度為

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

在此基礎(chǔ)上去掉個(gè)數(shù)最少而剩下數(shù)和為18的最佳方案是去掉2個(gè)3或去掉1個(gè)3與1個(gè)4而將剩下1個(gè)4變?yōu)?,于是長(zhǎng)為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.

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

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

解由最小長(zhǎng)度k應(yīng)滿(mǎn)足3k2-1≥23,可得k≥3,而至多可以鋸成2k段的木棒最短長(zhǎng)度為

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

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

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

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