當前位置:成語大全網 - 新華字典 - 數學的分界因式中有壹種方法叫賦值法,請問賦值法是什麽意思

數學的分界因式中有壹種方法叫賦值法,請問賦值法是什麽意思

染色法

將問題中的對象適當進行染色,有利於我們觀察、分析對象之間的關系。像國際象棋的棋盤那樣,我們可以把被研究的對象染上不同的顏色,許多隱藏的關系會變得明朗,再通過對染色圖形的處理達到對原問題的解決,這種解題方法稱為染色法。常見的染色方式有:點染色、線段染色、小方格染色和對區域染色。

例1 用15個“T”字形紙片和1個“田”字形紙片(如下圖所示),能否覆蓋壹個8×8的棋盤?

解:如下圖,將 8×8的棋盤染成黑白相間的形狀。如果15個“T”字形紙片和1個“田”字形紙片能夠覆蓋壹個8×8的棋盤,那麽它們覆蓋住的白格數和黑格數都應該是32個,但是每個“T”字形紙片只能覆蓋1個或3個白格,而1和3都是奇數,因此15個“T”字形紙片覆蓋的白格數是壹個奇數;又每個“田”字形紙片壹定覆蓋2個白格,從而15個“T”字形紙片與1個“田”字形紙片所覆蓋的白格數是奇數,這與32是偶數矛盾,因此,用它們不能覆蓋整個棋盤。

例2 如左下圖,把正方體分割成27個相等的小正方體,在中心的那個小正方體中有壹只甲蟲,甲蟲能從每個小正方體走到與這個正方體相鄰的6個小正方體中的任何壹個中去。如果要求甲蟲只能走到每個小正方體壹次,那麽甲蟲能走遍所有的正方體嗎?

解:甲蟲不能走遍所有的正方體。我們如右上圖將正方體分割成27個小正方體,塗上黑白相間的兩種顏色,使得中心的小正方體染成白色,再使兩個相鄰的小正方體染上不同的顏色。顯然,在27個小正方體中,14個是黑的,13個是白的。甲蟲從中間的白色小正方體出發,每走壹步,方格就改變壹種顏色。故它走27步,應該經過14個白色的小正方體、13個黑色的小正方體。因此在27步中至少有壹個小正方體,甲蟲進去過兩次。由此可見,如果要求甲蟲到每壹個小正方體只去壹次,那麽甲蟲不能走遍所有的小正方體。

例3 8×8的國際象棋棋盤能不能被剪成7個2×2的正方形和9個4×1的長方形?如果可以,請給出壹種剪法;如果不行,請說明理由。

解:如下圖,對8×8的棋盤染色,則每壹個4×1的長方形能蓋住2白2黑小方格,每壹個2×2的正方形能蓋住1白3黑或3白1黑小方格。推知7個正方形蓋住的黑格總數是壹個奇數,但圖中的黑格數為32,是壹個偶數,故這種剪法是不存在的。

例4 在平面上有壹個27×27的方格棋盤,在棋盤的正中間擺好81枚棋子,它們被擺成壹個9×9的正方形。按下面的規則進行遊戲:每壹枚棋子都可沿水平方向或豎直方向越過相鄰的棋子,放進緊挨著這枚棋子的空格中,並把越過的這枚棋子取出來。問:是否存在壹種走法,使棋盤上最後恰好剩下壹枚棋子?

解:如下圖,將整個棋盤的每壹格都分別染上紅、白、黑三種顏色,這種染色方式將棋盤按顏色分成了三個部分。按照遊戲規則,每走壹步,有兩部分中的棋子數各減少了壹個,而第三部分的棋子數增加了壹個。這表明每走壹步,每個部分的棋子數的奇偶性都要改變。

因為壹開始時,81個棋子擺成壹個9×9的正方形,顯然三個部分的棋子數是相同的,故每走壹步,三部分中的棋子數的奇偶性是壹致的。

如果在走了若幹步以後,棋盤上恰好剩下壹枚棋子,則兩部分上的棋子數為偶數,而另壹部分的棋子數為奇數,這種結局是不可能的,即不存在壹種走法,使棋盤上最後恰好剩下壹枚棋子。

例5 圖1是由數字0,1交替構成的,圖2是由圖1中任選 減1,如此反復多次形成的。問:圖2中的A格上的數字是多少?

解:如左下圖所示,將8×8方格黑白交替地染色。

此題允許右上圖所示的6個操作,這6個操作無論實行在哪個位置上,白格中的數字之和減去黑格中的數字之和總是常數。所以圖1中白格中的數字之和減去黑格中的數字之和,與圖2中白格中的數字之和減去黑格中的數字之和相等,都等於32,由(31+A)-32=32,得出A=33。

