Puntos en el plano con cada par teniendo al menos dos puntos equidistantes?

Question

Me dieron esta pregunta en persona por un compañero aprendiz durante un descanso de una sesión de entrenamiento de la IMO, lo que me hizo pensar que este problema está relacionado con las Olimpiadas. ¡Estoy interesado en la solución tanto como en el origen!

$\textbf{Problema:}$ ¿Existe un conjunto finito no vacío de puntos $P$ en $\mathbb{R}^2$ tal que para cada par de puntos $x$, $y$ en $P$ existen al menos dos puntos distintos $a$ y $b$ en $P$ tales que tanto $a$ como $b$ están a la misma distancia de $x$ y $y$.

Para ser honesto, en más de una década y obtener un grado en Matemáticas, no he avanzado mucho en este problema. Intenté hacer algunos cálculos basados en el número de pares y el principio del cajón para llegar a la conclusión de que debe haber un punto que sea el circuncentro de un triángulo formado por puntos en $P$. Suponer que $P$ es una solución mínima (en términos de tamaño de $P$) no parece ayudar mucho.

EDICIÓN: originalmente la pregunta dejaba abierta la posibilidad de que fuera en el plano o en el espacio, pero el caso del espacio es trivial.

EDICIÓN EDICIÓN: agregada una nota para decir que el conjunto debe ser no vacío. ¡Tenga en cuenta que no necesitamos al menos dos puntos, porque cuando decimos "pares de puntos" no decimos "par de puntos distintos"!

Answer 1

Una imagen vale más que mil palabras:

... pero voy a escribir algunas palabras de todas formas. Esta configuración tiene muchas simetrías e interesantes propiedades, algunas de las cuales describiré aquí; sin embargo, recomiendo intentar explorar la configuración y descubrirlas por tu cuenta antes de seguir leyendo.

Los ocho puntos están dispuestos en dos cuadrados de diferentes longitudes de lado, con el mismo centro, y en un ángulo de 45 grados entre sí, el cuadrado interno coloreado de rojo y el externo coloreado de azul. También hay ocho triángulos equiláteros con vértices en los ocho puntos: cada lado del cuadrado interno rojo se completa con un triángulo rojo equilátero que apunta hacia afuera, y cada lado del cuadrado externo azul se completa con un triángulo azul que apunta hacia adentro.

Los doce segmentos rojos tienen longitudes iguales, al igual que los doce segmentos azules. Estas igualdades son suficientes para verificar que cualquier par de puntos tiene un par de puntos equidistantes. Hasta las simetrías, solo hay seis casos para revisar: dos donde ambos vértices son del cuadrado azul (adyacentes u opuestos); dos donde ambos vértices son del cuadrado rojo (adyacentes u opuestos); y dos donde cada vértice es de un cuadrado diferente (y la distancia entre los dos vértices es ya sea roja o azul). Los dos casos finales son los más bonitos e interesantes, y el segundo de los cuales se muestra en el diagrama, donde el bisector verde perpendicular de los dos puntos verdes pasa a través de un par diferente de puntos, obtenidos del primer par mediante una rotación de 90 grados.

---

No conozco el origen del problema, pero me encontré con él antes, en los foros (o "fora") de xkcd, hace por lo menos 10, quizás 15 años. Recientemente recordé este problema y lo presenté a algunos de nuestros estudiantes de la IMO. Mi intento por buscar la formulación original y mi respuesta original me han traído hasta aquí. Lamentablemente, los foros de xkcd parecen haber estado fuera de línea desde agosto de 2019, y al parecer no fueron archivados por completo (o al menos, no puedo encontrar tal archivo), por lo que algunas páginas pequeñas en la historia de esta pregunta podrían estar perdidas para siempre...

Answer 2

Antes de empezar, un poco de filosofía sobre este problema:

Sinceramente, creo que no existe dicho conjunto. He probado algunas configuraciones y no puedo encontrar una que funcione. Así que a partir de ahora, solo hablaré sobre cómo refutar el problema.

Este problema es claramente una pregunta de estilo geométrico-combinatoria. Según veo, no creo que la parte geométrica del problema sea muy importante; creo que solo las simples nociones de bisectrices perpendiculares y tal vez polígonos son suficientes. La parte importante es la parte combinatoria y aquí están las principales ideas que vienen a la mente:

• principio extremal
• principio del palomar
• doble conteo de cualquier cosa útil (ángulos, triángulos, aristas, etc.)
• considerar un grafo o el conjunto de líneas que pasan por (al menos) $2$ puntos o tal vez el conjunto de bisectrices perpendiculares del conjunto de segmentos

Sin embargo, aquí está el gran problema:

Nunca se nos dijo que los puntos no pueden ser colineales o formar líneas paralelas

