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個格點，它們構成正方形的頂點.