¿Cuántos círculos se necesitan para cubrir un rectángulo?

Question

VERDADERO O FALSO

Supongamos que un rectángulo en $R^{2}$ puede ser cubierto por (permitiendo solapamientos) $25$ discos de radio $1$ entonces también puede estar cubierto por $101$ discos de radio $0.5$ .

Por supuesto, aunque es una pregunta verdadera o falsa, me gustaría la lógica sobre ella y una posible prueba general.

La respuesta es verdadero pero no veo ninguna lógica específica.

P.D. La pregunta es del examen de ingreso 2012 a un programa de posgrado en el TIFR, Mumbai.

Answer 1

Esto es muy divertido, pero en realidad no es una pregunta de matemáticas.

Este es el truco: si 25 círculos pueden cubrir el rectángulo completo, entonces 25 círculos de medio radio pueden cubrir el rectángulo a media escala (es decir, cortando ambos lados por la mitad). Repite esto 4 veces, y verás que sí, 100 círculos de medio radio pueden cubrir el rectángulo completo.

Acabo de darme cuenta de que hay 101 círculos. Supongo que llevas el 101 $^{st}$ como un sombrero.

Answer 2

Bueno, ¿en realidad no se necesitarían menos en la mayoría de los casos?

Hay dos disposiciones básicas de círculos superpuestos que, entre ellos, abarcan un área sólida mayor que la de cada círculo individual. La disposición ortogonal es más fácil de visualizar sobre todo en relación con un rectángulo, así que la utilizaremos. Una iteración de esta disposición de círculos toma cinco de ellos; cuatro en un cuadrado con sus bordes tocándose, y uno en el medio llenando el hueco del centro.

Una iteración cubriría completamente un cuadrado de 2R de lado (no puede ser más ancho que el círculo central, de diámetro 2R, o parte del cuadrado quedaría fuera de los puntos adyacentes de los cuatro círculos exteriores). Si necesitas cubrir un rectángulo compuesto por dos de estos cuadrados, 2R*4R, necesitarías dos iteraciones del patrón, pero (aquí está lo bueno) dos de los círculos de cada iteración son congruentes entre sí, y son redundantes; 5 círculos de radio R cubren un cuadrado de 2R*2R, pero sólo se necesitan 8 para 2R*4R, no 10. Duplique el área de nuevo, a un cuadrado de 4R*4R, y necesitará 4 iteraciones de la forma original (2 del patrón rectangular de 7 círculos), pero ahora las cuatro iteraciones tienen un círculo que es congruente con uno de los otros tres, así como otro círculo congruente con otra iteración; eso es 7 círculos de 20 que son redundantes por lo que sólo necesita 13.

El número de círculos ortogonales de radio r que se necesitan para cubrir un rectángulo de área n*m donde n y m son múltiplos pares de r es la suma de dos productos relacionados de n y m; para cubrir cada dimensión del rectángulo con círculos, se necesita un círculo más por dimensión que la mitad del número de radios de la dimensión, por lo que el primer conjunto de círculos ortogonales es el producto de esas dos cantidades. Luego, el segundo conjunto rellena los huecos, y requiere el producto de la mitad del número de círculos que hay en cada dimensión. Así pues, $N(r,n,m) = (n/2r+1)(m/2r+1) + nm/4r$ . Si se reduce el radio a la mitad, se encuentra que $N(r/2,n,m) = (n/r+1)(m/r+1) + nm/2r$ y si en cambio duplicas las dimensiones encontrarás que $N(r/2,n,m) = N(r,2n,2m)$ .

Trabajando hacia atrás con esta fórmula, un rectángulo que requiere 25 círculos de radio r sería en realidad un cuadrado de 6r de lado; $N(r, 6r, 6r) = (6r/2r + 1)(6r/2r + 1) + (6r/2r)(6r/2r) = 4^2 + 3^2 = 25$ . Reduciendo a la mitad el radio de los círculos, necesitaríamos $N(r/2, 6r, 6r) = N(r,12r,12r) = 7^2 + 6^2 = 85$ . Ese es un extremo; el otro es un rectángulo (2r*16r), utilizando una variación del patrón de cobertura en la que un círculo cubre cada extremo corto y el resto de la forma se rellena con el patrón normal. En este caso, el número de círculos se reduce a la sencilla ecuación $N(r,2r,2xr) = 3x+1$ que cuando se resuelve para x=8 es 25. Si reducimos r a la mitad, el patrón más eficiente vuelve a ser el indicado anteriormente, por lo que $N(r/2, 2r, 16r) = N(r,4r, 32r) = 3*9 + 2*16 = 59$ .

Por lo tanto, aunque se necesitará más del doble de círculos cuando el radio se reduzca a la mitad, nunca se necesitará el cuádruple de círculos. Por lo tanto, la respuesta a la pregunta tal y como está planteada es "verdadera"; un rectángulo que requiere 25 discos de radio $r$ para cubrir con la superposición puede estar cubierto con 100 discos de radio $r/2$ de hecho, podría cubrir un más grande rectángulo con este número.

Answer 3

VERDADERO. Aquí está un bosquejo de mi prueba:

Intentamos encontrar el mayor rectángulo que puede ser cubierto por 25 discos de radio 1, y luego vemos cuántos discos de radio 0,5 son necesarios para cubrirlo. Ahora bien, dado un disco de radio 1, el mayor rectángulo posible que quede completamente cubierto por el disco es aquel en el que el disco dado será la circunferencia del rectángulo (dibuja tú mismo la figura).

Sean la longitud y la anchura de este rectángulo a y b => Área del rect=ab. Además, como la diagonal del rectángulo es el diámetro(=2) del disco obtenemos sqrt(a^2+b^2)=2 es decir a^2+b^2=4. Ahora, queremos maximizar (ab), sujeto a la condición (a^2+b^2-4)=0. Utilizando el método del multiplicador de Lagrange obtenemos que ab es máximo cuando a=b=sqrt(2). Por lo tanto, el área del mayor rectángulo que puede ser cubierto por un disco=ab=2.

Tenemos 25 discos de radio 1, por lo que 25 subrectángulos de área 2 formarán el mayor rectángulo que puede ser cubierto por 25 discos de radio 1.

\=>Área del mayor rect. que pueden cubrir 25 discos de radio 1=25x2=50.

Ahora aplicamos el mismo procedimiento para discos de radio 0,5 para encontrar el área del mayor rectángulo que puede ser cubierto por un disco de radio 0,5. Aquí obtenemos a=b=1/cuadrado(2). Por lo tanto, el área de cada subrect.=ab=0,5

Por lo tanto, el número de subrectángulos necesarios para cubrir un rectángulo de área 50=100. Por lo tanto, el número de discos de radio 0,5 necesarios para cubrir un rectángulo de área 50 es 100 (ya que cada disco cubrirá completamente un subrectángulo).

\=> 101 discos de radio 0,5 también cubrirán el rectángulo.