Olimpíada Nacional de Sudáfrica 2000 (rectángulo de 4 azulejos con baldosas de 2 x 1)

Question

Deje $A_n$ el número de maneras de baldosa $4×n$ rectángulo usando $2×1$ azulejos. Demostrar que $A_n$ es divisible por 2 si y sólo si $A_n$ es divisible por 3.

Mi intento: Definir formas básicas, a, B y C, donde las áreas sombreadas son ocupados por los lazos. Va de forma recursiva, vamos $A(m)$, $B(m)$, $C(m)$ indique el número de maneras para llenar el resto de la onu-área sombreada de a, B, C en la posición $m$ (por ejemplo, $A(0)$ significa que el número de maneras de rellenar un espacio en blanco $4×n$ rectángulo).

Obviamente $A(0) = A(2) + B(0) + B(1) + C(1)$, $B(0) = A(1) + A(2) + B(2)$, $C(1) = A(2) + C(3)$, $B(1)= A(2) + A(3) + B(3)...$, pero, ¿cómo demostrar $A(m) \equiv 0, 1, 5 (mod\space6)$?

Answer 1

Este es un muy típico de la olimpiada de estilo de problema. Todos ellos pueden normalmente ser resuelto con la misma maquinaria.

En primer lugar, me gustaría recomendar ligeramente la redefinición de su serie $A$, $B$, y $C$, tal como están "al revés". Deje $A'(n) = A_n$. Deje $B'(n)$ el número de maneras de colocar azulejos $4 \times n$ rectángulo si la columna de la derecha contiene exactamente una vertical de domino, que toca la esquina superior derecha. Deje $C'(n)$ el número de maneras de colocar azulejos $4 \times n$ rectángulo si la columna de la derecha contiene exactamente una vertical de domino, el cual toca ni a la esquina superior derecha ni a la esquina inferior derecha.

Se puede derivar una lineal simple recurrencia expresan $A'(n)$ en términos de reducción de valores de los términos, de forma similar a como lo tienes tu "obvio" que las condiciones iniciales. Del mismo modo se puede derivar de las recurrencias de $B'(n)$$C'(n)$.

El uso de algunos conceptos básicos de la "recurrencia" de álgebra, puede eliminar todas las $B'$ $C'$ términos para obtener una sola recurrencia lineal con sólo $A'$ términos. Desde la recurrencia es lineal, debe ser periódica modulo 6. Usted simplemente necesita para calcular los primeros mod 6 valores hasta que comienza la repetición y, a continuación, la prueba será completa.