← Back to the programme
    OlympiadMediumCombinatorics5–6

    Tiling a 2 × n Board with Dominoes

    Cobrir um Tabuleiro 2 × n com Dominós

    A 2×n2 \times n board is to be tiled with 1×21 \times 2 dominoes. Find the number of tilings for n=5n = 5.

    Let T(n)T(n) be the number of tilings. Find T(1)T(1), T(2)T(2), T(3)T(3) and look for a recurrence.

    Solution

    Step 1 of 5

    1. 1.T(1)=1T(1) = 1, T(2)=2T(2) = 2, T(3)=3T(3) = 3, T(4)=5T(4) = 5