6

Part of 2000 South africa National Olympiad

Problems(1)

Tiling of a 4 x n rectangle

Source: South Africa 2000

A_n

be the number of ways to tile a

4 \times n

rectangle using

2 \times 1

tiles. Prove that

A_n

is divisible by 2 if and only if

A_n

is divisible by 3.

geometryrectanglecombinatorics unsolvedcombinatorics