2016五连珠问题及参考解答

五连珠问题问题1：特殊问题如图，在67的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或共顶点，那么称这两个棋子相连。现从这42个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连。请用数学的方法解决最少取出多少个棋子才可能满足要求？并说明理由。提示：如果证明至少需要取出个棋子。可采用的一种思路是：理论上证明取个棋子不能满足要求，而你确实找到一种取出个棋子就可以满足要求的取法。另一种思路是采用一种方法证明至少需要取个棋子才能满足要求，而你确实找到一种取出个棋子就可以满足要求的取法。当然或许你还有别的思路。在这个具体问题中，请你只用数学的方法解决该问题。问题2：二维一般问题对问题1中使用数学证明的方法，只能解决规模很小的问题。而且针对不同的规模，所使用的数学技巧会不同。这样就不具有一般性。如果现在需要你从一般性的问题考虑，你将如何解决这个问题呢？一个很自然的想法是利用数学建模的方法建立一般模型，然后设计算法或利用软件求解。基于此，请针对任意规模的棋盘，要求满足的条件与问题1相同。问至少去掉多少个棋子，可以使没有五个在一条直线（横、竖、斜方向）上依次相连。并对1317的长方形棋盘，给出具体的求解结果，并将最后结果给出直观的棋盘表格显示。问题3：三维问题若将该二维平面网格扩展到三维空间，得到一个的空间长方体网格。每个格子是一个111的小正方体。在这些格子中同样都填满了棋子，现要从中抽取一部分，使得在每种平面，包括横向所截的个平面，纵向所截的个平面，竖直方向所截的个平面，在每个平面上在横向、纵向、斜方向上都不出现5子连珠。并且要求在空间斜线上也不出现5子连珠。问最少去掉多少个棋子可以满足要求。请建立一般问题的数学模型。并针对676的空间网格用计算机求解，并给出具体的解结果。提示：如果用(i,j,k)三维坐标来表示空间的每个格子，对676网格，i=1,2,6;j=1,2,7;k=1,2,.,6。判断某些格子是否共线，可以通过判断这些格子是否在一条空间直线上来判断。如(1,1,1),(2,2,2),(3,3,3,),(4,4,4),(5,5,5),(6,6,6)这些格子在一条斜线上。(1,7,1),(2,6,2), (3,5,3),(4,4,4),(5,3,5),(6,2,6)这些格子也在一条斜线上。解答：问题1：去掉8个棋子。证明：对前5列，每行至少需要去掉1个棋子，则前5列至少需要去掉6个棋子。对后两列，每列至少需要去掉1个棋子，因此后两列至少需要去掉2个棋子。则总的至少需要去掉8个棋子。下面是一种去掉8个棋子而能满足条件的方式。 一种方案问题2：对mn的五连珠问题，建立一般线性规划模型为：建0-1决策变量，设我们的目标书去掉棋子数最少，则有目标函数为：下面建立约束每行连续5个格子中至少要去掉一个棋子，则有： 每列连续5个格子中至少要去掉一个棋子，则有： 每条反斜线上连续5个格子中至少要去掉一个棋子，则有：每条正斜线上连续5个格子中至少要去掉一个棋子，则有：因此总的线性规划模型为：约束总数：当时，问题2：Lingo程序!13*17的五连珠问题;model:sets:Line/1.13/;Column/1.17/;Lnum/1.9/;Cnum/1.13/;Rnum/1.5/;assign(Line,column):x;endsetsdata:text()=writefor(Assign(i,j)|x(i,j)#GT#0:x(,i,j,)=,x(i,j), );enddatamin=sum(assign(i,j):x(i,j);!单方向改变的约束;for(Lnum(i):for(column(j):sum(Rnum(r):x(i+r-1,j)=1); !i+方向得到的约束;for(Line(i):for(Cnum(j):sum(Rnum(r):x(i,j+r-1)=1); !j+方向得到的约束;for(Lnum(i):for(Cnum(j):x(i,j)+x(i+1,j+1)+x(i+2,j+2)+x(i+3,j+3)+x(i+4,j+4)=1); !反斜线约束;for(Lnum(i):for(Cnum(j):x(i,j+4)+x(i+1,j+3)+x(i+2,j+2)+x(i+3,j+1)+x(i+4,j)=1); !正斜线;for(assign(i,j):bin(x(i,j);end13*17个棋子需要44个棋子x(1,5)=1 x(1,10)=1 x(1,15)=1 x(2,3)=1 x(2,8)=1 x(2,13)=1 x(3,1)=1 x(3,6)=1 x(3,11)=1 x(3,16)=1 x(4,4)=1 x(4,9)=1 x(4,14)=1 x(5,2)=1 x(5,7)=1 x(5,12)=1 x(5,17)=1 x(6,5)=1 x(6,10)=1 x(6,15)=1 x(7,3)=1 x(7,8)=1 x(7,13)=1 x(8,1)=1 x(8,6)=1 x(8,11)=1 x(8,16)=1 x(9,4)=1 x(9,9)=1 x(9,14)=1 x(10,2)=1 x(10,7)=1 x(10,12)=1 x(10,17)=1 x(11,5)=1 x(11,10)=1 x(11,15)=1 x(12,3)=1 x(12,8)=1 x(12,13)=1 x(13,1)=1 x(13,6)=1 x(13,11)=1 x(13,16)=1 一种方案问题3：对mnp的五连珠问题，建立一般线性规划模型为：建0-1决策变量，设我们的目标书去掉棋子数最少，则有目标函数为：三个方向分别称为轴方向，轴方向，轴方向。下面建立约束(1)只变一个方向的约束：沿方向约束 沿方向约束 沿方向约束 (2)变两个方向的约束：沿方向约束 沿方向约束 沿方向约束 沿方向约束 沿方向约束 沿方向约束 (2)变三个方向的约束：沿方向约束该方向为图2中方向（1,1,1） 沿方向约束该方向为图2中方向（1,1，-1） 沿方向约束该方向为图2中方向（1,-1，1） 沿方向约束该方向为图2中方向（1,-1，-1） 图2 4条空间对角线方向示意图总共约束有3+6+4=13类。约束总数：当时，因此总的线性规划模型为：求解结果。minZ=64x(1,1,2)=1 x(1,2,5)=1 x(1,3,1)=1 x(1,3,3)=1 x(1,4,1)=1 x(1,4,6)=1 x(1,5,2)=1 x(1,5,4)=1 x(1,6,2)=1 x(1,7,5)=1 x(2,1,1)=1 x(2,1,3)=1 x(2,1,6)=1 x(2,2,4)=1 x(2,3,2)=1 x(2,4,4)=1 x(2,4,5)=1 x(2,5,5)=1 x(2,6,1)=1 x(2,6,3)=1 x(2,6,6)=1 x(2,7,1)=1 x(2,7,5)=1 x(3,1,4)=1 x(3,2,3)=1 x(3,3,3)=1 x(3,3,5)=1 x(3,3,6)=1 x(3,4,1)=1 x(3,4,3)=1 x(3,4,4)=1 x(3,5,2)=1 x(3,6,4)=1 x(3,7,3)=1 x(4,1,2)=1 x(4,2,1)=1 x(4,2,4)=1 x(4,3,1)=1 x(4,3,3)=1 x(4,3,5)=1 x(4,4,3)=1 x(4,4,4)=1 x(4,5,4)=1 x(4,5,6)=1 x(4,6,2)=1 x(4,7,4)=1 x(5,1,5)=1 x(5,2,2)=1 x(5,2,6)=1 x(5,3,4)=1 x(5,4,2)=1 x(5,5,1)=1 x(5,5,3)=1 x(5,6,5)=1 x(5,7,2)=1 x(5,7,6)=1 x(6,1,2)=1 x(6,2,5)=1 x(6,3,3)=1 x(6,4,1)=1 x(6,4,6)=1 x(6,5,4)=1 x(6,6,2)=1 x(6,7,5)=1 Lingo程序!问题3程序model:sets:xzhou/1.6/;yzhou/1.7/;zzhou/1.6/;numx/1.2/;numy/1.3/;numz/1.2/;numr/1.5/;assign(xzhou,yzhou,zzhou):x;endsetsdata:text()=writefor(Assign(i,j,k)|x(i,j,k)#GT#0:x(,i,j,k,)=,x(i,j,k), );enddatamin=sum(assign(i,j,k):x(i,j,k);!单方向改变的约束;for(numx(i):for(yzhou(j):for(zzhou(k):sum(numr(r):x(i+r-1,j,k)=1); !i+方向得到的约束;for(xzhou(i):for(numy(j):for(zzhou(k):sum(numr(r):x(i,j+r-1,k)=1); !j+方向得到的约束;for(xzhou(i):for(yzhou(j):for(numz(k):sum(numr(r):x(i,j,k+r-1)=1); !k+方向得到的约束;!两个方向改变的约束;for(numx(i):for(numy(j):for(zzhou(k):sum(numr(r):x(i+r-1,j+r-1,k)=1); !i+,j+方向得到的约束;for(numx(i):for(numy(j):for(zzhou(k):sum(numr(r):x(i+r-1,j+5-r,k)=1); !i+,j-方向得到的约束;for(xzhou(i):for(numy(j):for(numz(k):sum(numr(r):x(i,j+r-1,k+r-1)=1); !j+,k+方向得到的约束;for(xzhou(i):for(numy(j):for(numz(k):sum(numr(r):x(i,j+r-1,k+5-r)=1); !j+,k-方向得到的约束;for(numx(i):for(yzhou(j):for(numz(k):sum(numr(r):x(i+r-1,j,k+r-1)=1); !i+,k+方向得到的约束;for(numx(i):for(yzhou(j):for(numz(k):sum(numr(r):x(i+r-1,j,k+5-r)=1); !i+,k-方向得到的约束;!三个方向改变的约束;for(numx(i):for(numy(j):for(numz(k):sum(numr(r):x(i+r-1,j+r-1,k+r-1)=1); !i+,j+,k+方向得到的约束;for(numx(i):for(numy(j):for(numz(k):sum(numr(r):x(i+r-1,j+r-1,k+5-r