El Número de Oro

por **Black Joker !** » 28 Jun 2010, 16:34

Determine si es posible o no cubrir un tablero de $2009\times 2009$ ocupando solamente fichas de $1\times 2$ dispuestas horizontalmente y fichas de $1\times 3$ dispuestas verticalmente.

por **iMPuRe** » 28 Jun 2010, 21:49

algun hint?

por **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 !!

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

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

Mostrar

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...

por **Black Joker !** » 05 Jul 2010, 23:46

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

Mostrar
El tablero es 2009 x 2009, entonces cada casilla tiene coordenadas (i,j) con $i,j\in\{0,1,...,2008\}$ .

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

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:

$(X^{2008}+\ldots+X+1)(Y^{2008}+\ldots+Y+1)$ = $P(X,Y)\cdot(X+1)+Q(X,Y)\cdot(Y^2+Y+1)$

(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 2009

había un

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.

por **Jumbito** » 18 Jul 2010, 21:23

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

Problema. ¿Podemos llenar un tablero de $13\times 13$ usando solo rectangulos de $1\times 4$ , $4\times 1$ , 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 $(k,j)$

esta en la fila $k$

y columna

del tablero). Ahora, asociamos a la casilla $(k,j)$

el número $i^{k+2j}$ (donde $i^2=-1$

). La suma de los numeros en un rectangulo de $1\times 4, 4\times 1$ es $0$

. Entonces la suma de todos las casillas del tablero es igual al numero situado en el centro del tablero, esto es $i^{21}=(1+i^2+...+i^{13})(i^2+i^4+i^{26})=i\cdot\dfrac{i^{13}-1}{i-1}\cdot i^2\cdot \dfrac{i^{26}-1}{i^2-1}=i^3$ , que es falso. Finalmente no existe el cubrimiento mencionado.

Referencia. Problems from the book

por **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 $13\times 13$ usando solo rectangulos de $1\times 4$ , $4\times 1$ , 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 esta en la fila y columna del tablero). Ahora, asociamos a la casilla el número $i^{k+2j}$ (donde ). La suma de los numeros en un rectangulo de $1\times 4, 4\times 1$ es . Entonces la suma de todos las casillas del tablero es igual al numero situado en el centro del tablero, esto es $i^{21}=(1+i^2+...+i^{13})(i^2+i^4+i^{26})=i\cdot\dfrac{i^{13}-1}{i-1}\cdot i^2\cdot \dfrac{i^{26}-1}{i^2-1}=i^3$ , 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 $a\times b$ pueden ser cubiertos por fichas de $1\times n$ y $m\times 1$ . Entonces m|a

y

, pero en todo caso la técnica es bien poderosa y eso es lo importante.

Saludos

El Número de Oro

Cubriendo un tablero

Cubriendo un tablero

Re: Cubriendo un tablero

Re: Cubriendo un tablero

Re: Cubriendo un tablero

Re: Cubriendo un tablero

Re: Cubriendo un tablero

Re: Cubriendo un tablero

¿Quién está conectado?