In how many ways can we tile a horizontal strip $2 \times n$ with bricks $1 \times 2$ or $2 \times 1$?
This exercise is similar to the previous one. We denote $F_{n}$ as the number of ways to tile a horizontal strip $2 \times n$ using bricks $1 \times 2$ or $2 \times 1$.

It is clear that $F_{0}=1$ and $F_{1}=1$: The only way to tile an empty space is to place no dominoes, and only one domino $2 \times 1$ fits in a strip $2 \times 1$.

Let's return to the general case with a strip of size $n+2$. Consider the 4 rightmost squares. Either the two rightmost squares are occupied by a domino $2 \times 1$, and removing it leaves a strip $2 \times (n+1)$ properly tiled ($F_{n+1}$ possibilities), or the 4 rightmost squares are two horizontal dominoes $1 \times 2$, and in this case, removing them leaves a strip $2 \times n$ properly tiled ($F_{n}$ possibilities). Since the two cases are disjoint, we obtain the relation:

$$
F_{n+2}=F_{n+1}+F_{n}
$$

The same recurrence as in the previous exercise allows us to conclude that $F_{n} = \frac{1}{\sqrt{5}}\left(\varphi^{n+1}-\bar{\varphi}^{n+1}\right)$.

## 3 Game Strategies, Combinatorics TD (Théodore Fougereux)

## Symmetry in Game Theory

## Examples and Exercises

Symmetry is often a useful idea in two-player games. The idea is to mirror the opponent's move symmetrically to always ensure a legal move.

## Example 1.

Alice and Bob play tic-tac-toe on a $2020 \times 2020$ grid, their goal is to align 2020 crosses (or 2020 circles). A turn consists of Alice placing a cross and then Bob placing a circle. If Alice and Bob make a line in the same turn, it is a draw; otherwise, the first to create a line wins. Show that Bob can ensure he does not lose.