Question

【題目】平面直角坐標(biāo)系中有16個(gè)格點(diǎn)(i，j)，其中0≤i≤3，0≤j≤3.若在這16個(gè)點(diǎn)中任取n個(gè)點(diǎn)，這n個(gè)點(diǎn)中總存在4個(gè)點(diǎn)，這4個(gè)點(diǎn)是一個(gè)正方形的頂點(diǎn)，求n的最小值.

Answer 1

【答案】11.

【解析】

分兩步來(lái)證明：先找到10個(gè)點(diǎn)，它們中的任意四點(diǎn)不能構(gòu)成正方形的頂點(diǎn)，再根據(jù)抽屜原理證明任意的11個(gè)點(diǎn)，一定存在4個(gè)點(diǎn)為正方形的四個(gè)頂點(diǎn).

存在下面的10點(diǎn)即：

點(diǎn)(0，0)，(1，0)，(2，0)，(2，1)，(3，1)，(0，2)，(3，2)，(0，3)，(1，3)，(3，3)，

其中任意4個(gè)點(diǎn)不能構(gòu)成正方形的頂點(diǎn)，故.

下證：任意11點(diǎn)中，一定存在4個(gè)點(diǎn)為正方形的四個(gè)頂點(diǎn).

因?yàn)楣踩?/span>11個(gè)點(diǎn)，分兩種情況討論：

（1）有一行有4個(gè)點(diǎn)（設(shè)為），則余下三行共有7個(gè)點(diǎn)，

由抽屜原理知余下三行中必有一行至少有3個(gè)點(diǎn)（設(shè)為），

因，分布在兩行，

若該兩行相鄰或中間隔一行，則存在四個(gè)點(diǎn)，它們?yōu)檎�方形的四個(gè)頂點(diǎn)；

若該兩行間隔兩行，如圖，不妨設(shè)為線(xiàn)段上的格點(diǎn)，為線(xiàn)段上的格點(diǎn)，對(duì)應(yīng)的點(diǎn)的坐標(biāo)為，

余下4個(gè)點(diǎn)分布在中間兩行，若線(xiàn)段上有兩個(gè)整點(diǎn)，則它們和中的兩點(diǎn)構(gòu)成正方形的頂點(diǎn)，否則線(xiàn)段上至少有3個(gè)點(diǎn)，則其中必有兩個(gè)格點(diǎn)與中的兩點(diǎn)構(gòu)成正方形的頂點(diǎn).

（2）任意一行都沒(méi)有4個(gè)點(diǎn)，則各行的格點(diǎn)數(shù)分別為，故4行中必有相鄰兩行各有3個(gè)格點(diǎn)，這6個(gè)格點(diǎn)中必存在4個(gè)格點(diǎn)，它們構(gòu)成正方形的頂點(diǎn).