24.1.08

1362.- Problem(it)a

¿Cuál será el máximo número de cuadraditos de lado 1 que se pueden meter dentro de un círculo de radio 100 sin que se salgan ni se superpongan?

cuánto hace que no ponía un problem(it)a! Se escuchan soluciones, especialmente aquellas ingeniosas y raras, aunque no sean necesariamente correctas.

34 comentarios:

pablotossi dijo...

uf, sin pensar: 314,1592...?

(esto de no pensar es algo peligroso y que me expone al linchamiento en la plaza?)

JuanPablo dijo...

no, tiene que ser un número entero.

pero tranqui, que no pasa nada. Tenés un uno.

Anónimo dijo...

4*(70^2+2 \sum_{n=71}^99 ([[\sqrt{100^2-n^2}]])), o sea 16 316.

Uhm...No estoy muy satisfecho con mi aproximación. Mejor no firmo. :P

JuanPablo dijo...

?! tenés un uno.

pablotossi dijo...

gracias por el uno, ahora me pogo a pensar...

y por cierto, está bien que use mi tumblr para los rants y ramblings que voy recolentando en iternet... pero que ALGUIEN firme con ese link haciéndose pasar por mí no es ético... además que no soy para nada importante como para que anden suplantando mi identidad.

Juan Pablo, borrá el comment anterior que no es mío, o cambiále el nick.

Gracias.

26 dijo...

Para ganarme mi 1 no me mojaré mucho:
Más de 20000 y menos 40000
(que son las areas de los cuadrados que respectrivamente se inscribe en y circunscribe al circulo de radio 100)

¿o precisas mas precisión?

Tom dijo...

No tengo la menor idea. Completamente desorientado. Ni siquiera cómo empezar. Para la próxima prometo pensar. Cosas por pensar:
a) ¿Cómo empiezo a poner cuadraditos para optimizar el area cubierta?. Ejemplo: ¿Cuántos cuadraditos de lado 1 entran en un círculo de radio 2?. A hacer dibujitos. Entran 5 (con uno en el centro, en forma de flor) y no 4 (formando un duadrado). ¿podrían entrar más con otro ordenamiento?
b) Ya estoy llegando tarde al trabajo

hjg dijo...

31111

conjeturo aproximación asintótica:
puede aproximarse bastante bien (para cuadraditos chicos) por

(pi * R^2 - 3 h R)/h^2

(h es el largo del lado del cuadrado)
o para h=1

3.1416 * R^2 - 3 R = 31115.9

pablotossi dijo...

profesor, vengo por otro uno:

cof640cof

JuanPablo dijo...

eh, pablo, borro el comment!

JuanPablo dijo...

todos tienen un uno, menos 26, que se aganó un abrazo, tanto tiempo, che! qué es de tu vida?

JuanPablo dijo...

(bue, 26 también tiene un uno)

tom, buen razonamiento. Calculo que ese es el óptimo

hernán, el truco del área es bueno, y es de lo mejor para aproximar asintóticamente cosas. Hasta el día de hoy es un problema abierto mejorar el orden de ese error (se calcula que es un problema más difícil que la hipótesis de Riemann)

Frenzo dijo...

Propondría:

N = 2 Suma (desde k = 0.5 hasta 98.5) de la parte entera de [(10000 - k^2)^0.5]

Con el excel, la cuenta da 31272.

¿Vuelvo en marzo?

Frenzo dijo...

Ups, falta un "2" antes del corchete...

Frenzo dijo...

Y conté dos veces la primera columna. Vuelvo en marzo.

JuanPablo dijo...

jajajaja! ok, tenés un uno, entonces!

26 dijo...

Juan Pablo, no te doy las gracias por el 1, que lo tengo más que merecido, pero si lo hago por el abrazo, Gracias, ¿la vida? la vida es maravillosa como siempre. Estaré por donde antes viendo si puedo recuperar mi viejo rincón de acertijos.

Martin dijo...

Usando la idea de frenzo, me da 31190.

Imaginemos el círculo centrado en el origen. La idea es llenar cada medio círculo independientemente; poner una columna de 99 apoyada en el eje x y centrada en el eje y; después, en cada cuadrante, aproximar con la suma de Riemann

\sum_{j=1}^{99} sqrt(100^2 - (j+1/2)^2)

Para cada cuadrante tengo 7699, y sobre los ejes 99+99+98+98 (se "pierden" dos cuadrados por la superposición en el origen).

Anónimo dijo...

Realmente es un problema abierto?

Martin dijo...

Yo supongo que no, pero no sabría dónde buscar la solución.

Juan Pablo?

hjg dijo...

Seguramente es un problema abierto, suena practicamente imposible demostrar que tal o cual empaquetamiento es óptimo (por supuesto que, razonablemente y con la ayuda de las computadoras uno puede obtener resultado particulares, pero no se trata de eso).
Acá hay unos dibujitos, pueden ver que no necesariamente el empquetamiento "trivial" (todos los cuadraditos con lados paralelos y en fila) es óptimo.
Yo por lo general me conformo con aproximaciones asintóticas, pero, de nuevo, acá no se trataba de eso.

JuanPablo dijo...

