Polígono en una cuadrícula

Question

Dado un cuadrado construido en una cuadrícula de puntos con coordenadas enteras, ¿cuál es su área máxima, si sabemos que hay exactamente 3 puntos de cuadrícula en su interior?

No tengo idea de cómo empezar. Busqué en Google y descubrí que existe un teorema de Pick, pero nuevamente no sé cómo usarlo.

Answer 1

Este es AHSME 1998 #29. AoPS hilos. La formulación en ese concurso fue de opción múltiple; que estiman que el área máxima era más cercano, entre los $4.0$, $4.2$, $4.5$, $5.0$, e $5.6$. Tomando el concurso de vivir de nuevo en 1998, estoy bastante seguro de que este es uno de los cinco preguntas que me dejaron en blanco.

Usted ha mencionado la selección teorema. Ese teorema conduce a un área de estimación de $4$, a partir de cuatro celosía puntos en los vértices y tres en el interior. Pero la selección teorema tiene una condición previa - todos los vértices deben ser de celosía puntos. El problema no especificar que, por lo que el teorema no se aplica.

Tengo un argumento en uno de los enlaces de los hilos, que se encuentra por perseguir a un callejón sin salida, que descartó la más grande de opción múltiple opción.
Tomamos los tres puntos $(0,0)$, $(1,0)$, e $(0,1)$ nuestras tres interior de entramado de puntos, por lo que el centro de la plaza se encuentra dentro de ese triángulo. A continuación, los tres más cercanos de celosía puntos fuera de ese triángulo debe ser fuera de la plaza, a una distancia de al menos $\frac{s}{2}$ desde el centro. En el caso interesante, estos tres puntos serán en $(1,1)$, $(0,-1)$, e $(-1,0)$ - todo lo demás está más lejos desde el centro de uno de estos puntos. El circuncentro de los tres puntos es en $(\frac16,\frac16)$, a una distancia $\frac56\sqrt{2}$ a partir de cada uno de ellos. Desde que, $s \le \frac53\sqrt{2}$.
Pero espera - que el ajuste de un círculo, no un cuadrado. Sólo podemos tener las distancias igual a $\frac s2$ si los tres puntos son puntos medios de los lados, formando un triángulo isósceles rectangular. No, por lo que este extremo es imposible, y $s$ es significativamente menor que el $\frac53\sqrt{2}$, para un área significativamente menor que el de $\frac{50}{9}\approx 5.6$.

Entonces, es bastante fácil de encontrar la configuración de la zona de $4.5$ (@Takahiro Waki de la primera foto). La configuración de la zona de $5.0$ (@Takahiro Waki de la segunda foto) es más difícil de encontrar, pero está ahí.

Eso es suficiente para responder a las preguntas de múltiples opciones problema - que era un auténtico problema difícil, para un concurso con un tiempo límite de tres minutos por problema en promedio. Pero estamos trabajando con los más altos estándares de aquí, queremos mostrar que el supremum de área es exactamente $5$.

Volvamos a los puntos que he mencionado. Suponga que $A=(0,0)$, $B=(1,0)$, e $C=(0,1)$ están en la plaza del interior, de modo que $(1,1)=D$, $(0,-1)=E$, e $(-1,0)=F$ están dentro o fuera de sus límites. Pongamos nombre a la plaza así; llamarlo $Q$. Los segmentos de $DE$ e $DF$ pasan a través del triángulo $ABC$, por lo que pasar a través de $Q$'s interior. Aquí está una foto, con una versión de la zona-5 cuadrado dibujado en:

Podemos describir cada punto fuera de la $Q$ como ser en uno o dos lados de $Q$; cada uno de los lados es descrito por una desigualdad lineal, y comprobamos que de estas desigualdades están satisfechos. Pretendemos que la distancia entre dos puntos en lados opuestos de $Q$ es de al menos el lado de longitud $s$ de $Q$. Por qué? Debido a que los lados son líneas paralelas; la distancia más corta entre los puntos en las dos líneas es el ortogonal de la distancia entre las líneas.
También, si un segmento de $XY$ ($X,Y$ fuera de $Q$) intersecta $Q$, a continuación, $X$ e $Y$ no están en el mismo lado de la $Q$. Si fuera así, todos los puntos en el segmento de entre ellos cumplen la misma desigualdad lineal.

Así que ahora, miramos a nuestros tres puntos de $D,E,F$. Que los lados son ellos? La etiqueta de los lados en un orden cíclico $S_1,S_2,S_3,S_4$. WLOG, $D$ es en la cara $S_1$. Desde $DE$ e $DF$ ambos se cruzan $Q$ni $E$ ni $F$ puede estar en el lado de la $S_1$. Si bien $E$ o $F$ es en la cara $S_3$, $DE=DF=\sqrt{5}\ge s$ y el área de $Q$ es en la mayoría de las $5$. Si uno de $E$ e $F$ es en la cara $S_2$ y el otro está en el lado $S_4$, a continuación, $EF=\sqrt{2}\ge s$ y el área de $Q$ es en la mayoría de las $\sqrt{2}$. Eso deja sólo una posibilidad para un área mayor que $5$: tanto $E$ e $F$ están en el mismo lado de la $S_2$ (WLOG) de $Q$.

Ahora, desde la $D$ está en el lado opuesto de $S_1$ de $B$ e $C$, la línea de $S_1$ debe intersectar segmentos de $BD$ e $CD$ sin tocar $B$ o $C$. Como tal, tiene pendiente negativa. Del mismo modo, la línea de $S_2$ debe intersectar segmentos de $AE$ e $AF$ sin tocar $A$, por lo que tiene pendiente negativa así. Pero $S_1$ e $S_2$ son perpendiculares; si uno tiene pendiente negativa, el otro también. Esto es una contradicción, y esta configuración es imposible.

Con ese caso descartado, el área se encuentra en la mayoría de los $5$. Ya hemos demostrado que un área de exactamente $5$ es posible, y hemos terminado.

Answer 2

Experimentalmente, tengo que estar de acuerdo en Takahiro Waki la respuesta de un área de 5.

La plaza está delimitada por un punto en cada lado: $I$, $F$, $G$ e $O$, por lo que no puede extender sobre uno de sus lados. Esa es mi intuición sobre el por qué de esta plaza tiene el área más grande, pero yo no lo sé de seguro.

También, Escoge el teorema de no trabajo aquí desde los vértices de la plaza no tiene que ser en coordenadas enteras, y no creo que hay un factor de escala que nos permite analizar todas las posibilidades.

Answer 3

Pensemos en la plaza que tutorial izquierda y arriba del punto, entonces nos encontramos próximos dos cuadrados es extremal.

En primer lugar, esta plaza es $\dfrac{9}{2}$. Entonces esto no puede ser más grande que la plaza de rotación o de estiramiento.

La siguiente imagen es la plaza de qué lado es $\sqrt{5}$.