El Acertijo 05, página 08

Etiquetas:


2 comentarios:

Anónimo dijo...

Tengo una idea que podría servir para una demostración de que no se puede generar un bosque infinito partiendo de un conjunto finito de números; cuando la retoque un poco la pondré aquí.

¡Excelente problema!

22/6/08, 18:10  
Anónimo dijo...

Esta solución es de Germán Zorba (lector de Snark):


Una estrategia para demostrar que no pueden ser infinitos puede ser la siguiente:

Para cada casillero cuento la distancia a los K casilleros elegidos al principio.

Para cada entero D, acotamos por debajo el valor del primer número que puedo
poner a distancia D de los casilleros originales, llamamos p(D) a esta cota.

Por ejemplo p(0)=1, porque el primer número que pongo es el 1
p(1)=3, porque puedo poner un 3 junto al 1 y al 2 (suponemos que K>=2)

En general, el menor valor posible para el primer número a distancia D se obtendría si lo ponemos junto a los dos menores a distancia D-1, así que proponemos la recursión
p(D)=p(D-1)+p(D-1)+1

que lleva a la fórmula p(D)=2^(D+1)-1

Ahora acotamos (por arriba) la cantidad de casilleros a distancia menor a D. Una cota muy burda para esto es K * (2D-1)^2. Esto nos da una cota superior para el primer número que pongo a distancia D de los K originales : K * (2D-1)^2+1

Ahora, basta con notar que para D suficientemente grande 2^(D+1)-1>K * (2D-1)^2+1. Este valor de D acota la porción del tablero que se puede utilizar, y por lo tanto el bosque no puede ser infinito.

Encontrar los bosques más grandes posibles es otro cantar, lo primero que buscaría es desarrollar técnicas para fabricar bosques muy grandes, y refinar las cotas de arriba con la esperanza de que cotas y tamaños de bosques encontrados se igualen. Por el momento no se me ocurre mejor estrategia que eso y no tengo la paciencia suficiente para llevarla adelante.

22/7/08, 12:21  

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)