Dada una $k^2$ -conjunto recordado $S$ de puntos con coordenadas $(x,y)\in \{ 1,2,...,k \}$ demostrar que algunos $4$ puntos en $S'$ se encuentran en un círculo.

Question

Se nos da una $k^2$ -conjunto recordado $S$ de puntos en un plano. Las coordenadas de los puntos son números enteros entre $1$ y $k$ . A continuación, construimos otro conjunto $S'$ que contiene al menos $\frac{5}{2} k-1$ puntos de S. Debemos demostrar que siempre hay al menos $4$ puntos en $S'$ que se encuentran en un círculo común.

La situación equivale a una $k$ por $k$ cuadrado con una cuadrícula de números enteros, los miembros de $S$ siendo todos los vértices de la cuadrícula. Una cierta porción de los puntos, $k^{2}-\frac{5}{2}k+1$ de ellos, se retira entonces. Para $4$ para estar en una circunferencia, basta con que estén en los vértices de un trapecio isósceles. Por tanto, basta con demostrar que quitando $k^{2}-\frac{5}{2}k+1$ puntos nunca es suficiente para eliminar todas las posibles subsecciones que forman un trapecio isósceles de la cuadrícula cuadrada.

Este problema es bastante interesante porque el enunciado reformulado visualmente parece muy intuitivo, pero no estoy seguro de cómo proceder para demostrarlo rigurosamente, especialmente en lo que respecta a la cantidad específica $k^{2}-\frac{5}{2}n+1$ .

Le agradecería cualquier ayuda.

Answer 1

Dejemos que $M$ sea el conjunto de puntos que son los puntos medios de $p$ y $q$ , donde $p$ y $q$ son puntos en $S'$ con el mismo $y$ -(así que en la misma fila de $S$ ). Si hay dos puntos distintos de $M$ con el mismo $x$ -coordenada, entonces existirá un trapecio isósceles en $S'$ y, por tanto, cuatro puntos en $S'$ en un círculo.

Para cada $i\in \{1,\dots,k\}$ , dejemos que $r_i$ sea el número de puntos en $S'$ cuyo $y$ -coordinación es $i$ . I reclamar hay al menos $2r_i-3$ puntos medios distintos en $M$ cuyo $y$ -coordinación es $i$ . Una vez que el reclamar está probado, el número total de puntos medios distintos en $M$ sería $$ \sum_{i=1}^k (2r_i-3)=2\sum_{i=1}^k r_i-\sum_{i=1}^k3\ge 2(\tfrac52k-1)-3k=2k-2. $$ Hay al menos $2k-2$ puntos medios en $M$ pero hay $2k-3$ posible $x$ -coordenadas para estos puntos medios (¿por qué?). A continuación, puede concluir con el principio de encasillamiento.

Para ayudar a probar la afirmación, aquí hay una pista, detrás de un bloque de spoiler en caso de que quieras intentar resolver el problema sin ella:

Supongamos que hay cuatro puntos en una fila, cuyo $x$ las coordenadas son $\{a,b,c,d\}$ , donde $a<b<c<d$ . Entonces $(a+b)/2,(a+c)/2,(a+d)/2,(b+d)/2,$ y $(c+d)/2$ son todos los puntos medios distintos de esa fila.

Answer 2

Para que 4 puntos estén en una circunferencia, tienen que estar en los vértices de un subcuadrado.

Esto no es cierto. Consideremos el círculo que pasa por (2, 1), (1, 2) y (1, 3). También pasará por (2, 4), por simetría. De hecho, una condición suficiente (aunque no sé si necesaria) es que los puntos sean vértices de un paralelogramo isósceles.