Question

【题目】平面直角坐标系中有16个格点(i，j)，其中0≤i≤3，0≤j≤3.若在这16个点中任取n个点，这n个点中总存在4个点，这4个点是一个正方形的顶点，求n的最小值.

Answer 1

【答案】11.

【解析】

分两步来证明：先找到10个点，它们中的任意四点不能构成正方形的顶点，再根据抽屉原理证明任意的11个点，一定存在4个点为正方形的四个顶点.

存在下面的10点即：

点(0，0)，(1，0)，(2，0)，(2，1)，(3，1)，(0，2)，(3，2)，(0，3)，(1，3)，(3，3)，

其中任意4个点不能构成正方形的顶点，故.

下证：任意11点中，一定存在4个点为正方形的四个顶点.

因为共取11个点，分两种情况讨论：

（1）有一行有4个点（设为），则余下三行共有7个点，

由抽屉原理知余下三行中必有一行至少有3个点（设为），

因，分布在两行，

若该两行相邻或中间隔一行，则存在四个点，它们为正方形的四个顶点；

若该两行间隔两行，如图，不妨设为线段上的格点，为线段上的格点，对应的点的坐标为，

余下4个点分布在中间两行，若线段上有两个整点，则它们和中的两点构成正方形的顶点，否则线段上至少有3个点，则其中必有两个格点与中的两点构成正方形的顶点.

（2）任意一行都没有4个点，则各行的格点数分别为，故4行中必有相邻两行各有3个格点，这6个格点中必存在4个格点，它们构成正方形的顶点.