domingo, 24 de agosto de 2003
Hace un tiempo publiqué este acertijo:
"Dicen que este sabueso visitó todas las casillas del tablero.
Encuentren como fue el recorrido... o demuestren que es imposible de lograr."
La solución de este acertijo implica el conocimiento de un "criterio" que permite solucionar infinidad de problemas que aparentemente no tienen nada que ver entre si.
Intenten solucionarlo por su cuenta antes de leer la explicación que sigue.
Lo primero es comenzar a probar algunos recorridos intentando familiarizarnos con el problema.
Luego de unos tanteos al azar, nos convenceremos que cualquier recorrido que hagamos nos deja siempre una casilla sin recorrer. ¿Qué hacer entonces?
La idea luminosa que permite solucionarlo es el llamado "criterio de paridad" también conocido como "criterio del damero" o "del tablero de ajedrez".
Pintamos el tablero como si fuera un tablero de ajedrez:
Ahora bien: Si las contamos, vemos que hay 13 negras y 12 blancas. Para que el recorrido pueda hacerse entonces, se debería empezar por una casilla negra (¿por qué?), pero el número 1 fue puesto en una casilla de las blancas. El recorrido es por lo tanto imposible.
Es increíble la cantidad de problemas que pueden solucionarse de esta manera.
Por ejemplo este:
Mi tío quiere embaldosar un patio cuadrado de ocho casillas de lado que tiene en dos de sus ángulos unos hermosos árboles tal como se ve en la siguiente figura.
Muestre como hacer el cubrimiento o demuestre que es imposible
Más adelante les propondré otros problemas que se resuelven con el "Criterio de paridad". (aunque, claro, no les avisaré que es así)
Suscribirse a:
Enviar comentarios (Atom)
25 comentarios:
siguiendo el criterio ése de paridad, se ve que es imposible. Si pintamos los cuadritos en plan tablero de ajedrez, vemos que los dos árboles quedan en cuadros del mismo color. esto hace que queden 30 cuadros de un color, y 32 del otro, lo cual hará que nunca encaje la última baldosa de 2x1.
para poder hacerlo, tendrían que estar los árboles en baldosas de distinto color... o bien, partir la baldosa por la mitad (a veces vale más fuerza que maña...)
Bien Anejo.
Lo que falta decir (y que seguramente anejo da por supuesto) es que no importa como ubiquemos las baldosas de 2x1, estas siempre ocuparán 1 casilla de un color y otra del otro, por eso es que siempre nos termina sobrando una baldosa y dos casillas.
Otro tema, un poco más complicado es algo que anejo dice al pasar.
Si en el patio de 64 casillas plantamos dos árboles en cualquier parte, ubicándolos en casillas de "distinto color"
¿Igual se puede hacer el cubrimiento
Aquí no sirve el criterio de paridad ya que tenemos la misma cantidad de casillas de ambos colores. ¿Se podrá?
En realidad ya está demostrado que si se puede. Algún día postearé la demostración. O, tal vez, a alguno le tiente encontrarla....
muy buena la explicación! sencilla, simple, directa, blablabla...
Te dejo una generalización (de todo):
el patio con los dos arbolitos, 1) ¿se puede embaldosar con baldosas en forma de L, hechas con 3 cuadraditos, el del 'vertice' negro y los dos laterales blancos, de manera que alternen una blanca y una negra?
2) ¿y si hay baldosas con el vértice negro y otras de color blanco?
Baldositas así:
N B
B
o así:
B N
N
Bueno, no se si mi solución será válida o no, pero ahí va:
Tenemos 62 casillas, 31 de cada "color", y cada baldosa ocupa por fuerza dos casillas de colores distintos, podemos dividir esas 62 casillas en 31 grupos de dos casillas (cada una de un color distinto), por tanto sí se podría cubrir todo el patio.
nop
Jazzgas escribió: "Bueno, no se si mi solución será válida o no, pero ahí va:
Tenemos 62 casillas, 31 de cada "color", y cada baldosa ocupa por fuerza dos casillas de colores distintos, podemos dividir esas 62 casillas en 31 grupos de dos casillas (cada una de un color distinto), por tanto sí se podría cubrir todo el patio."
tienes la mitad de tu planteamiento correcto, pero ¿por qué afirmas que si se puede? siguiendo tu planteamiento llegas a la conclusion de que para meter 31 medio-baldosas de color negro hace falta 31 medio-baldosas blancas. O lo que es lo mismo, hace falta tantas baldosas de un color como del otro. Pinta los cuadritos y te darás cuenta de que hay 30 blancas y 32 negras, llegando a la conclusión de que no se pueden poner esas baldosas.
A lo que dice JuanPablo, parece que he encontrado una explicación bastante sencilla... Si hay 62 cuadraditos, y cada baldosa en L ocupa 3 de ellos... ¿no me salen las cuentas o es que necesito 20.6666666... baldosas?
lo siento, parece que he j**ido un poco el diseño de tu página al escribir con un nombre más largo.
ahora mismo lo arreglo.
c_u_m_i_c... es mi nuevo apodo (que es lo mismo pero con iniciales)
3
2
5
7
8
esto no lo hago por egocentrismo, sino porque puedan ver bien la buenísima página que te has currado
A ver, vamos por partes (si puedo)
En el cuerpo del post, había dejado un problema que creo que fue suficientemente respondido por anejo y después por CUMIC
Luego, en estos comments puse una variante:
De un tablero de 64 casillas sacamos dos cualesquiera de distinto color (es decir, que nos quedan 31 de cada color) ¿Se puede cubrir siempre con baldosas de 2x1?
Creo que eso es lo que intentó responder Jassgas, sin embargo su respuesta no es correcta (o al menos no es completa)
Es cierto que es condición necesaria que haya la misma cantidad de casillas de ambos colores para que se pueda hacer, pero no es suficiente
Por ejemplo, imaginemos un tablero en forma de T
NBNBN
__B__
__N__
__B__
Si sacamos las dos casillas con asterisco
NBNBN
__*__
__*__
__B__
No se puede completar con baldosas de 2x1 aunque hay la misma cantidad de cada una.
No es tan simple... se los dejo.
Después vino Juan Pablo con algo que parece... ¿un cazabobos?
Y finalmente la aparición rutilante de CUMIC (que de modorra nada)Bienvenido
bueno, tratándose de un tablero de 64 casillas completamente cuadrado (ya que se trata de un tablero de 8x8 casillas), resulta obvio que sí se podrá completar el embaldosado con piezas de 2x1...
pero para demostrarlo sólo se me ocurre usar un razonamiento lógico, no matemático: la única manera de conseguir que no se pudiera hacer (teniendo en cuenta que sólo disponemos de dos "árboles"), sería aislando una de las casillas de la esquina, así:
B=blanca
N=negra
A=árbol
B A B
A B N
B N B
La primera B queda aislada (como en el ejemplo del tablero con forma de T), y no se puede cubrir. ¿Cuál es el problema? Que para ello habría que colocar los árboles en casillas del mismo color. Como la condición es colocarlos en casillas de distinto color, y no hay manera de aislar una esquina con dos árboles en casillas de distinto color (un segundo para que coja aire y acabo la frase...) ... pues eso, siempre se podrá cubrir el tablero
no, no era un cazabobos! Era pasar de múltiplos de 2 a mútliplos de 3, muy bien respondido todo por cumic...!
El 1) tiene otra demostración, si cada baldosa tiene dos B y una N, al embaldosar, habrá el doble de casillas B que de N.
vale, pero sí era un poco cazabobos... ;P
algo había ;-)
Holas de nuevo:
Anejo:
Lo que decís está bien, pero no termina por demostrarlo.
Una manera sería probar las 1024 maneras de elegir dos casillas de diferente color y (de)mostrar que siempre se puede hacer el embaldosado.
Esto, aparte de tedioso, no demostraría el caso general de tableros de nxm (donde uno de los dos lados es par)
Lo que alguien hizo no fue una demostración matemática en sentido extricto sino quese ideó un procedimiento que garantiza que siempre se puede hacer el cubrimiento.
En si, no es difícil, aunque claro, dicho esto después de haber visto la solución :-)
Uno de estos días haré un post con este tema.
Juan Pablo: ¿Y cazaste alguno?
Vos sos el 1ro, Markelo ;-)
La verdad que no tengo perdón. ¡Darte el pie para que me contestes! ;-)
jajajaja!
quisiera saber cuantos cuadrados se forman en un tablero de ajedrez. No son 64.
Publicar un comentario