Problem

Source: Tuymaada 2022 Senior P-7

Tags: combinatorics, tiels, domino, rectangle



A $1 \times 5n$ rectangle is partitioned into tiles, each of the tile being either a separate $1 \times 1$ square or a broken domino consisting of two such squares separated by four squares (not belonging to the domino). Prove that the number of such partitions is a perfect fifth power. (K. Kokhas)