例6 有壹批商品,每件都是長方體形狀,尺寸是1×2×4。現在有壹批現成的木箱,內空尺寸是6×6×6。問:能不能用這些商品將木箱填滿?

解:我們用染色法來解決這個問題。先將6×6×6的木箱分成216個小正方體,這216個小正方體,可以組成27個棱長為2的正方體。我們將這些棱長為2的正方體按黑白相間塗上顏色(如下圖)。

容易計算出,有14個黑色的,有13個白色的。現在將商品放入木箱內,不管怎麽放,每件商品要占據8個棱長為1的小正方體的空間,而且其中黑、白色的必須各占據4個。現在白色的小正方體***有8×13=104(個),再配上104個黑色的小正方體,壹***可以放26件商品,這時木箱余下的是8個黑色小正方體所占據的空間。這8個黑色的小正方體的體積雖然與壹件商品的體積相等,但是容不下這件商品。因此不能用這些商品剛好填滿。

例7 6個人參加壹個集會,每兩個人或者互相認識或者互相不認識。證明:存在兩個“三人組”,在每壹個“三人組”中的三個人,或者互相認識,或者互相不認識(這兩個“三人組”可以有公***成員)。

證明:將每個人用壹個點表示,如果兩人認識就在相應的兩個點之間連壹條紅色線段,否則就連壹條藍色線段。本題即是要證明在所得的圖中存在兩個同色的三角形。

設這六個點為A,B,C,D,E,F。我們先證明存在壹個同色的三角形:

考慮由A點引出的五條線段AB,AC,AD,AE,AF,其中必然有三條被染成了相同的顏色,不妨設AB,AC,AD同為紅色。再考慮△BCD的三邊:若其中有壹條是紅色,則存在壹個紅色三角形;若這三條都不是紅色,則存在壹個藍色三角形。

下面再來證明有兩個同色三角形:不妨設△ABC的三條邊都是紅色的。若△DEF也是三邊同為紅色的,則顯然就有兩個同色三角形;若△DEF三邊中有壹條邊為藍色,設其為DE,再考慮DA,DB,DC三條線段:若其中有兩條為紅色,則顯然有壹個紅色三角形;若其中有兩條是藍色的,則設其為DA,DB。此時在EA,EB中若有壹邊為藍色,則存在壹個藍色三角形;而若兩邊都是紅色,則又存在壹個紅色三角形。

故不論如何塗色,總可以找到兩個同色的三角形。

二、賦值法

將問題中的某些對象用適當的數表示之後,再進行運算、推理、解題的方法叫做賦值法。許多組合問題和非傳統的數論問題常用此法求解。常見的賦值方式有:對點賦值、對線段賦值、對區域賦值及對其他對象賦值。

例8 壹群旅遊者,從A村走到B村,路線如下圖所示。怎樣走才能在最短時間內到達B村?圖中的數字表示走這壹段路程需要的時間(單位:分)。

解:我們先把從A村到各村的最短時間標註在各村的旁邊,從左到右,壹壹標註,如下圖所示。

由此不難看出,按圖中的粗黑線走就能在最短時間(60分鐘)內從A村走到B村。

例9 把下圖中的圓圈任意塗上紅色或藍色。問:有無可能使得在同壹條直線上的紅圈數都是奇數?請說明理由。

解:假設題中所設想的染色方案能夠實現,那麽每條直線上代表各點的數字之和便應都是奇數。壹***有五條直線,把這五條直線上代表各點的數字之和的這五個奇數再加起來,得到的總和數仍應是壹個奇數。但是,由觀察可見,圖中每個點都恰好同時位於兩條直線上,在求上述總和數時,代表各點的數字都恰被加過兩次,所以這個總和應是壹個偶數。這就導致矛盾,說明假設不成立,染色方案不能實現。

例10 平面上n(n≥2)個點A1,A2,…,An順次排在同壹條直線上,每點塗上黑白兩色中的某壹種顏色。已知A1和An塗上的顏色不同。證明:相鄰兩點間連接的線段中,其兩端點不同色的線段的條數必為奇數。

證明:賦予黑點以整數值1,白點以整數值2,點Ai以整數

值為ai,當Ai為黑點時,ai=1,當Ai為白點時,ai=2。再賦予線段AiAi+1以整數值ai+ai+1,則兩端同色的線段具有的整數值為2或4,兩端異色的線段具有的整數值為3。

所有線段對應的整數值的總和為

(a1+a2)+(a2+a3)+(a3+a4)+…+(an-1+an)

=a1+an+2(a2+a3+…+an-1)

=2+1+2(a2+a3+…+an-1)=奇數。

設具有整數值2,3,4的線段的條數依次為l,m,n,則

2l+m+4n=奇數。

由上式推知,m必為奇數,證明完畢。