anónimo, me refería al problema de hallar el orden exacto del error en la fórmula que usó hernán; esa cota la dio Gauss, y Hardy la mejoró hará unos 80 años (en vez de un error O(R), probó O(R^{2/3}), y que era mayor a O(R^{1/2}). Después, hubo avances muy pequeños, pero ninguna cota esencialmente buena. El problema aparece en más versiones de las que uno se imagina.

martín, vos sos el más indicado para averiguarlo! (sos coautor de alguien que lo tiene en su página)

Martin dijo...
Este comentario ha sido eliminado por el autor.
Martin dijo...

Buen punto! Pero la página esa no la escribió Pedro sino un amigo (y hace 6/7 años). Pero ahora que sé quién es, le puedo preguntar!

Buscando un poquito, si miran esta página da para pensar que el problema está abierto:
http://www.stetson.edu/~efriedma/squincir/

Churi dijo...

Voy a sacarme un 1, pero voy a mejorar la cota superior de 26: menos de 31416!!

Ja!

JuanPablo dijo...

churi, entre hernán y vos ya tenemos una cota del error razonable, apenas 305 cuadraditos, o sea menos del 1%

tenés un 1 (uno)

hjg dijo...

Eh, momento, yo no "usé" ninguna fórmula, la "descubrí" (algunos siglos tarde, como siempre) por mi cuenta, no tenía idea del problema, y lo pensé así:

1.tomemos un empaquetamiento en filas horizontales, sobre el semicírculo superior, con la primer fila apoyada sobre el eje.

2. Veamos primero el largo de cada una de las barritas horizontales, suponiendo para empezar que se pueden hacer tan largas como para que toquen el borde del circulo (sin sobresalir).
En este caso, el area cubierta por las barras casi cubre el semicírculo, excepto por un cachito en cada costado. Aproximamos ese cachito por un triángulo (esencial dibujarlo). Consideremos todos esos triangulitos, imaginemos que los "bajamos" sobre el eje x. Vemos (vemos?) que ocupan precisamente la mitad del area del la barra más larga. O sea que el área perdida puede aproximarse (siempre para el semicírculo superior) por 1 x R; o sea que cada barra pierde en promedio un area equivalente a un cuadradito.

3. Pero lo anterior no basta, porque adentro de cada barra tenemos que empaquetar cuadraditos, es decir que la longitud de las barras debemos reducirla hasta que sea un número entero, o sea descartar la parte fraccionaria ¿Cuánta área perderemos en cada barrita? Sospecho fuertemente (pero que lo demuestre Magoya) que, en términos probabilísticos (y siempre para R grande) la parte fraccionaria está distribuida uniformemente en [0-1]. Por lo cual, en promedio, perderemos el area de medio cuadradito.

4. Así, sumando para todas las barras, y multiplicando por 2 para incluir el otro semicírculo, llegamos a que el área "desperdiciada" es 3 R, y por lo tanto la cantidad total de cuadraticos es (en esta "mi" aproximacion) : 3.1416 * R^2 - 3 R

4. Nótese que:
a- La aproximación 2 daría una cota inferior (pero asintóticamente ajustada... es de creer). En cambio la aproximación 3 no es cota sino aproximación por valor medio.
b- Damos por buena la suposición de que este empaquetamiento (en filas) es óptimo (lo cual, es de creer, no es verdad; a lo sumo podemos sospechar en convergencias asintóticas). O sea que hay dos errores acá: la diferencia entre el empaquetamiento óptimo de verdad y el trivial (en filas) por un lado, y el cálculo del area correspondiente a este empaquetamiento.
c- No di (ni se me ocurrió buscar) cotas ni órdenes para ninguno de los dos errores.
Es lo que hay.

JuanPablo dijo...

es lo que hay, y no está nada mal. Tendría que dedicarle un post para explicar (más o menos claro) el por qué, pero el 3 que aparece en tu estimación se puede cambiar por un 2\sqrt{2} (lo demostraron nada menos que Polya y Szego con una idea muy inocente!), y agregarle una pequeña corrección.

Con técnicas elementales, no se puede avanzar mucho más. El método del círculo de Hardy sirve para manejar las diferencias con la parte entera que molesta en cada bandita, pero implica desarrollar Fourier, y bancarse unas cuentas infernales.

pablotossi dijo...

a mi me da 7592
1898 por cuadrante.... ahora me salvé del linchamiento?

y lo justifico pensando así:

[url=http://xs.to][img]http://xs223.xs.to/xs223/08051/cubosencirculo631.jpg[/img][/url]

http://xs.to/xs.php?h=xs223&d=08051&f=cubosencirculo631.jpg

....con algo de fuerza bruta:P

Frenzo dijo...

Me gustó la demostracón de Hernan, muy fina. Un detalle: me parece que debería ser 2R (y no 3R) el área a restar del cículo (porque hay 2R filas y cada una tiene un espcio libre del orden de un cuadradito, si no entendí mal).

pablotossi dijo...

perdon, mi fuerza bruta hizo que lo hiciera como un bruto y que lo hiciera con radio 50 :P

hjg dijo...

frenzo: gracias.
se pierde un area de 2R por encajar las barras en el circulo (paso 2), pero adicionalmente 1/2 por cada barra por recortar la parte fraccionaria (paso 3). Y como son 2R barras, me da 2R + 1/2 * 2R = 3R

Frenzo dijo...

Ah, claro! Gracias

JuanPablo dijo...

pablo, por otro 1: si lo hiciste de 50 en vez de 100, alcanza con multiplicar todo por 1?