Como un poco de teoría, decimos que algunos puntos están en posición general cuando ninguno $3$ son colineales y ninguna $2$ líneas formadas por puntos de nuestro conjunto son paralelas. ¡Así que nunca se nos dijo que el conjunto de puntos que estamos buscando está en posición general! ¡Esto significa que no podemos usar la mayoría de las ideas enumeradas anteriormente ya que es fácil encontrar contraejemplos!

Y aún así parece tan fácil.

He intentado varias aplicaciones del principio extremal y dobles conteos pero realmente no logré conseguir una contradicción. Sin embargo, ¡sí logré obtener una contradicción asumiendo que los puntos están en posición general! Así que aquí está la solución:

---

Sea $P$ el conjunto de puntos. Sea $S$ el conjunto de líneas que pasan exactamente por $2$ puntos de $P$. Observa que $|S|=\binom{n}{2}$ porque los puntos están en posición general.

Considera $S'$ el conjunto de las bisectrices perpendiculares de los segmentos cuyos extremos están en $P$. Debido a que hay $\binom{n}{2}$ segmentos cuyos extremos están en $P$ y los puntos están en posición general, hay $\binom{n}{2}$ bisectrices perpendiculares, por lo tanto $|S'|=\binom{n}{2}$.

SIN EMBARGO, para cualquier segmento $AB$ hay al menos $2$ puntos $X,Y$ que están en la bisectriz perpendicular del segmento, así que cada bisectriz perpendicular en $S'$ es en realidad una de las líneas en $S$, por lo tanto existe una inyección de $S'$ a $S$.

Pero hemos demostrado que $|S|=|S'|$, así que debe haber una bijección de $S'$ a $S$, así que cada línea que pasa por $2$ puntos de $P$ es la bisectriz perpendicular de un segmento cuyos extremos están en $P$.

Toma el envoltorio convexo de los puntos en $P$ y toma cualquier línea formada por $2$ puntos en el envoltorio convexo. Esa línea claramente no puede ser la bisectriz perpendicular de un segmento cuyos extremos están en $P$

$\mathcal{Q.E.D}$

---

El hecho de que los puntos estén en posición general nos permite demostrar que hay una inyección de $S'$ a $S$. Si los puntos pueden ser realmente colineales o formar líneas paralelas, entonces el argumento anterior es falso.

---

Para concluir, no existe dicho conjunto asumiendo que los puntos están en posición general. En cuanto al caso general, no estoy seguro. Para ser honesto, la declaración original podría implicar este detalle, y Cryvate podría haber olvidado agregarlo, porque en mi experiencia, el $99\%$ de los problemas geométrico-combinatorios involucran puntos en posición general.

---

EDICIÓN: $2$ personas han mencionado en los comentarios que la pregunta no involucraba posición general.

Sí, lo sé, simplemente quería mostrar una solución para el caso en el que los puntos están realmente en posición general y destacar por qué el problema es mucho más difícil cuando no lo están.

Discutí algunos enfoques y esto fue puramente teórico sobre el problema principal, mientras proporcionaba la solución para el caso especial.

Además, como dije antes, es altamente posible que si esto fuera en un campamento de preparación para una olimpiada, la pregunta original realmente involucrara posición general. Yo mismo soy un estudiante de olimpiadas y por lo que sé, el $99\%$ de estos problemas involucran posición general, y cuando no lo hacen generalmente involucran algo más, como coloraciones o condiciones suplementarias.

Answer 3

Sea $P$ el conjunto finito de puntos mencionados anteriormente. Por definición, para cada par de puntos $x$ y $y$, existe otro par diferente $a$ y $b$ que se encuentra en la línea que pasa por el punto medio de $x$ y $y$ y es perpendicular al segmento de recta $\overline{\rm xy}$ que une dichos puntos.

Sea $L$ el conjunto de todas las líneas que se pueden construir pasando por cada par de puntos en $P$ (este es un conjunto mucho más grande, pero aún finito). Ahora consideremos el par de líneas $l_1, l_2\in L$ que presentan el ángulo no nulo más pequeño entre ellas (puede haber más de uno, pero es suficiente con considerar un par). Entonces, existe un par de puntos $x_1\in l_1$ y $x_2\in l_2$ que no cumplen la condición, es decir, no hay otro par $a, b$ equidistante de $x_1$ y $x_2$, lo que conlleva a una contradicción.

Observa que si existiera tal par $a, b$, la condición "$l_1$ y $l_2$ teniendo el ángulo no nulo más pequeño entre ellas" no se cumpliría, ya que el ángulo entre $l_1$ o $l_2$ y la línea perpendicular al segmento $\overline{\rm x_1x_2}$ (la línea que pasa por $a$ y $b$) sería más pequeño.

Por lo tanto, $P$ y $L$ deben ser ambos conjuntos infinitos.