例11 下面的表1是壹個電子顯示盤,每壹次操作可以使某壹行四個字母同時改變,或者使某壹列四個字母同時改變。改變的規則是按照英文字母的順序,每個英文字母變成它的下壹個字母(即A變成B,B變成C……Z變成A)。問:能否經過若幹次操作,使表1變為表2?如果能,請寫出變化過程,如果不能,請說明理由。

S O B R K B D S

T Z F P H E X G

H O C N R T B S

A D V X C F Y A

表1 表2

解:不能。將表中的英文字母分別用它們在字母表中的序號代替(即A用1,B用2……Z用26代替)。這樣表1和表2就分別變成了表3和表4。

每壹次操作中字母的置換相當於下面的置換:

1→2,2→3,…,25→26,26→1。

19 15 2 18

20 26 6 16

8 15 3 14

1 4 22 24

表3

11 2 4 19

8 5 24 7

18 20 2 19

3 6 25 1

表4

容易看出,每次操作使四個數字改變了奇偶性,而16個數字的和的奇偶性沒有改變。因為表3中16個數字的和為213,表4中16個數字的和為174,它們的奇偶性不同,所以表3不能變成表4,即表1不能變成表2。

例12 如圖(1)~(6)所示的六種圖形拼成右下圖,如果圖(1)必須放在右下圖的中間壹列,應如何拼?

解:把右上圖黑、白相間染色(見上圖)。其中有11個白格和10個黑格,當圖形拼成後,圖形(2)(4)(5)(6)壹定是黑、白各2格,而圖形(3)必須有3格是同壹種顏色,另壹種顏色1格。因為前四種圖形,黑、白已各占2×4=8(格),而黑格總***只有10格,所以圖形(3)只能是3白1黑。由此知道圖(1)壹定在中間壹列的黑格,而上面的黑格不可能,所以圖(1)在中間壹列下面的黑格中。

那麽其它圖形如何拼呢?為了說明方便,給每壹格編壹個數碼(見左下圖)。

因為圖(3)是3白1黑,所以為使角上不空出壹格,它只能放在(1,3,4,5)或(7,12,13,17)或(11,15,16,21)這三個位置上。

若放在(1,3,4,5)位置上,則圖(6)只能放在(7,12,13,18)或(15,16,19,20)或(2,7,8,13)這三個位置,但是前兩個位置是明顯不行的,否則角上會空出壹格。若放在(2,7,8,13)上,則圖(2)只能放在(12,17,18,19)位置上,此時不能同時放下圖(4)和圖(5)。

若把圖(3)放在(7,12,13,17)位置上,則方格1這壹格只能由圖(2)或圖(6)來占據。如果圖(2)放在(1,2,3,4),那麽圖(6)無論放在何處都要出現孤立空格;如果把圖(6)放在(1,4,5,10),那麽2,3這兩格放哪壹圖形都不合適。

因此,圖形(3)只能放在(11,15,16,21)。其余圖的拼法如右上圖。

練習12

1.中國象棋盤的任意位置有壹只馬,它跳了若幹步正好回到原來的位置。問:馬所跳的步數是奇數還是偶數?

2.右圖是某展覽大廳的平面圖,每相鄰兩展覽室之間都有門相通。今有人想從進口進去,從出口出來,每間展覽廳都要走到,既不能重復也不能遺漏,應如何走法?

3.能否用下圖中各種形狀的紙片(不能剪開)拼成壹個邊長為99的正方形(圖中每個小方格的邊長為1)?請說明理由。

4.用15個1×4的長方形和1個2×2的正方形,能否覆蓋8×8的棋盤?

5.平面上不***線的五點,每兩點連壹條線段,並將每條線段染成紅色或藍色。如果在這個圖形中沒有出現三邊同色的三角形,那麽這個圖形壹定可以找到壹紅壹藍兩個“圈”(即封閉回路),每個圈恰好由五條線段組成。

6.將正方形ABCD分割成n2個相等的小正方格,把相對的頂點A,C染成紅色,B,D染成藍色,其他交點任意染成紅、藍兩種顏色之壹。試說明:恰有三個頂點同色的小方格的數目是偶數。

7.已知△ABC內有n個點,連同A,B,C三點壹***(n+3)個點。以這些點為頂點將△ABC分成若幹個互不重疊的小三角形。將A,B,C三點分別染成紅色、藍色和黃色。而三角形內的n個點,每個點任意染成紅色、藍色和黃色三色之壹。問:三個頂點顏色都不同的三角形的個數是奇數還是偶數?

8.從10個英文字母A,B,C,D,E,F,G,X,Y,Z中任意選5個字母(字母允許重復)組成壹個“詞”,將所有可能的“詞”按“字典順序”(即英漢辭典中英語詞匯排列的順序)排列,得到壹個“詞表”:

