Saltar al contenido

¿Cuántos cuadrados se pueden formar usando n puntos?

Esta noticia fue aprobado por nuestros expertos así garantizamos la veracidad de nuestro contenido.

Solución:

En el avión $n$ los puntos pueden determinar como máximo $O(n^2)$ cuadrícula. Esto se debe a que dos puntos distintos pueden determinar hasta tres cuadrados.

En $R^3$ este argumento ya no se sostiene, ya que dos puntos pueden formar las esquinas de muchos cuadrados arbitrariamente. Como señala Gerhard, $O(n^3)$ es un límite superior (en cualquier dimensión) dado que tres puntos determinan como máximo un cuadrado.

Uno puede hacer un poco mejor que esto. Usando el teorema de Szemerédi-Trotter se puede demostrar que un conjunto de $n$ puntos en $R^3$ determina como máximo $O(n^7/3)$ triángulos rectángulos Resulta que $n$ los puntos determinan como máximo $O(n^7/3)$ cuadrados (ya que un cuadrado contendrá un triángulo rectángulo). Por otro lado, ciertamente es fácil ver que existen conjuntos de puntos con al menos $Omega(n^2)$ cuadrícula. el límite de $O(n^7/3)$ se sabe que es agudo para el problema menos restringido de contar triángulos rectángulos.

Actualizar: Un resultado de Sharir, Shefer y Zahl muestra que el número de triángulos similares entre sí en un punto establecido en $R^3$ es como máximo $O(n^frac157)$dónde $15/7 = 2.142ldots$lo que implica el mismo límite para el número de cuadrados.

Sin embargo, cerrar la brecha de los cuadrados parece un problema interesante y no trivial.

En k dimensiones, tome una unidad regular k simplex en k puntos y cópiela a una distancia ortogonal de 1. Esto da como resultado k elija 2 cuadrados unitarios en 2k puntos. Invito a otros a contar arreglos cuadrados en un hipercubo.

Combinatoriamente, no puede haber más cuadrados que tres conjuntos de un conjunto n. En efecto, dado que tres puntos de un cuadrado determinan el cuarto, hay como máximo un cuarto tantos cuadrados como tres conjuntos. Me imagino que Erdos puede tener un límite superior para arreglos planos, que debería ser del orden de n^2, ya que dos puntos cualesquiera en el plano determinan uno de los tres cuadrados que contienen esos dos puntos.

Gerhard “Puntos, manchas y nudos…” Paseman, 2020.07.05.

Sección de Reseñas y Valoraciones

Recuerda que puedes difundir este enunciado si te fue útil.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *