Cubriendo un tablero

Moderador: iMPuRe

Avatar de Usuario
Black Joker !
Mensajes: 18
Registrado: 17 May 2010, 14:02
Ubicación: En un punto intermedio entre Valdivia y Osorno
Contactar:

Cubriendo un tablero

Mensajepor Black Joker ! » 28 Jun 2010, 16:34

Determine si es posible o no cubrir un tablero de [math] ocupando solamente fichas de [math] dispuestas horizontalmente y fichas de [math] dispuestas verticalmente.
"I don't wanna change the world, I just wanna leave it colder"

Avatar de Usuario
iMPuRe
Moderador
Mensajes: 92
Registrado: 01 Jul 2008, 00:18
Ubicación: San Miguel, Santiago
Contactar:

Re: Cubriendo un tablero

Mensajepor iMPuRe » 28 Jun 2010, 21:49

algun hint? :|
http://mateolimpiadasin.blogspot.com/

Avatar de Usuario
Black Joker !
Mensajes: 18
Registrado: 17 May 2010, 14:02
Ubicación: En un punto intermedio entre Valdivia y Osorno
Contactar:

Re: Cubriendo un tablero

Mensajepor Black Joker ! » 01 Jul 2010, 16:47

iMPuRe escribió:algun hint? :|


Ahora sí. La solución que le conozco requiere que se haga lo siguiente.

A cada casilla del tablero se le asigna un complejo "conveniente" :ninja:

Hay un ejercicio de la Baltic Way (1999 si mi memoria no me falla) que está íntimamente vinculado con este problema y puede servir de inspiración.

Saludos !!
"I don't wanna change the world, I just wanna leave it colder"

S. E. Puelma Moya
Mensajes: 8
Registrado: 03 Nov 2008, 17:16
Ubicación: Santiago, Chile

Re: Cubriendo un tablero

Mensajepor S. E. Puelma Moya » 05 Jul 2010, 22:18

Solución (no continuar leyendo si quiere intentarlo por su cuenta)

El tablero es 2009 x 2009, entonces cada casilla tiene coordenadas (i,j) con [math].

A la casilla con coordenadas (i,j) corresponde el monomio [math]. Cada ficha 1x2 horizontal cubre dos casillas cuyos monomios suman [math]. De la misma manera, cada ficha 1x3 vertical cubre tres casillas cuyos monomios suman [math].

Supongamos que es posible cubrir el tablero como es descrito en el enunciado. Sumando los monomios correspondientes a todas las casillas del tablero, de dos maneras distintas, se obtiene lo siguiente:

[math] = [math]

(disculpen la presentación de la igualdad en este formato, pero no tenía otra opción)

Para algunos polinomios P,Q (el lado izquierdo es sólo sumar por columnas y factorizar; el lado derecho es primero sumar los monomios de casillas cubiertas por fichas 1x2 horizontales y factorizar por X+1, para después sumar los monomios de casillas cubiertas por fichas 1x3 verticales y factorizar por Y^2+Y+1)

En la igualdad arriba, reemplace X=-1, Y=r (raíz cúbica de la unidad, distinta de 1) y el lado derecho es 0, pero el lado izquierdo es distinto de 0 (¡verificar!). Contradicción, por lo tanto no es posible cubrir el tablero como es descrito en el enunciado

Hay más problemas que pueden ser resueltos con esta técnica, aunque no me queda claro si el comodín negro se refería a esto...
Sebastián Elías Puelma Moya

Avatar de Usuario
Black Joker !
Mensajes: 18
Registrado: 17 May 2010, 14:02
Ubicación: En un punto intermedio entre Valdivia y Osorno
Contactar:

Re: Cubriendo un tablero

Mensajepor Black Joker ! » 05 Jul 2010, 23:46

S. E. Puelma Moya escribió:Solución (no continuar leyendo si quiere intentarlo por su cuenta)

El tablero es 2009 x 2009, entonces cada casilla tiene coordenadas (i,j) con [math].

A la casilla con coordenadas (i,j) corresponde el monomio [math]. Cada ficha 1x2 horizontal cubre dos casillas cuyos monomios suman [math]. De la misma manera, cada ficha 1x3 vertical cubre tres casillas cuyos monomios suman [math].

Supongamos que es posible cubrir el tablero como es descrito en el enunciado. Sumando los monomios correspondientes a todas las casillas del tablero, de dos maneras distintas, se obtiene lo siguiente:

[math] = [math]

(disculpen la presentación de la igualdad en este formato, pero no tenía otra opción)

Para algunos polinomios P,Q (el lado izquierdo es sólo sumar por columnas y factorizar; el lado derecho es primero sumar los monomios de casillas cubiertas por fichas 1x2 horizontales y factorizar por X+1, para después sumar los monomios de casillas cubiertas por fichas 1x3 verticales y factorizar por Y^2+Y+1)

En la igualdad arriba, reemplace X=-1, Y=r (raíz cúbica de la unidad, distinta de 1) y el lado derecho es 0, pero el lado izquierdo es distinto de 0 (¡verificar!). Contradicción, por lo tanto no es posible cubrir el tablero como es descrito en el enunciado

Hay más problemas que pueden ser resueltos con esta técnica, aunque no me queda claro si el comodín negro se refería a esto...


Sep, a esta técnica me refería y esta era la sol esperada. Cuando la vi me llamó la atención por lo simpática y poderosa. Respecto al problema, recuerdo vagamente que lo vi casi en la misma version, pero en vez del [math] había un [math] y la solución expuesta era por argumentos de coloración. Esa version tambien podia resolverse ocupando la tecnica mostrada por S.E.Puelma Moya, y en base a esto sospecho que el mismo argumento de coloracion podria funcionar.

Asi que el interesado puede intentar atacar el problema con coloración.

Saludos y porfa que se mueva a resueltos.
"I don't wanna change the world, I just wanna leave it colder"

Jumbito
Mensajes: 55
Registrado: 19 Jul 2008, 15:50

Re: Cubriendo un tablero

Mensajepor Jumbito » 18 Jul 2010, 21:23

Si no me equivoco el problema que se cita es el siguiente:

Problema. ¿Podemos llenar un tablero de [math] usando solo rectangulos de [math], [math], tal que la casilla central quede vacía (y solo esta casilla)? (Baltic Contest 1998).

Solución. Suponga que el cubrimiento es posible, y etiquetemos cada casilla del modo usual (esto es, la casilla [math] esta en la fila [math] y columna [math] del tablero). Ahora, asociamos a la casilla [math] el número [math] (donde [math]). La suma de los numeros en un rectangulo de [math] es [math]. Entonces la suma de todos las casillas del tablero es igual al numero situado en el centro del tablero, esto es [math], que es falso. Finalmente no existe el cubrimiento mencionado.

Referencia. Problems from the book
Felipe Arbulú

Avatar de Usuario
Black Joker !
Mensajes: 18
Registrado: 17 May 2010, 14:02
Ubicación: En un punto intermedio entre Valdivia y Osorno
Contactar:

Re: Cubriendo un tablero

Mensajepor Black Joker ! » 21 Jul 2010, 00:00

Jumbito escribió:Si no me equivoco el problema que se cita es el siguiente:

Problema. ¿Podemos llenar un tablero de [math] usando solo rectangulos de [math], [math], tal que la casilla central quede vacía (y solo esta casilla)? (Baltic Contest 1998).

Solución. Suponga que el cubrimiento es posible, y etiquetemos cada casilla del modo usual (esto es, la casilla [math] esta en la fila [math] y columna [math] del tablero). Ahora, asociamos a la casilla [math] el número [math] (donde [math]). La suma de los numeros en un rectangulo de [math] es [math]. Entonces la suma de todos las casillas del tablero es igual al numero situado en el centro del tablero, esto es [math], que es falso. Finalmente no existe el cubrimiento mencionado.

Referencia. Problems from the book


El problema que recuerdo era así (la versión del 102 Combinatorics Problems )

Suponga que un tablero de [math] pueden ser cubiertos por fichas de [math] y [math]. Entonces [math] y [math], pero en todo caso la técnica es bien poderosa y eso es lo importante.


Saludos :P
"I don't wanna change the world, I just wanna leave it colder"



Volver a “Problemas Resueltos”