2010考前复习_669801681.ppt

“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有?(n+1)/n?=2个鸽子。” 出现ak + ak+1 + ··· + al累加,多半要构造 出现奇偶性,整除,多半要取mod 整点问题 反证法 内点问题 多次利用鸽巢 Sj = ∑ai　 i =1 j 证明：在平面直角坐标系中，33个整点中必有9个整点的重心仍是整点。 证：先证明9个整点中必有3个整点的重心的仍是整点。（证明方法请参照整点问题ppt） 33个整点中必有9个3点组，每组的重心仍是整点。 33个中有3个整点为重心整点， 剩下30个，取3个整点为重心整点， 剩下27个，取3个整点为重心整点， 。。。 剩下9个，取3个整点为重心整点， 而这9个重心中必有3个的重心仍是整点，从而就证明了33个整点中必有9个整点的重心仍是整点。 9组 在边长为1的正方形内任取5个点试证 其中至少有两点，其间距离小于 证　把１×１正方形分成四个－×－的 正方形．如下图： 1 2 1 2 则这５点中必有两点落在同 一个小正方形内．而小正方 形内的任两点的距离都小于 第四章 Burnside引理:设G={a1,a2,…ag}是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。 G将[1,n]划分成l个等价类.c1(ak)是在置换ak的作用下不动点的个数。 l=[c1(a1)+c1(a2)+…+c1(ag)]/|G| Pólya定理 设G={P1,P2,…,Pg}是n个对象的一个置换群，C(Pk)是置换Pk的循环的个数，用m种颜色对n个对象着色, 着色方案数为 母函数型Pólya定理 Sk=(b1k+b2k+…+bmk),k=1,2…n C(P1) C(P2) C(Pg) 1 |G| l=—[m +m +…+m ]. 1 |G| i=1 k=1 n g P(G)= ∑ ∏Skck(pi) 熟悉各种凸多面体的转动群 欠角和的概念 平面多边形的转动群 注意不动图象 4.6 举例 足球： 正5边形内角108o，正六边形内角120o 欠角=360o –(108o +2·120o )=12o 720 /12 =60(个顶点) 60·3/2=90(条棱) 60/5=12(个5边形) 60·2/6=20(个6边形) 10根红、10根蓝、10根绿火柴搭一个正20面体， 有多少方案？ 解：正20面体有正3角形组成，12个顶点，30条棱，20个面 置换群为： 不动：(1)30 1个 (30!/10!10!10!)*230 （30根火柴的可重排列,火柴头两个方向,相当于二着色） 顶点—顶点: (5)6 24个 (6!/2!2!2!)*26 （12个顶点，6个轴，4个转动角度） ( 5根火柴一组,共6组，每组中5根火柴颜色必须相同，才有不动图象) 面心—面心 (3)10 20个 （20个面，10个轴，2个转动） （每组3根火柴,一共10个组，3根火柴颜色必须相同，才有不动图象,颜色无法平分,故无不动图象） 棱中—棱中 (1)2(2)14 15个 （火柴有方向，无不动图象） 方案数：L=((30！/10！10！10！)*230+24*(6！/2！2！2！)*26)/60 第六章 线性规划 标准形式 二阶段法 若第一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解 大M法 如果是求极大值，需加-M；如果是求极小值，需加M。 如基变量中还存在M，就不能实现极值。 约束 条件： 加入松弛变量 加入人工变量 先减去 再加上 换出变量 找λj0或min(λj) λj0或者max(λj) 换入变量 最优解 min max λj ≤ 0 λj ≥ 0 例： 第一阶段：将人工变量迭代出去，从而找到原问题的基础可行解 ，构造如下模型： 若W=0,说明问题存在基本可行解，可以进行第二个阶段； 否则，原问题无可行解，停止运算。 ⑵.两阶段法： cj 0 0 0 0 0 1 1 cB xB b P1 P2 P3 P4 P5 P6 P7 0 x4 11 1 -2 1 1 0 0 0 11 1 x6 3 -4 1 2 0 -1 1 0 3/2 1 x7 1 -2 0 1 0 0 0 1 1 Z 4 6 -1 -3 0 1 0 0 0 x4 10 3 -2 0 1 0 0 -1 － 1 x6 1 0 1 0 0 -1 1 -2 1 0 x3 1 -2 0 1 0 0 0 1 － Z 1 0 -1 0 0 1 0 3 0 x