AAAAA,AAAAB,…,AAAAZ,

AAABA,AAABB,…,ZZZZY,ZZZZZ。

設位於“詞”CYZGB與“詞”XEFDA之間(這兩個詞除外)的“詞”的個數是k,試寫出“詞表”中的第k個“詞”。

練習12

1.偶數。

解:把棋盤上各點按黑白色間隔進行染色(圖略)。馬如從黑點出發,壹步只能跳到白點,下壹步再從白點跳到黑點,因此,從原始位置起相繼經過:白、黑、白、黑……要想回到黑點,必須黑、白成對,即經過偶數步,回到原來的位置。

2.不能。

解:用白、黑相間的方法對方格進行染色(如圖)。若滿足題設要求的走法存在,必定從白色的展室走到黑色的展室,再從黑色的展室走到白色的展室,如此循環往復。現***有36間展室,從白色展室開始,最後應該是黑色展室。但右圖中出口處的展室是白色的,矛盾。由此可以判定符合要求的走法不存在。

3.不能。

解:我們將 99×99的正方形中每個單位正方形方格染上黑色或白色,使每兩個相鄰的方格顏色不同,由於 99×99為奇數,兩種顏色的方格數相差為1。而每壹種紙片中,兩種顏色的方格數相差數為0或3,如果它們能拼成壹個大正方形,那麽其中兩種顏色之差必為3的倍數。矛盾!

4.不能。

解:如圖,給8×8的方格棋盤塗上4種不同的顏色(用數字1,2,3,4表示)。顯然標有1,2,3,4的小方格各有16個。每個1×4的長方形恰好蓋住標有1,2,3,4的小方格各壹個,但壹個2×2的正方形只能蓋住有三種數字的方格,故無法將每個方格蓋住,即不可能有題目要求的覆蓋。

5.證:設五點為A,B,C,D,E。考慮從A點引出的四條線段:如果其中有三條是同色的,如AB,AC,AD同為紅色,那麽△BCD的三邊中,若有壹條是紅色,則有壹個三邊同為紅色的三角形;若三邊都不是紅色,則存在壹個三邊同為藍色的三角形。這與已知條件是矛盾的。

所以,從A點出發的四條線段,有兩條是紅色的,也有兩條是藍色的。當然,從其余四點引出的四條線段也恰有兩條紅色、兩條藍色,整個圖中恰有五條紅色線段和五條藍色線段。

下面只看紅色線段,設從A點出發的兩條是AB,AE。再考慮從B點出發的另壹條紅色線段,它不應是BE,否則就有壹個三邊同為紅色的三角形。不妨設其為BD。再考慮從D點出發的另壹條紅色線段,它不應是DE,否則從C引出的兩條紅色線段就要與另壹條紅色線段圍成壹個紅色三角形,故它是DC。最後壹條紅色線段顯然是CE。這樣就得到了壹個紅色的“圈”:

A→B→D→C→E→A。

同理,五條藍線也構成壹個“圈”。

6.證:將紅點賦值為0,藍點賦值為1。再將小方格四頂點上的數的和稱為這個小方格的值。若恰有三頂點同色,則該小方格的值為奇數,否則為偶數。在計算所有n2個小方格之值的和時,除A,B,C,D只計算壹次外,其余各點都被計算了兩次或四次。因為A,B,C,D四個點上的數之和是偶數,所以n2個小方格之值的和是偶數,從而這n2個值中有偶數個奇數。

7.奇數。

解:先對所有的小三角形的邊賦值:邊的兩端點同色,該線段賦值為0,邊的兩端點不同色,該線段賦值為1。

然後計算每個小三角形的三邊賦值之和,有如下三種情況:

(1)三個頂點都不同色的三角形,賦值和為3;

(2)三個頂點中恰有兩個頂點同色的三角形,賦值和為2;

(3)三個頂點同色的三角形,賦值和為0。

設所有三角形的邊賦值總和為S,又設(1)(2)(3)三類小三角形的個數分別為a,b,c,於是有

S=3a+2b+0c=3a+2b。(*)

註意到在所有三角形的邊賦值總和中,除了AB,BC,CA三條邊外,都被計算了兩次,故它們的賦值和是這些邊賦值和的2倍,再加上△ABC的三邊賦值和3,從而S是壹個奇數,由(*)式知a是壹個奇數,即三個頂點顏色都不同的三角形的個數是壹個奇數。

8.EFFGY。

解:將A,B,C,D,E,F,G,X,Y,Z分別賦值為0,1,2,3,4,5,6,7,8,9,則

CYZGB=28961,_XEFDA=74530。

在28961與74530之間***有74530-28961-1=45568(個)數,詞表中第45568個詞是EFFGY。