Problem

Source: 2002 Romania JBMO TST 1.3

Tags: rectangle, Tiling, tiles, combinatorics, Coloring



Consider a $1 \times n$ rectangle and some tiles of size $1 \times 1$ of four different colours. The rectangle is tiled in such a way that no two neighboring square tiles have the same colour. a) Find the number of distinct symmetrical tilings. b) Find the number of tilings such that any consecutive square tiles have distinct colours.