Solución Desafío 24: Así se tapa una mesa


pulsar aquí.

Recordemos el problema: se trata de demostrar que, dados un tablero rectangular y un número suficientemente grande de discos todos del mismo tamaño, si con un número n de estos discos consigo llenar el tablero (llenar significa colocar los discos con sus centros dentro del tablero de forma que no se superpongan y que no quepa ningún disco más), entonces con 4n discos conseguiré tapar el tablero (tapar significa colocar los discos con sus centros dentro del tablero de forma que todos los puntos del tablero queden dentro de uno de los discos).

La solución propuesta por el Profesor Gimenez es la siguiente:

Supongamos que tenemos una configuración de n discos que llena el tablero.

En primer lugar, observaremos que si en esta configuración duplicamos el radio de los discos, entonces taparemos el tablero. En efecto, en la configuración que llena el tablero vamos a sustituir los n discos de radio r por n discos grandes de radio 2r (los centros de los discos no han cambiado). Si en esta nueva configuración algún punto del tablero no estuviera tapado por ninguno de los n discos grandes, esto significaría que este punto, que llamaremos P, estaría a una distancia estrictamente mayor que 2r de todos los centros de los discos. Pero si volvemos a nuestra configuración original con discos de radio r, esto significa que en P podríamos colocar otro disco de radio r que no se solaparía con ninguno de los n discos pequeños, lo cual contradice que el tablero estuviera lleno con nuestros n discos. Por lo tanto no existe tal punto P, es decir que el tablero ha quedado totalmente tapado con los n discos de radio 2r.

Pero eso no es lo que se pedía ya que lo que pretendemos es tapar la mesa con discos de radio r. Lo que haremos entonces es un zoom, una reducción al 50% de todas las distancia en esta configuración. Conseguimos de esta manera que los discos grandes vuelvan a tener el tamaño correcto ya que su radio se parte a la mitad. Pero en esta reducción, las medidas del tablero también se han partido a la mitad por lo que hemos conseguido tapar con n discos de radio r un tablero con la mitad de largo y la mitad de ancho que el tablero original.

Este pequeño tablero representa exactamente una cuarta parte del tablero original ya que al partir a la mitad el largo y el ancho del tablero, obtenemos 4 tableros idénticos con la mitad de largo y la mitad de ancho. El razonamiento anterior nos dice que cada una de estas 4 partes del tablero original se puede tapar con n discos de radio r, por lo que el tablero original se puede tapar con 4n discos de radio r, que es lo que había que justificar.

Observamos además que esta demostración es constructiva. En efecto no sólo nos dice que se puede, sino que también nos dice cómo hacerlo. Si empezamos con n discos que llenan el tablero, entonces fijándonos en los centros y reduciendo todas las distancias a la mitad, obtendremos la posición de los centros de los n discos que taparán la cuarta parte del tablero. Basta reproducir en las 4 partes iguales del tablero esta configuración para tapar nuestro tablero original.

La mayoría de las soluciones que dimos por válidas y que no usaban el razonamiento anterior consistieron en intentar determinar la manera de llenar un tablero rectangular usando el menor número de discos posible y, para esta configuración particular, demostrar la propiedad. En efecto, aunque se pidiera demostrar la propiedad para cualquier manera de llenar el tablero, si se demuestra para una configuración que use el menor número de discos posible, la propiedad quedará demostrada para todas las formas de llenar el tablero. El problema de esta solución es que transforma el problema original en un problema mucho más complejo por lo que casi ninguna de estas soluciones ha sido del todo correcta. En efecto no es nada trivial encontrar esa configuración más económica ya que los bordes del tablero dan muchos problemas. Aun así, dado el gran esfuerzo realizado y la elegancia de algunas partes del razonamiento, hemos decidido dar por buenas estas soluciones.

Cabe destacar que había otra manera sencilla de demostrar la propiedad haciendo una demostración por inducción (para los que dominan esta técnica) sobre el número n de discos utilizados para llenar el tablero. El primero en hacer una inducción correcta ha sido José Miguel Gómez Contreras. Para la demostración por inducción, hay que tener un poco de cuidado para la justificación del primer paso, el caso en el que el tablero se llena con un solo disco (¡ojo!, la mesa es rectangular y no cuadrada). Para el paso inductivo, basta con elegir una recta que parta el tablero en dos partes rectangulares y que deje al menos un disco en cada lado (hay infinitas formas de hacerlo). Aplicando la hipótesis de inducción a cada trozo de tablero obtenemos la propiedad para el tablero original.

El error más común ha sido justificar la propiedad para una manera particular de llenar la mesa (sin justificar que ésta sea la que usa en menor número de discos como hemos observado antes). Por ejemplo, algunos han llenado la mesa con muchos discos, intentando colocar el mayor número de discos posible sin que se solapen, por lo que conseguían justificar en general que no era necesario usar 4 veces el número de discos sino que casi siempre con el doble era suficiente pero eso no era lo que queríamos justificar. Otro error común partía de una buena idea: podríamos intentar sustituir, en nuestra configuración que llena el tablero, cada disco por una configuración de 4 discos que tapen una mayor superficie y así intentar tapar todo el tablero. Han aparecido de manera recurrente dos configuraciones de 4 discos pero desgraciadamente ninguna de las 2 funciona siempre. Aunque funcione muy bien con un solo disco en un tablero cuadrado por ejemplo, es fácil encontrar configuraciones donde esto no funciona. Finalmente tampoco han faltado los que han querido demostrar que la propiedad no era cierta aportando contraejemplos. Si pensáis en un ejemplo donde la propiedad no parece cierta, podéis usar la demostración constructiva presentada en el video para colocar, en esta configuración, los centros de los discos que taparan el tablero en vuestro ejemplo y así convenceros de que la propiedad es siempre cierta.

Solución de José Luis Miota Rincón: 24 Cómo tapar una mesa.Maito

Solución de Pedro Correa: Solución desafío 24 PEDRO CORREA

 

 

Deja un comentario

Archivado bajo OTROS

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s