在4x1993的方格盘上放棋子，每格至多一子。问至多放多少棋子，使不存在任4枚子构成一个正方形。

4486

1999

答案应该是1999.

解法如下:每排的集合分别为A1,A2,A3,A4.Ai交Aj最多只能有一个元素,否则会构成一个四边形.所以Nmax=1993+C(4取2)=1999.

这题的类似题目为:

M是平面上所有点(x,y)的集合,其中x,y均是整数,且1<=x<=12,1<=y<=13.证明:不少于49个点的M的每一个子集,必包含一个矩形的四个顶点,且此矩形的边平行于坐标轴.

1999？

第一排放1993个，第二排隔一个放一个，就不止1999了。

哦,原来是正方形,我太粗心了,谢谢cross(该怎么称呼列).让我再想想.

算出来了,答案应该是4983个.

首先在4x4中(用i#j表示方位,例如1#2表示第1排第2个)最多可融入10个(这里的正放形可以不平行于长和宽,即1#2,2#1,2#3,3#2这种情况也就属于正方形.)排法下:

1#1.1#3.1#4.2#1.2#2.3#3.3#4.4#1.4#2.4#3而且不会影响下个4x4的排法.

好象有问题,没有考虑1#3.2#1.3#4.4#2这种正方形的情况．５５５５５５５５５５

请再想想

[此贴子已经被作者于2006-4-14 19:24:08编辑过]