Este problema se planteó en marzo de 2010 en el G4G9 en una charla del matemático japonés Hirokazu "Iwahiro" Iwasawa. Iwasawa afirma que existe una prueba sencilla de que N > 10, aunque no la compartió con el público, ya que demostrarlo es aparentemente un ejercicio esclarecedor por sí mismo.
Respuestas
¿Demasiados anuncios?
MortenSickel
Puntos
123
boost
Puntos
3169
Este enigma me lo contó el viernes pasado Peter Winkler (que había mencionado que se lo había contado un japonés que quizá sea al que te refieres).
La solución en el $n \leq 10 $ es considerar el embaldosado del plano mediante hexágonos de altura unitaria. Inscribimos dentro de cada uno de estos hexágonos un círculo unidad. Esta rejilla de círculos tiene una densidad > 0,90 en el plano, por lo que si se coloca al azar esta rejilla en el plano se espera que el número de puntos cubiertos > 9 (de los 10), y esto implica que existe una disposición que cubre 10. (faltan algunos detalles en este argumento del método probabilístico, pero se entiende la idea básica).
Creo que para el $n>10$ tenemos alguna forma de calcular un límite superior de la densidad de un empaquetamiento de esferas en el plano que lo descarta en general. (o algo parecido)
Zsbán Ambrus
Puntos
962
En la respuesta a los problemas abiertos de la geometría euclidiana? , Alexey Ustinov llama la atención sobre un artículo de 2012.
Greg Aloupis, Robert A. Hearn, Hirokazu Iwasawa, Ryuhei Uehara, Cubrir puntos con discos unitarios disjuntos , 24ª Conferencia Canadiense sobre Geometría Computacional (2012)
El resumen de ese artículo confirma que se trata del mismo problema y ofrece límites mejorados.
Consideramos el siguiente problema. ¿Cuántos puntos deben situarse en el plano para que ninguna colección de discos unitarios disjuntos pueda cubrirlos? La respuesta, k, ya se sabe que satisface 11 k 53. Aquí mejoramos el límite inferior a 13 y el superior a 50. También proporcionamos un conjunto de 45 puntos que aparentemente no se pueden cubrir, aunque esto se ha determinado mediante búsqueda por ordenador.
El artículo también afirma que el límite inferior de 11 se publicó en 2008
Gerry Myerson
Puntos
23836
0 votos
Omitir el no solapamiento en el título parece demasiado ingenioso.
1 votos
Tal vez me estoy perdiendo algo, pero el resultado parece obviamente falso: toma un punto rodeado por otros 9 puntos en un círculo pequeño, entonces ¿cómo vas a tener un disco que cubra el punto central sin tocar los puntos restantes? Si interpreto el problema como que no todos los puntos tienen que estar en un disco, entonces parece bastante trivial, porque todo lo que tengo que hacer es asegurarme de que cada vez que añada un nuevo disco, éste cubra al menos un punto, lo cual es ciertamente factible.
7 votos
Tal vez lo esté entendiendo mal, pero pensaba que MathOverflow era para hacer preguntas cuya respuesta no se conocía.
0 votos
Tal vez el autor original podría reformular su pregunta de modo que la segunda parte fuera la "pregunta" principal, y luego hacer que el título actual fuera un comentario para aportar contexto o interés.
0 votos
¿Existe un límite superior conocido (por ejemplo, mediante una construcción)?
0 votos
Esta es probablemente una pregunta mejor en AoPS que aquí. No me opongo a este tipo de preguntas aquí, pero creo que obtendrás más respuestas mejores allí.
2 votos
No se trata de un límite muy estricto, pero si se rellena, por ejemplo, un área de 2x2 con suficiente densidad de puntos espaciados uniformemente, independientemente de cómo se coloquen los discos, siempre quedarán algunos puntos sin cubrir en el área del "trébol invertido" donde se juntan tres discos.
2 votos
@DouglasS.Stones En este documento aparece un límite superior: arxiv.org/abs/1101.3468
2 votos
Creo que esta cuestión también es interesante en dimensiones superiores. ¿Cómo el número mínimo $N(d)$ (definidos de la forma obvia) crecen con la dimensión $d$ ?
4 votos
Aplicación práctica de esta pregunta: todos mis cubos son del mismo tamaño, ¿puedo seguir recogiendo toda el agua si mi tejado tiene goteras a las $N$ ¿puntos?
1 votos
@WlodAA "discos de unidad"
0 votos
@RobPratt, gracias (miro pero no veo).