Maths Olympiad Prep

Library / Canadian Mathematical Olympiad /15 of 57

Canadian Mathematical Olympiad

Combinatorics Difficulty 6.0 National Olympiad Prove it Canada

Problem:

Given an m×nm \times n grid with squares coloured either black or white, we say that a black square in the grid is stranded if there is some square to its left in the same row that is white and there is some square above it in the same column that is white (see Figure).
Figure 1
A 4×54 \times 5 grid with no stranded black squares

Find a closed formula for the number of 2×n2 \times n grids with no stranded black squares.

Solution

Solution:

There is no condition for squares in the first row. A square in the second row can be black only if the square above it is black or all squares to the left of it are black. Suppose the first kk squares in the second row are black and the (k+1)(k+1)-st square is white or k=nk=n. When k<nk<n then for each of the first k+1k+1 squares in the first row we have 2 choices, and for each of the remaining n−k−1n-k-1 columns we have 3 choices. When k=nk=n, there are 2n2^{n} choices for the first row. The total number of choices is thus:
∑k=0n−12k+13n−k−1+2n \sum_{k=0}^{n-1} 2^{k+1} 3^{n-k-1} + 2^{n}
This expression simplifies to
2⋅3n−2n 2 \cdot 3^{n} - 2^{n}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.