Garantizar un centroide de punto de red entero

Question

Mi pregunta es la siguiente:

Escribir $n(4)$ sea el número mínimo de puntos enteros de la red en el plano para que unos cuatro de ellos determinen un centroide de punto entero de la red, demuestre que $n(4)=13$ .

En un ejercicio anterior he demostrado, utilizando el principio de encasillamiento, que entre cinco puntos enteros distintos de la red, el punto medio de dos de ellos será también un punto entero de la red. Este hecho es necesario para resolver el problema anterior.

¿Puede alguien ayudar, por favor?

Actualización: A partir de los comentarios de abajo he conseguido demostrar que $n(4)\le 13$ . Para completar la prueba queda demostrar que $n(4)>12$ . En otras palabras, se necesita un conjunto de 12 puntos enteros de la red que evite tener cualquier subconjunto que produzca un centroide de punto entero de la red.

Answer 1

El hecho de que 13 puntos es suficiente para garantizar algún conjunto de cuatro con centroide de punto de celosía se ha demostrado en los comentarios, gracias a Steve Kass. Esta respuesta es, con suerte, un ejemplo de 12 puntos que no funcionan, como sugiere hardmath.

EDIT: como señala hardmath en un comentario, un intento anterior no funcionó. Este es uno que he comprobado en arce.

Para doce puntos que no tienen ningún subconjunto de 4 con centroide en un punto de la red, considere los puntos de la red:

$$(0,0),\ (0,4),\ (0,8),$$ $$(1,2),\ (1,6),\ (1,10),$$ $$(2,1),\ (2,5),\ (2,9),$$ $$(3,3),\ (3,7),\ (3,11).$$ Obsérvese que hay tres en cada grupo que son congruentes mod $(Z_4)^2$ . Así que otra forma de ver el cálculo es considerar tres cada uno de los primeros términos de las cuatro listas, y mirar las sumas mod $4$ .

Hice una comprobación de todos los conjuntos de 4 de los vértices anteriores en arce, para verificar que ninguna de las sumas tiene ambas coordenadas $0 \mod 4$ y por lo tanto ninguno de los centroides son puntos de la red.

He aquí un esbozo de cómo se puede comprobar el ejemplo "a mano". Supongamos que se tiene el multiconjunto $A=\{ 0,0,0,1,1,1,2,2,2,3,3,3 \}$ de residuos mod 4. (tres de cada residuo). Entonces sólo hay las siguientes seis formas de hacer una suma de $0$ mod $4$ de $A$ y al lado de cada uno, entre paréntesis, el valor mod 4 de esa suma después de intercambiar los residuos $1$ y $2$ :

$0+0+2+2$ : [ $2=0+0+1+1$ ]

$1+1+3+3$ : [ $2=2+2+3+3$ ]

$0+0+1+3$ : [ $1=0+0+2+3$ ]

$1+1+2+0$ : [ $2=2+2+2+0$ ]

$2+2+3+1$ : [ $3=1+1+3+2$ ]

$3+3+0+2$ : [ $3=3+3+0+1$ ]

Una mirada a los cuatro puntos de la red "generadora" $(0,0),(1,2),(2,1),(3,3)$ muestra cómo se obtuvo el conjunto generador utilizando cada clase de residuo mod 4 como primera coordenada, y utilizando la primera coordenada con 1 y 2 permutados como segunda coordenada. A continuación, cada uno de los pares generadores se incrementó simplemente mod 4 en las segundas coordenadas para obtener 12 puntos distintos de la red.

Answer 2

Inicialmente coffeemath y yo buscamos subconjuntos de doce puntos de una cuadrícula de 4x4, como el siguiente (que resulta ser un "mal ejemplo"):

x  x  x  o
x  x  o  x
x  x  o  x
x  x  x  o

Este es un enfoque natural porque las coordenadas de los puntos pueden reducirse en módulo 4 sin afectar a la propiedad del centroide entero. Sin embargo, al hacerlo, puntos distintos pueden ser enviados a una imagen común, dando así menos de 12 puntos en la cuadrícula 4x4. El ejemplo de coffeemath ilustra esto, ya que sólo hay 4 imágenes distintas cuando se reduce mod 4.

Decidí investigar si existe un subconjunto de doce puntos de estos 16 puntos, libre de subconjuntos de 4 centros enteros. Aunque $\binom{16}{12} = 1820$ existen posibilidades, con algunas ayuda de Dan Shved sobre la combinación de simetrías de la cuadrícula 4x4 En el caso de la mayoría de los casos, éstos pueden reducirse a sólo 33 casos representativos. Así podría comprobarlos a mano: todos incluyen subconjuntos de 4 puntos con centroides enteros.

A continuación, he investigado el número máximo de puntos que se pueden tomar de la malla 4x4 sin obtener un centroide 4-subconjunto tan entero. Resulta que se pueden tomar como máximo 8 puntos. Hasta las simetrías comentadas en el enlace anterior, sólo hay tres formas de alcanzar ese límite. Abajo x denota los puntos incluidos en el subconjunto, sin embargo cada solución resulta ser simétrica con su complemento:

x  x  o  o  |  o  x  x  o  |  o  x  o  x  
x  x  o  o  |  o  o  x  x  |  o  x  o  x  
x  x  o  o  |  x  o  o  x  |  x  o  x  o  
x  x  o  o  |  x  x  o  o  |  x  o  x  o  

La disposición de 12 puntos más compacta y simétrica que he encontrado es en una cuadrícula de 6x6:

o  x  o  o  x  o
x  x  o  o  x  x
o  o  o  o  o  o
o  o  o  o  o  o
x  x  o  o  x  x
o  x  o  o  x  o

Ninguno de los arreglos de 8 puntos en una cuadrícula de 4x4 mostrados anteriormente se extiende a un subconjunto de 12 puntos de una cuadrícula de 5x5, lo que sugiere que no hay subconjuntos factibles de 12 puntos de una cuadrícula de 5x5.