試卷題1按字典序法遞增、遞減鄰位互換法求全排列之后的第100

1、試卷 1題 1: 按字典序法，遞增、遞減、鄰位互換法求全排列 839647521 之后的第 100 的排列。原中介數(shù)100 對(duì)應(yīng)進(jìn)制數(shù)新中介數(shù)對(duì)應(yīng)排列7264232140206734222140206735131186942735112224376131122245273976458211012137210121523364529871839741562題 2: 證明在平面直角坐標(biāo)系中 33 個(gè)整點(diǎn)中必有 9 個(gè)整點(diǎn)的重心是整點(diǎn)。先證明 9 個(gè)整點(diǎn)中必有 3 個(gè)整點(diǎn)的重心的仍是整點(diǎn)。（證明方法請(qǐng)參照第三章習(xí)題 17 解答）33 個(gè)整點(diǎn)中必有 9 個(gè) 3 點(diǎn)組，每組的重心仍是整點(diǎn)。而這 9 個(gè)重

2、心中必有 3 個(gè)的重心仍是整點(diǎn)，從而就證明了 33 個(gè)整點(diǎn)中必有 9 個(gè)整點(diǎn)的重心仍是整點(diǎn)。題 3: 求下列有的棋盤(pán)布子的方案數(shù)。(為 1 的地方是1 0 0 0 0 00 1 0 0 0 00 0 1 1 0 00 0 0 1 0 00 0 0 0 1 10 0 0 0 1 1布子多項(xiàng)式：(1+4x+2x2)(1+3x+x2)2= 1+ 10 x+37x2+62x3+47x4+16x5+2x66-10)5+37)4 -62)3+47)2-16)1+2=116)題 4: 用斜邊分別為 1 和 2(1/2)的兩種直角三角形的磚和邊長(zhǎng)為 1 的正方形的磚給 1xN 的路鋪面,共有多少種方案?在所有

3、方案中,正方形的磚一共用了多少塊?見(jiàn)第二章習(xí)題 34 解答。題 5: 用外形相同的紅,綠火柴各 6 根搭一個(gè)正 8 面體,有多少方案?轉(zhuǎn)動(dòng)群(1)12不動(dòng):1 個(gè)8 個(gè)6 個(gè) 不存在3 個(gè)6 個(gè)面心對(duì)面心旋轉(zhuǎn)120(3)4頂點(diǎn)對(duì)頂點(diǎn)旋轉(zhuǎn)90(4)3(2)6(1)2(2)5頂點(diǎn)對(duì)頂點(diǎn)旋轉(zhuǎn) 180棱中對(duì)棱中 （無(wú)）方案數(shù)212C(12,6)+824C(4,2)+326C(6,3)/24=157888題 6: 用單純形法解下列線性規(guī)劃問(wèn)題。x+5y5 3x+y3 x,y0用工具（第六章課后題計(jì)算工具）計(jì)算。為 x=5/7,y=6/7,minx+2y=17/7試卷 2題 1:按字典序法，遞增、遞減、鄰

4、位互換法求全排列 739648521 之后的第 100 的排列。原中介數(shù)100 對(duì)應(yīng)進(jìn)制數(shù)新中介數(shù)對(duì)應(yīng)排列6264232140206364222140206365131176942835112224636131122250676983452171012104610121177364529871739841562題 2: 證明在平面直角坐標(biāo)系中 21 個(gè)整點(diǎn)中必有 6 個(gè)整點(diǎn)的重心是整點(diǎn)。先證明 9 個(gè)整點(diǎn)中必有 3 個(gè)整點(diǎn)的重心的仍是整點(diǎn)（證明方法請(qǐng)參照第三章習(xí)題 17 解答），再證 5 個(gè)整點(diǎn)中必有 2 個(gè)整點(diǎn)的重心是整點(diǎn)。21 個(gè)整點(diǎn)中必有 5 個(gè) 3 點(diǎn)組，每組的重心仍是整點(diǎn)。而這 5

