Lynne is tiling her long and narrow rectangular front hall. The hall is 2 tiles wide and 13 tiles long. She is going to use exactly 11 black tiles and exactly 15 white tiles. Determine the number of distinct ways of tiling the hall so that no two black tiles are adjacent (that is, share an edge).

## PART B

For each question in Part B, your solution must be well organized and contain words of explanation or justification when appropriate. Marks are awarded for completeness, clarity, and style of presentation. A correct solution, poorly presented, will not earn full marks.
We picture the floor as having 2 rows and 13 columns.

We solve the problem by determining the number of ways in which we can choose the 11 tiles to be black (and make the remaining tiles white). Since no two black tiles are to be adjacent, then it cannot be the case that both tiles in any column are black.

Thus, each of the 13 columns has 0 black tiles or 1 black tile.

Since there are to be 11 black tiles, then 11 columns will have 1 black tile and 2 columns will have no black tiles.

We denote each column with no black tiles by "E".

If a column has 1 black tile, it is either the top tile (we denote the column "T") or the bottom tile ("B").

Since no two black tiles are adjacent, then there cannot be adjacent columns both having the top tile black or both having the bottom tile black.

So the given problem is equivalent to determining the number of sequences of 13 characters (one for each column), where each character is $\mathrm{E}, \mathrm{T}$ or $\mathrm{B}$, with exactly two E's (for the empty columns), and with the property that there are not two (or more) consecutive T's or two (or more) consecutive B's.

We count the number of such sequences by considering a number of cases. Before considering these cases, we note that whenever there is a block of consecutive T's and B's, then there are exactly two possible configurations for this block. This is because the first letter (for which there are 2 choices) determines the second letter (since there cannot be consecutive T's or B's) which determines the third letter, and so on.

Case 1: Two E's together; EE at one end of sequence

There are 2 possible locations for the EE (either end of the sequence).

In either case, there is one block of T's and B's.

There are 2 possible configurations for the single resulting block of T's and B's (TBTB $\cdots$ or BTBT...).

In this case, there are $2 \times 2=4$ sequences.

Case 2: Two E's together; EE not at end of sequence

There are 10 possible locations for the EE (starting in any column from the 2nd column to the 11th column).

In this case, there are two blocks of T's and B's.

There are 2 possible configurations for the each of the two resulting blocks of T's and B's.

In this case, there are $10 \times 2 \times 2=40$ sequences.

Case 3: Two E's separate; one at each end of sequence

The position of the E's are fixed.

In this case, there is one block of T's and B's.

There are 2 possible configurations for the single resulting block of T's and B's.

In this case, there are 2 sequences.

Case 4: Two E's separate; one at an end of the sequence, one not at an end

There are 2 possible locations for the $\mathrm{E}$ that is at an end of the sequence.

There are 10 possible locations for the $\mathrm{E}$ that is not at an end (it cannot be at either end or next to the $\mathrm{E}$ that is at an end).

There are two blocks of T's and B's.

There are 2 possible configurations for the each of the two resulting blocks of T's and B's.

In this case, there are $2 \times 10 \times 2 \times 2=80$ sequences.

Case 5: Two E's separate; neither at an end of the sequence

The leftmost $\mathrm{E}$ could be in column 2. There are then 9 possible locations for the second $\mathrm{E}$ (columns 4 through 12).

The leftmost $\mathrm{E}$ could be in column 3. There are then 8 possible locations for the second $\mathrm{E}$ (columns 5 through 12).

We continue in this way to the last possibility, where the leftmost $\mathrm{E}$ is in column 10. There is then 1 possible location for the second $\mathrm{E}$ (column 12).

This gives $9+8+7+\cdots+1=45$ possible locations for the E's.

There are three blocks of T's and B's (to the left of the first E, between the two E's, and to the right of the second $\mathrm{E}$ ).

There are 2 possible configurations for the each of the three resulting blocks of T's and B's.

In this case, there are $45 \times 2 \times 2 \times 2=360$ sequences.

Combining all of the cases, we see that there are $4+40+2+80+360=486$ possible sequences, and so 486 possible ways of tiling the floor.

## Part B