5、個(gè)重心中必有 2 個(gè)的重心仍是整點(diǎn)，從而就證明了 21 個(gè)整點(diǎn)中必有 6 個(gè)整點(diǎn)的重心仍是整點(diǎn)。題 3:求下列有 1 1 0 0 0 01 1 0 0 0 00 0 1 1 0 00 0 0 1 0 00 0 0 0 1 10 0 0 0 1 0的棋盤(pán)布子的方案數(shù)。(為 1 的地方是)布子多項(xiàng)式: (1+x2)(1+3x+x2)(1+4x+2x2) = 1+ 9x+30 x2+47x3+37x4+14x5+2x66-9)5+30)4 -47)3+37)2-14)1+2=140題 4: 用直角邊分別為 2(1/2)和 2 的兩種直角三角形的磚和邊長(zhǎng)為 1 的正方形的磚給 1xN 的路鋪面,共有多

6、少種方案?在所有方案中,正方形的磚一共用了多少塊?解略,方法參照第二章習(xí)題 34 解答。題 5: 用外形相同的紅,綠火柴各 6 根搭一個(gè)正六面體,有多少方案?解:轉(zhuǎn)動(dòng)群(1)12不動(dòng):1 個(gè)8 個(gè)6 個(gè) 不存在3 個(gè)6 個(gè)頂點(diǎn)對(duì)頂點(diǎn)旋轉(zhuǎn)120(3)4面心對(duì)面心旋轉(zhuǎn)90(4)3面心對(duì)面心旋轉(zhuǎn) 180(2)6棱中對(duì)棱中 （無(wú)）(1)2(2)5方案數(shù)212C(12,6)+824C(4,2)+326C(6,3)/24=157888題 6: 用單純形法解下列線性規(guī)劃問(wèn)題。min2x+y 5x+y5 x+3y3 x,y0用工具（第六章課后題計(jì)算工具）計(jì)算.為 y=5/7,x=6/7,min2x+y=17/

7、7試卷 3題 1: 128 位的 0、1 串由 48 個(gè) 1，80 個(gè) 0 組成，證明至少有兩個(gè)點(diǎn)其位置差為 7 或者 14。設(shè) 47 個(gè) 1 的 位置分別為 a1,a2,.,a47.( 其中 a1a2.a47) 則設(shè)第二組數(shù)為 a1+6a2+6a3+6.a47+6 第三組為a1+12a2+12.a47+12 因?yàn)閍47128,a47+12140 但這三組數(shù)共有 473=141 個(gè)，鴿籠原理。必有兩數(shù)相等。題 2: 下面的棋盤(pán)中布 6 個(gè)棋子，為 1 的地方是1 0 0 0 0 01 1 0 0 0 00 0 1 1 0 00 0 0 1 0 00 0 0 0 1 00 0 0 0 1 1，求

8、方案數(shù)。的布子多項(xiàng)式為 (1+3x+x2)3 所求方案數(shù)為 6!-95!+304!-453!+302!-9+1=142題 3: 用字典序法，遞增、遞減、鄰位互換法求比 987654321 的序數(shù)小 99 的排列數(shù)。原中介數(shù)100 對(duì)應(yīng)進(jìn)制數(shù)新中介數(shù)對(duì)應(yīng)排列8765432140118765432140118765031098764132512345678130123455489675843211004500810044658758643219987615324題 4: 用火柴搭一個(gè)正 20 面體，求其方案數(shù)。若用一半紅火柴，一半藍(lán)火柴，求其方案數(shù)。不動(dòng): (1)30轉(zhuǎn)動(dòng)群1 個(gè)6 個(gè)6 個(gè)10 個(gè)15 個(gè)頂點(diǎn)對(duì)頂點(diǎn)旋轉(zhuǎn)72(5)6頂點(diǎn)對(duì)頂點(diǎn)旋轉(zhuǎn)140(5)6面心對(duì)面心旋轉(zhuǎn) 60(3)10棱中對(duì)棱中 （無(wú)）(1)2(2)14(1)方案數(shù) 230+1226+1226+102210/60(2)方案數(shù)230C(30,15)+2426C(6,3)+20210C(10,5)/60題 5: 上樓梯邁一步可以上一級(jí)，也可以上